Three Sum
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that:
i != j,i != k, andj != knums[i] + nums[j] + nums[k] == 0
The solution set must not contain duplicate triplets.
Examples
nums = [-1, 0, 1, 2, -1, -4] output: [[-1, -1, 2], [-1, 0, 1]] explanation: The triplets `[-1, -1, 2]` and `[-1, 0, 1]` are the only unique combinations that sum to zero. nums = [1, 2, -2, -1] output: [] explanation: There are no three numbers in the array that add up to zero. nums = [-2, 0, 1, 1, -2, -1, 0, 2, -1] output: [[-2, 0, 2], [-2, 1, 1], [-1, -1, 2], [-1, 0, 1]] explanation: The array contains four unique triplets that sum to zero.
Our solution processes the input array by first sorting the array and then using a two-pointer approach to find unique triplets that sum to zero. The algorithm iterates through the sorted array and, for each element nums[i], it sets two pointers: one starting right after i (left = i + 1) and one at the end of the array (right = nums.length - 1).
We calculate the sum of the current element and the two pointers: sum = nums[i] + nums[left] + nums[right].
- If the sum is zero, we have found a valid triplet, which we add to the result list.
- If the sum is less than zero, we increment the
leftpointer to increase the sum. - If the sum is greater than zero, we decrement the
rightpointer to decrease the sum. To avoid processing duplicate triplets, we skip over duplicate elements for both the current element (nums[i]) and the two pointers (leftandright).
If the loop completes, we return the list of unique triplets.
The use of sorting ensures that duplicates are easily avoided and the two-pointer approach allows for efficient finding of the triplets.
from typing import List
def three_sum(nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
length = len(nums)
for i in range(length - 2):
# Skip duplicate elements to avoid duplicate triplets
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, length - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicate elements for left pointer
while left < right and nums[left] == nums[left + 1]:
left += 1
# Skip duplicate elements for right pointer
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return resultTime Complexity: The solution has a time complexity of O(n^2), where n is the number of elements in the array. Sorting the array takes O(n log n), and the two-pointer approach iterates over the array in O(n^2) time.
Space Complexity: The solution uses O(1) extra space for the two-pointer technique (excluding the input and output space). Sorting the array is done in-place, so no additional space is required apart from the result storage.
Watch our mock interview with Angie and Andrea Dias (Software Engineer, Modern Health) as he solves the 3 Sum Algorithm Problem.
import java.util.*; class Solution { public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int i = 0;i<n- 1;i++){ if(i > 0 && nums[i] == nums[i - 1]){ continue; } int j = i + 1; int k = n - 1; while(j < k){ int sum = nums[i] + nums[j] + nums[k]; if(sum == 0){ List<Integer> temp = new ArrayList<>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); ans.add(temp); j++; k--; while(j < k && nums[j] == nums[j - 1]){ j++; } while(j < k && nums[k] == nums[k + 1]){ k--; } } else if(sum > 0){ k--; } else{ j++; } } } return ans; } public static void main(String[] args) { // debug your code below int[] arr = {-1, 0, 1, 2, -1, -4}; System.out.println(threeSum(arr)); } }