Scale Engineer

3Sum

Med
#0015Time: O(n^3)Space: O(k), where k is the number of unique triplets. In the worst case, this can be O(n^2).64 companies
Patterns
Two Pointers
Algorithms
Sorting
Data structures
Array
Companies
AMDAccentureAdobeAgoda

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

    1. Initialize an empty HashSet called resultSet to store unique triplets.
    1. Use three nested loops to iterate through all unique combinations of indices (i, j, k).
    1. For each combination, check if nums[i] + nums[j] + nums[k] == 0.
    1. If the sum is zero, create a list with these three numbers.
    1. Sort the list to create a canonical representation of the triplet.
    1. Add the sorted list to the resultSet.
    1. After the loops complete, convert the resultSet to an ArrayList and return it.

Walkthrough

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.

import java.util.*; class Solution {    public List<List<Integer>> threeSum(int[] nums) {        Set<List<Integer>> 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<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);                        Collections.sort(triplet);                        resultSet.add(triplet);                    }                }            }        }        return new ArrayList<>(resultSet);    }}

Complexity

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).

Trade-offs

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.

Solutions

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;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem