Solution: 3Sum

Let's solve the 3Sum problem using the Two Pointers pattern.

We'll cover the following

Statement

Given an array of integers, nums, and an integer value, target, determine if there are any three integers in nums whose sum is equal to the target, that is, nums[i] + nums[j] + nums[k] == target. Return TRUE if three such integers exist in the array. Otherwise, return FALSE.

Note: A valid triplet consists of elements with distinct indexes. This means, for the triplet nums[i], nums[j], and nums[k], i ≠\not = j, i ≠\not = k and j ≠\not = k.

Constraints:

  • 33 ≤\leq nums.length ≤\leq 500500
  • −103-10^3 ≤\leq nums[i] ≤\leq 10310^3
  • −103-10^3 ≤\leq target ≤\leq 10310^3

Solution

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

Naive approach

The naive approach to solving this problem is to use three nested loops. Each nested loop starts at the index greater than its parent loop. For example, if we use the iterators i, j, and k in the loops, j will start from i + 1, and k will start from j + 1. This approach will check all the possible triplets to see if they sum up to the required target value.

We have the required solution, but at what cost? Since we’re using three nested loops, the overall time complexity for this solution is O(n3)O(n^3). However, we aren’t using any extra space to get to the final output, so the space complexity is O(1)O(1).

Optimized approach using two pointers

The essence of this algorithm is in its smart use of the two pointers, focused on identifying three elements that achieve a specific target sum together. It starts by sorting the array, which facilitates the search process. One element is fixed as a reference point. The two pointers are set at one element ahead of the array’s fixed reference point and end of the array, respectively. Then, the algorithm dynamically adjusts the two pointers based on their combined sum’s closeness to the target. If the combined sum is less than the target, the algorithm moves the lower pointer to increase the sum. If the sum is greater, it moves the upper pointer down to decrease it. This step-by-step adjustment helps simplify the search, minimizing the potential combinations.

Now, let’s look at the workflow of the implementation of the algorithm:

First, we sort the input array, nums, in ascending order. This is because traversing an unsorted array would lead to a bad time complexity. If the input array is sorted, we can easily decide, depending on the sum of the current triplet, whether to move the low pointer toward the end, or, the high pointer toward the start. Next, we iterate over the elements in nums using the index i, where i << nums.length - 2. Against each nums[i], we find the other two integers that complete the triplet whose sum equals the target value, that is, nums[i] + nums[low] + nums[high] == target. We do this by traversing nums with the low and high pointers. In each iteration, the traversal starts with the low pointer being at nums[i+1] and the high pointer at the last element of nums. Then, depending on the current sum value, we move these pointers as follows:

  • If the sum of the triplet is equal to the target, we return TRUE. Otherwise, we continue.

  • If the sum of the triplet is less than the target, we move the low pointer forward, that is, toward the end. The aim is to increase the value of the sum so that it gets closer or equal to the target value.

  • If the sum of the triplet is greater than the target, we move the high pointer toward the start. The aim is to reduce the value of the sum so that it gets closer or equal to the target value.

We repeat this for each iteration until we get the required triplet.

Note: As per the problem statement, each number in a triplet, nums[i], nums[low], and nums[high], should be a different element of nums, so i can’t be equal to low or high, and low can’t be equal to high. Therefore, we keep the loop restricted to nums.length - 2.

Now, let’s look at the following illustration to get a better understanding of the solution:

Press + to interact
canvasAnimation-image
1 of 8

Let’s look at the code for this solution below:

class SumOfThree {
	public static boolean findSumOfThree(int nums[], int target) {
		Arrays.sort(nums);
		int low, high, triples;
		for (int i = 0; i < nums.length - 2; i++) {
			low = i + 1;
			high = nums.length - 1;
			while (low < high) {
				triples = nums[i] + nums[low] + nums[high];
				if (triples == target) {
					return true;
				}
				else if (triples < target) {
					low++;
				} 
				else {
					high--;
				}
			}
		}
		return false;
	}
	// Driver code
	public static void main(String[] args) {
		int[][] numsList = {{3, 7, 1, 2, 8, 4, 5},
                       {-1, 2, 1, -4, 5, -3},
                       {2, 3, 4, 1, 7, 9},
                       {1, -1, 0},
                       {2, 4, 2, 7, 6, 3, 1}};
					   
		int[] testList = {10, 7, 20, -1, 8};
		
		for (int i=0; i<testList.length; i++) {
			System.out.print(i+1);
			System.out.println(".\tInput array: " + Arrays.toString(numsList[i]));
			
			if (findSumOfThree(numsList[i], testList[i])) {
			System.out.println("\tSum for " + testList[i] + " exists ");
			} else {
			System.out.println("\tSum for " + testList[i] + " does not exist ");
			}
			
			System.out.println(new String(new char[100]).replace('\0', '-'));
		}
	}
}
3Sum

Solution summary

First, sort the array in ascending order. To find a triplet whose sum is equal to the target value, loop through the entire array. In each iteration:

  1. Store the current array element and set up two pointers (low and high) to find the other two elements that complete the required triplet.

    • The low pointer is set to the current loop’s index + 1.

    • The high is set to the last index of the array.

  2. Calculate the sum of array elements pointed to by the current loop’s index and the low and high pointers.

  3. If the sum is equal to target, return TRUE.

  4. If the sum is less than target, move the low pointer forward.

  5. If the sum is greater than target, move the high pointer backward.

Repeat until the loop has processed the entire array. If, after processing the entire array, we don’t find any triplet that matches our requirement, we return FALSE.

Time complexity

In the solution above, sorting the array takes O(nlog(n))O(nlog(n)) and the nested loop takes O(n2)O(n^2) to find the triplet. Here, nn is the number of elements in the input array. Therefore, the total time complexity of this solution is O(nlog(n)+n2)O(nlog(n) + n^2), which simplifies to O(n2)O(n^2).

Space complexity

The space complexity of this solution is O(1)O(1).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.