# 3Sum **Difficulty:** MEDIUM [External](https://leetcode.com/problems/3sum) Canonical: https://scaleengineer.com/dsa/problems/3sum **Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers) **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array **Companies:** [AMD](https://scaleengineer.com/companies/amd), [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Altimetrik](https://scaleengineer.com/companies/altimetrik), [Amazon](https://scaleengineer.com/companies/amazon), [American Express](https://scaleengineer.com/companies/american-express), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Barclays](https://scaleengineer.com/companies/barclays), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cadence](https://scaleengineer.com/companies/cadence), [Careem](https://scaleengineer.com/companies/careem), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Docusign](https://scaleengineer.com/companies/docusign), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [HCL](https://scaleengineer.com/companies/hcl), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Turing](https://scaleengineer.com/companies/turing), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [HashedIn](https://scaleengineer.com/companies/hashedin), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Warnermedia](https://scaleengineer.com/companies/warnermedia), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Bosch](https://scaleengineer.com/companies/bosch), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Dream11](https://scaleengineer.com/companies/dream11), [Gojek](https://scaleengineer.com/companies/gojek), [Rakuten](https://scaleengineer.com/companies/rakuten), [Trexquant](https://scaleengineer.com/companies/trexquant), [Vimeo](https://scaleengineer.com/companies/vimeo), [Works Applications](https://scaleengineer.com/companies/works-applications), [Zomato](https://scaleengineer.com/companies/zomato), [smartnews](https://scaleengineer.com/companies/smartnews) --- ## Problem Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`. Notice that the solution set must not contain duplicate triplets. **Example 1:** **Input:** nums = [-1,0,1,2,-1,-4] **Output:** [[-1,-1,2],[-1,0,1]] **Explanation:** nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. **Example 2:** **Input:** nums = [0,1,1] **Output:** [] **Explanation:** The only possible triplet does not sum up to 0. **Example 3:** **Input:** nums = [0,0,0] **Output:** [[0,0,0]] **Explanation:** The only possible triplet sums up to 0. **Constraints:** * `3 <= nums.length <= 3000` * `-105 <= nums[i] <= 105` # Approaches ## Brute Force with Triple Nested Loops This approach iterates through every possible combination of three numbers in the array to check if their sum is zero. To handle duplicate triplets, the found triplets are sorted and stored in a `Set`. **Time:** O(n^3) · **Space:** O(k), where k is the number of unique triplets. In the worst case, this can be O(n^2). **Pros:** Simple to understand and implement. **Cons:** Very inefficient, with a cubic time complexity.; Will likely result in a 'Time Limit Exceeded' error on most platforms for larger inputs. ### Explanation The most straightforward solution is to check every possible triplet in the array. We can achieve this using three nested loops. The outer loop iterates from `i = 0` to `n-3`, the second loop from `j = i + 1` to `n-2`, and the inner loop from `k = j + 1` to `n-1`. Inside the innermost loop, we check if `nums[i] + nums[j] + nums[k] == 0`. A key challenge is avoiding duplicate triplets in the output. For example, `[-1, 0, 1]` and `[0, 1, -1]` represent the same triplet. To solve this, whenever we find a valid triplet, we sort it to have a canonical representation. Then, we add this sorted triplet to a `HashSet` to automatically filter out duplicates. Finally, we convert the `HashSet` of triplets into a `List` to return. ```java import java.util.*; class Solution { public List> threeSum(int[] nums) { Set> resultSet = new HashSet<>(); int n = nums.length; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] + nums[k] == 0) { List triplet = Arrays.asList(nums[i], nums[j], nums[k]); Collections.sort(triplet); resultSet.add(triplet); } } } } return new ArrayList<>(resultSet); } } ``` ### Algorithm - 1. Initialize an empty `HashSet` called `resultSet` to store unique triplets. - 2. Use three nested loops to iterate through all unique combinations of indices `(i, j, k)`. - 3. For each combination, check if `nums[i] + nums[j] + nums[k] == 0`. - 4. If the sum is zero, create a list with these three numbers. - 5. Sort the list to create a canonical representation of the triplet. - 6. Add the sorted list to the `resultSet`. - 7. After the loops complete, convert the `resultSet` to an `ArrayList` and return it. ## Hash Set Optimization This approach improves upon the brute-force method by reducing one loop. It iterates through the array, fixing one number `nums[i]`, and then tries to find two other numbers that sum up to `-nums[i]`. This '2Sum' subproblem is solved efficiently using a hash set. **Time:** O(n^2) · **Space:** O(n) for the hash set used to solve the 2Sum subproblem. **Pros:** Significantly faster than the brute-force approach.; Relatively easy to reason about by breaking it down into a 2Sum problem. **Cons:** Requires extra space for the hash set.; Can be slightly slower in practice than the two-pointer approach due to hash set overhead. ### Explanation We can optimize the O(n^3) approach to O(n^2) by using a hash set. The idea is to transform the problem into a series of 2Sum problems. We iterate through the array with a single loop, fixing the first element of the potential triplet, `nums[i]`. For each `nums[i]`, the problem becomes: find two numbers in the rest of the array (`nums[i+1]` to `nums[n-1]`) that sum to `target = -nums[i]`. We can solve this 2Sum problem in O(n) time. For each `nums[i]`, we iterate through the rest of the array with a second pointer `j`. We use a `HashSet` to store the numbers we've seen so far in this inner loop. For each `nums[j]`, we calculate the `complement = target - nums[j]`. If the `complement` is already in our hash set, we've found a triplet. To avoid duplicate triplets, we can sort the input array first. This helps in skipping over duplicate values for `nums[i]`. Then we can store the resulting triplets in a `Set` to handle all other duplicate cases. ```java import java.util.*; class Solution { public List> threeSum(int[] nums) { Set> resultSet = new HashSet<>(); if (nums.length < 3) return new ArrayList<>(); Arrays.sort(nums); // Sort to handle duplicates easily for (int i = 0; i < nums.length - 2; i++) { // Skip duplicate elements for the first number if (i > 0 && nums[i] == nums[i-1]) { continue; } Set seen = new HashSet<>(); for (int j = i + 1; j < nums.length; j++) { int complement = -nums[i] - nums[j]; if (seen.contains(complement)) { resultSet.add(Arrays.asList(nums[i], complement, nums[j])); } seen.add(nums[j]); } } return new ArrayList<>(resultSet); } } ``` ### Algorithm - 1. Initialize an empty `HashSet` called `resultSet` to store the unique result triplets. - 2. Sort the input array `nums`. This helps in skipping duplicates. - 3. Iterate through the array with an index `i` from `0` to `n-1`. - 4. To avoid duplicate triplets, if `i > 0` and `nums[i]` is the same as `nums[i-1]`, skip the current iteration. - 5. For each `nums[i]`, create a new `HashSet` called `seen`. - 6. Iterate through the rest of the array with an index `j` from `i+1` to `n-1`. - 7. Calculate the required third number: `complement = -nums[i] - nums[j]`. - 8. If `seen` contains `complement`, a triplet is found. Add `(nums[i], nums[j], complement)` to the `resultSet`. - 9. Add `nums[j]` to the `seen` set. - 10. After the loops, convert the `resultSet` to a `List` and return it. ## Two Pointers Approach This is the most optimal and common approach. It involves sorting the array first and then using a two-pointer technique. For each element `nums[i]`, two pointers (`left` and `right`) are used to scan the rest of the array to find two numbers that sum up to `-nums[i]`. Sorting allows for both efficient scanning and easy handling of duplicates. **Time:** O(n^2). The O(n log n) sorting time is dominated by the O(n^2) two-pointer scan. · **Space:** O(log n) or O(n), depending on the sorting algorithm's implementation. This does not include the space required for the output list. **Pros:** Most efficient time complexity.; Low auxiliary space complexity.; Handles duplicates elegantly without needing an extra data structure like a `HashSet` for the results. **Cons:** Requires modifying the input array by sorting it. If the original order must be preserved, a copy should be made first. ### Explanation This method combines sorting with the two-pointer technique to achieve an efficient O(n^2) solution with minimal space overhead. First, the input array `nums` is sorted in non-decreasing order. This takes O(n log n) time. We then iterate through the array with a for loop, fixing the first element of the triplet, `nums[i]`. For each `nums[i]`, we initialize two pointers: `left = i + 1` and `right = n - 1`. We then move these pointers inward until `left` crosses `right`, searching for a pair `(nums[left], nums[right])` that sums to `target = -nums[i]`. Inside the `while (left < right)` loop, if `nums[left] + nums[right] == target`, we've found a valid triplet. If the sum is less than the target, we increment `left`; if it's greater, we decrement `right`. Duplicate handling is crucial and is handled efficiently by skipping over identical elements for `nums[i]` and for `nums[left]` and `nums[right]` after a triplet is found. ```java import java.util.*; class Solution { public List> threeSum(int[] nums) { List> result = new ArrayList<>(); if (nums == null || nums.length < 3) { return result; } Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { // Skip duplicate elements for the first number if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.length - 1; int target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); // Skip duplicate elements for the second number while (left < right && nums[left] == nums[left + 1]) { left++; } // Skip duplicate elements for the third number while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } else if (sum < target) { left++; } else { // sum > target right--; } } } return result; } } ``` ### Algorithm - 1. Initialize an empty `List` called `result`. - 2. Sort the input array `nums`. - 3. Iterate through the sorted array with an index `i` from `0` to `n-3`. - 4. If `i > 0` and `nums[i] == nums[i-1]`, continue to the next iteration to avoid duplicate first elements. - 5. Initialize two pointers: `left = i + 1` and `right = n - 1`. - 6. Set the `target` sum for the two pointers as `-nums[i]`. - 7. While `left < right`: - a. Calculate `sum = nums[left] + nums[right]`. - b. If `sum == target`, a triplet is found. Add `(nums[i], nums[left], nums[right])` to `result`. - c. After finding a triplet, increment `left` and decrement `right`. Also, skip any subsequent duplicate elements for `left` and `right` to avoid duplicate triplets. - d. If `sum < target`, increment `left` to increase the sum. - e. If `sum > target`, decrement `right` to decrease the sum. - 8. Return the `result` list. # Solutions ### CSharp ```csharp public class Solution { public IList < IList < int >> ThreeSum(int[] nums) { Array.Sort(nums); int n = nums.Length; IList < IList < int >> ans = new List < IList < int >> (); for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int j = i + 1, k = n - 1; while (j < k) { int x = nums[i] + nums[j] + nums[k]; if (x < 0) { ++j; } else if (x > 0) { --k; } else { ans.Add(new List < int > { nums[i], nums[j--], nums[k--] }); while (j < k && nums[j] == nums[j + 1]) { ++j; } while (j < k && nums[k] == nums[k + 1]) { --k; } } } } return ans; } } ``` ### Java ```java class Solution { public List> threeSum(int[] nums) { Arrays.sort(nums); List> ans = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int j = i + 1, k = n - 1; while (j < k) { int x = nums[i] + nums[j] + nums[k]; if (x < 0) { ++j; } else if (x > 0) { --k; } else { ans.add(List.of(nums[i], nums[j++], nums[k--])); while (j < k && nums[j] == nums[j - 1]) { ++j; } while (j < k && nums[k] == nums[k + 1]) { --k; } } } } return ans; } } ``` ### JavaScript ```javascript /** * @param {number[]} nums * @return {number[][]} */ var threeSum = function ( nums ) { const n = nums . length ; nums . sort (( a , b ) => a - b ); const ans = []; for ( let i = 0 ; i < n - 2 && nums [ i ] <= 0 ; ++ i ) { if ( i > 0 && nums [ i ] === nums [ i - 1 ]) { continue ; } let j = i + 1 ; let k = n - 1 ; while ( j < k ) { const x = nums [ i ] + nums [ j ] + nums [ k ]; if ( x < 0 ) { ++ j ; } else if ( x > 0 ) { -- k ; } else { ans . push ([ nums [ i ], nums [ j ++ ], nums [ k -- ]]); while ( j < k && nums [ j ] === nums [ j - 1 ]) { ++ j ; } while ( j < k && nums [ k ] === nums [ k + 1 ]) { -- k ; } } } } return ans ; }; ``` ### CPP ```cpp class Solution { public: vector> threeSum(vector &nums) { sort(nums.begin(), nums.end()); vector> ans; int n = nums.size(); for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) { if (i && nums[i] == nums[i - 1]) { continue; } int j = i + 1, k = n - 1; while (j < k) { int x = nums[i] + nums[j] + nums[k]; if (x < 0) { ++j; } else if (x > 0) { --k; } else { ans.push_back({nums[i], nums[j++], nums[k--]}); while (j < k && nums[j] == nums[j - 1]) { ++j; } while (j < k && nums[k] == nums[k + 1]) { --k; } } } } return ans; } }; ``` ### Python ```python class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums . sort() n = len(nums) ans = [] for i in range(n - 2): if nums[i] > 0: break if i and nums[i] == nums[i - 1]: continue j, k = i + 1, n - 1 while j < k: x = nums[i] + nums[j] + nums[k] if x < 0: j += 1 elif x > 0: k -= 1 else: ans . append([nums[i], nums[j], nums[k]]) j, k = j + 1, k - 1 while j < k and nums[j] == nums[j - 1]: j += 1 while j < k and nums[k] == nums[k + 1]: k -= 1 return ans ```