## CodingBison

Let us go through some of the common problems related to two-pointer technique.

### 2-Sum related Problems

In 2-Sum, the goal is to find two elements that add up to K in a sorted array (arr). The brute-force approach would be to run two for-loops (i and j) and check if the sum matches K or not. However, this approach would be O(N^2). Instead, we can use two pointer will also allow us find all pairs that add upto K. Here is how we can do that:

• Have two pointers: one at start and another at end.
• Check the sum of (arr[start]+ arr[end]).
• If the sum is greater than K, then decrement end.
• If the sum is greater less than K, then increment start.
• If the sum is equal to K, then you have found your match! If you want to find more pairs, then you can decrement end and increment start (since we want to skip the current pair) and continue.
• Keep doing this till start < end. If we did not find any match, then such two elements do not exist.

There is a lot of variation of the basic 2-Sum. We list some of them below.

#### Valid Triangle Number

Given an array consists of non-negative integers, count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. So, if input is [2,2,3,4], then we can have (2,3,4), (2,3,4) , and (2,2,3) and so the output should be 3.

Here are the high-level steps:

• In this case, we start by sorting the array.
• Fix the last element (using pointer k) a[k] and then do a two-pointer (i and j) such that (a[i]+a[j]) > a[k].
• If (a[i]+a[j]) > a[k], then for this (i,j) and k, the answer would be (j-i) since all of these can form a triplet with k.
• Next reduce k and check.

#### Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). We have to find two lines that together with the x-axis form a container, such that the container contains the most water.

• Start from both ends and keep walking towards the center. At each point calculate the area -- this area is a candidate.
• When going from the two ends towards center, if a[l] < a[h], then do l++. The idea is that you want to seek a line that is higher than the current line.
• On the other hand, if a[l] > a[h], then do h-- since the right hand side line is shorter than the one at the left-end. Keep doing this till (l <= h).

#### Max Number of K-Sum Pairs

In this problem, we have to find all the pairs that add up to K. This problem is same as regular 2-Sum except that if we find a pair that adds upto K, then in that case, we skip both the pointers (so increment i and decrement j) and the idea is that we have already counted this pair and so we can skip both the pointers.

Here is the implementation (in Java):

``` public int maxOperations(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int ret = 0, i = 0, j = n-1;

while (i < j) {
if ((nums[i]+nums[j]) == k) {
ret++;
i++;
j--;
} else if ((nums[i]+nums[j]) > k) {
j--;
} else {
i++;
}
}
return ret;
}
```

#### 2 Sum Closest

This is similar to 2 Sum. If the current sum is higher, then drop the right one (decrement the right pointer (say j)). If the current sum is lower, then drop the left one (increment the left pointer (say i)). At each point, evaluate (a[i]+a[j]) as a candidate.

There are other problems that ask 2Sum Closest as well. Here are some of those questions:

##### Find two weights in a Bag with Capacity C

Problem: Given a bag with capacity C as integer value, and an int list, find 2 numbers from the list such that we can fill this bag with min space left.

For example, let the bag capacity C is 10 and the array list is [1, 2, 3, 4, 5]. The answer is [4, 5]. In this case, we simply need to find two numbers such that either they equal the capacity C or come closest to it.

##### Movies on Flight

Problem: You are on a flight and wanna watch two movies during this flight. You are given int[] movie_duration which includes all the movie durations. You are also given the duration of the flight which is d in minutes. Now, you need to pick two movies and the total duration of the two movies is less than or equal to (d - 30min). Find the pair of movies with the longest total duration.

If multiple found, return the pair with the longest movie. Once again, we need to find two pairs such that it equals the duration (d -30min) or comes closest to it.

##### Two Sum Less Than K

Given sum K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1.

### 3-Sum related Problems

#### 3Sum

Given an array, find all three elements a, b, c such that a + b + c = 0. The combinations need to be unique. Here is the way to do that:

• We sort the input array.
• Next, we process arr[i] (i starts from 0 till N-3, where N is the length of the array).
• When we process arr[i], we find two elements in the right subarray of i (from i+1 till N-1) that equal to -arr[i].
• We do not consider anything left of arr[i] since if that were a candidate, then that would have been considered already.
• The problem can have duplicates. The usual trick to avoid duplicate combinations is being used here as well. If (j != i) && (a[j]==a[i]) then skip. We can also do this when selecting the two elements on the right of arr[i] and so check needs to be pretty thorough!!
• Note that if someone were to ask the same for 2Sum (array has duplicates but return only the unique ones), then we can use the same trick to weed out duplicates as above.

#### 3Sum Closest

This is same as 3 Sum. Given an array, find all three elements a, b, c such that a + b + c is closest to the target. Here we do not have to worry about duplicates since this would not affect the final answer.

#### 3Sum Smaller

Similar to 3Sum but the ask is to find three numbers such that a+b+c < target. Here is how we can do that:

• Sort the array.
• For each arr[i], see if we have (arr[i]+b+c) < target.. If so, then take the count of all the numbers between b and c and go the right of arr[i].
• If we have (arr[i]+b+c) >= target, then it is too big and we should drop the rightmost one and explore further.

#### 3Sum With Multiplicity

Even here, we should try the case, where a[i] is the last element of the three and check in the hashmap that has all elements from 0 to i-1 if there are two elements that add up to K-a[i]. Following that we should add a[i]. Note that since we are checking for two elements, we would still need to avoid the above issue (since we are checking from 0 to i-1 and all elements are already loaded in the hashmap) since there is not much we can do here.

