• ← Previous
• Next →

Let us go through some of the 2-Sum related problems that are solved using 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:

• Have two pointers (array indices): one at start (index 0) and another at end (index arr.length-1).
• Check the sum of (arr[start]+ arr[end]).
  • If the sum is greater than K, then we need to go lower. We do that by decrementing end since we want a lower value for sum and clearly, arr[end] is lower (since the array is sorted).
  • If the sum is less than K, then we need to go higher. We do that by incrementing start since we want a higher value for sum and clearly, arr[start] is higher (since the array is sorted).
  • If the sum is equal to K, then you have found your match!
• Else, keep doing this till start < end. If we did not find any match, then such two elements do not exist.

Here is the solution that returns an array of two elements, if two elements exist. Else, it returns an empty array.

 int[] two_sum_solution(int[] arr, int K) {
     int start = 0, end = arr.length -1;

     while (start < end) {
         int sum = arr[start] + arr[end];
         if (sum > K) end--;
         else if (sum < K) start++;
         else { // sum must be equal to K
            return new int[] {arr[start], arr[end]};
         }
     }

     // Solution does not exist. Return an empty error
     return new int[] {};
 }

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

Problem: Valid Triangle Number

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:

• 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.

Problem: Container With Most Water

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.

• 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).

Problem: Max Number of K-Sum Pairs

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;
 }

Problem: 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:

Problem: 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.

Problem: 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.

• ← Previous
• Next →