Let us go through some of the common problems related to two-pointer technique.
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:
There is a lot of variation of the basic 2-Sum. We list some of them below.
Problem: https://leetcode.com/problems/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:
Problem: https://leetcode.com/problems/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.
Problem: https://leetcode.com/problems/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;
}
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:
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.
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.
Problem: https://leetcode.com/problems/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.
Problem: https://leetcode.com/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:
Problem: https://leetcode.com/problems/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.
Problem: https://leetcode.com/problems/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:
Problem: https://leetcode.com/problems/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.
Problem: https://leetcode.com/problems/4sum/
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.
There are some cool optimizations that focus on target being less than being the smallest *K and target being higher than the highest * K:
Problem: https://leetcode.com/problems/4sum-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.
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.
Problem: https://leetcode.com/problems/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.
Here is the solution (in Java):
public boolean splitArray(int[] nums) {
if (nums.length < 7)
return false;
int[] sum = new int[nums.length];
sum[0] = nums[0];
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])
set.add(sum[i - 1]);
}
// 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;
}
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.
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)..
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[0];
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;
}