Note that if we were to use HashMap to find two elements, then we do not know if the current element is already being accounted for or not. For example, if array is [2, 1, 0, 100] and we want to check if two elements add up to 4, then since we have already added 2, when we look at 2, we would find that 4-2 already exists. So, to avoid this issue, as we proceed, we add a[i] only after we have checked for K-a[i] in the array.

### 4-Sum related Problems

#### 4 Sum

Given an array, how many (a,b,c,d) are there in the array such that a + b + c + d = K? The solution set must not contain duplicate quadruplets.

• This is all about optimization since the time-complexity is O(N^3)
• So, this finds 4Sum using 3Sum and that uses 2Sum.
• For the outermost number (this is the a[i] and for this a[i], we need to find three numbers]),
• If (a[i] + 3 * max < target), then skip. This means that even if we were to combine a[i] with all the three max and if the value is still less than target, then that means a[i] is too small.
• If (4 * a[i] > target) break; Because, we have reached an a[i] such that 4 times of a[i] is itself bigger than target -- there is no point calling Has3Sum on this or on any element to the right of a[i].
• Also, to eliminate duplicates, at each layer, if a[i] is same as a[i-1], then we can skip that.

There are some cool optimizations that focus on target being less than being the smallest *K and target being higher than the highest * K:

• In 4Sum, if the target is less than 4 * a[lo] or if target is higher than 4 * a[hi], then we have no solution.
• In 3Sum, if the target is less than 3 * a[lo] or if target is higher than 3 * a[hi], then we have no solution.
• In 2Sum, if the target is less than 2 * a[lo] or if target is higher than 2 * a[hi], then we have no solution.
• So, the above is, in some ways, lesser than the least and higher than the highest approach.

#### 4 Sum II

Given 4 lists A, B, C, D, how many tuples (i, j, k, l) have A[i] + B[j] + C[k] + D[l] is zero.

A naive solution would be O(N^4). Here, we can use the unique solution to consider lists (A, B) first and then consider lists (C, D). In doing so, we know that we are processing elements uniquely.

• In this case, we find all pair sums of (A, B) and store it in a hashmap.
• Next, we iterate over all pair sums of (C, D) (say M) -- and for each M, we see if we have (X-M) in the hashmap.
• This reduces the time-complexity to O(N^2) and the space-complexity to O(N+M), where N and M are the lengths of A and B.

This does not apply to "4Sum" since we only one one list. We cannot apply the above here. Let us say, we can, then we can split 4Sum into two lists but what if the 4 elements come from the single list.. So, "4Sum II" is a unique problem since it says that the solution must have one element from each of the list.

Note that this problem is similar to the problem of finding a^3+b^3=c^3+d^3.

• Find (a^3+b^3) for all pairs of (a, b). Then put them in a hashmap.
• Next, find (c^3+d^3) for all pairs of (c, d). Check if they existing the hashmap.

#### Split Array with Equal Sum

Given an array, find subarrays such that sums of (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) should be equal.

We take a similar approach as that of 4 Sum II.

• Once again, vary i and j and get all the equal sums (pre-compute prefix sum to reduce time complexity).
• Next, vary j and k and see if we can find an equal sum that also exists in the (i, j) subarray values stored in the hashtable.
• BTW, it is NOT asking to split the array into 4 equals parts. If that were the case, then it would have asked sums of (0, i - 1), (i, j - 1), (j, k - 1) and (k, n - 1) should be equal. "
• So, basically, when ever you see four parts of a collection -- consider breaking it in the middle and then doing brute-force on the two halves.
• So, the above approach sort of make these solutions a little bit like divide and conquer (though the divide and conquer is not recursive).

Here is the solution (in Java):

``` public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;
int[] sum = new int[nums.length];
sum = nums;
for (int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
for (int j = 3; j < nums.length - 3; j++) {
HashSet < Integer > set = new HashSet < > ();
// j is NOT included. So, check 0 till (j-1).
for (int i = 1; i < j - 1; i++) {
if (sum[i - 1] == sum[j - 1] - sum[i])
}

// j is NOT included. So, check (j+1) till (N-1).
for (int k = j + 2; k < nums.length - 1; k++) {
if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))
return true;
}
}
return false;
}
```

### Other Problems

##### Check If Two String Arrays are Equivalent

We can use two pointers and NOT have to construct the string. Check If Two String Arrays are Equivalent: We can use two pointers and NOT have to construct the string.

##### Increasing Triplet Subsequence

Given an unsorted array, return whether an increasing subsequence of length 3 exists or not in the array. We need to find three numbers in sequence (a < b < c). Here we track b and c

Basically, use three pointers. Keep track of first (smallest), second (smallest), and then compare with a[i]. You don't need to keep three variables.

The key idea is that we push first and second to smaller values, if we see one. So, that if we hit the third number, it would compare against the two smallest earlier numbers (the smallest forming a sequence)..

• If you find something smaller (or equal to) than first, then make it first.
• Else, compare with second -- if it is smaller (or equal), then set second to that.
• Else, you have a found a number that is not smaller than first or second. It must be the third. So, return true.

Here is the code (in C):

``` bool increasingTriplet(int* a, int len) {
int i, first, second = INT_MAX;

if (!len) return false;

// first is the smallest of the three.
first = a;
for (i = 1; i < len; i++) {
if (a[i] <= first) {
first = a[i];
} else if (a[i] <= second ) {
second = a[i];
} else {
return true;
}
}
return false;
}
```