Problem

Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k.

Example

Example 1:

Input: nums= [3,1,7,4,5,9,10] , k = 21;
Output:[[7, 4, 10]]

Follow up

What if Duplicates Not Allowed?

Solution

Method 1 - Brute Force

Use 3 nested loops and find the 3 elements which sum to k.

Code

Java
private static List<List<Integer>> threeSum(int[] nums, int target) {
    List < Integer[] > result = new ArrayList < > ();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] == target) {
                    result.add(List.of(
                        nums[i], nums[j], nums[k]
                    ));
                }
            }
        }
    }
    return result;
}

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(1)

Method 2 - Sorting and Two Pointer Approach - Outputs duplicate triplets❌

  • Sort the array.
  • Use the other loop to fix the one element at a time
  • Now problem is reduced to “Find a pair of numbers from an array whose sum equals k”

Code

Java
private List<List<Integer> threeSum(int[] nums, int target) {
    List < Integer[] > result = new ArrayList < > ();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[i] + nums[left] + nums[right] == target) {
                result.add(List.of(nums[i], nums[left], nums[right]));
                left++;
                right--;
            } else if (nums[i] + nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 3 - Sorting and Two Pointer Approach - Fixes Duplicate Issue 🏆

If we need to fix the duplicate issue, easiest solution is sorting. Look at 2Sum 2 – Input array is sorted and 3Sum0 - Find three elements in an array that sum to a zero.

public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> ans = new ArrayList<List<Integer>>();
	Arrays.sort(nums);
	for (int i = 0; i < nums.length; i++) {
		if (i != 0 && nums[i] == nums[i - 1]) {
			continue;
		}
		int left = i + 1, right = nums.length - 1;
		while (left < right) {
			int currSum = nums[i] + nums[left] + nums[right];
			if (currSum > target) {
				right--;
			} else if (currSum < target) {
				left++;
			} else {
				List<Integer> triplet = List.of(nums[i], nums[left], nums[right]);
				ans.add(triplet);
				left++;
				right--;
				while (left < right && nums[left] == nums[left - 1]) {
					left++;
				}
				while (left < right && nums[right] == nums[right + 1]) {
					right--;
				}
			}
		}
	}
	return ans;
}

Method 3 - Use Hashing 🏆

  • Use the other loop to fix the one element at a time.
  • Now required_sum is (with two elements) = k-fixed element.
  • Create a HashSet, Iterate through rest of the array.
  • For current_element, remain_value = required_sum – current_element.
  • Check if remain_value in the HashSet, we have found our triplets else add current_element to the hashset.

Time Complexity: O(n^2)

Code

Java
private List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList <> ();
    for (int i = 0; i < nums.length; i++) {
        int currentTarget = target - nums[i];
        // now this reduces to two sum
        Set < Integer > existingNums = new HashSet <> ();
        for (int j = i + 1; j < nums.length; j++) {
            if (existingNums.contains(currentTarget - nums[j])) {
                result.add(List.of(nums[i], nums[j], currentTarget - nums[j]));
            } else {
                existingNums.add(nums[j]);
            }
        }
    }
    return result;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)