Find a triplet in an array with a given sum.
Medium
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.
Time 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.
Related questions
Find quadruplets in an array with a given sum.Find a sorted triplet in a given array.Given an array, find the two sum.Related courses
