Coding

3 Sum

Asked at

Acko

HashedIn

Sprinklr

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array nums. Return all triplets such that:

i != j, i != k, and j != k
nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets. One element can be a part of multiple triplets. The output and the triplets can be returned in any order.

Input: nums = [2, -2, 0, 3, -3, 5] Output: [[-2, 0, 2], [-3, -2, 5], [-3, 0, 3]] Explanation: nums[1] + nums[2] + nums[0] = 0 nums[4] + nums[1] + nums[5] = 0 nums[4] + nums[2] + nums[3] = 0

Input: nums = [2, -1, -1, 3, -1] Output: [[-1, -1, 2]] Explanation: nums[1] + nums[2] + nums[0] = 0 Note that we have used two -1s as they are separate elements with different indexes But we have not used the -1 at index 4 as that would create a duplicate triplet

Input: nums = [8, -6, 5, 4] (Give answer with the output and triplets sorted in ascending order)

1 <= nums.length <= 3000
-104 <= nums[i] <= 104

cpp

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
    }
};

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
    }
}

python

class Solution:
    def threeSum(self, nums: list) -> list[list]:

javascript

class Solution {
    threeSum(nums) {

    }
}

csharp

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        
    }
}

func threeSum(nums []int) [][]int {

}

Stuck? Show a way to structure it+

01Sort the values and fix each possible first element once.
02Search the remaining suffix with left and right pointers.
03After finding a triplet, skip duplicate values at all three positions.
04Use sorted-order bounds to stop early when no later triplet can sum to zero.

Reference answer

Sort the array. Iterate an index i as the first triplet element, skipping it when it equals the previous value. If nums[i] is positive, stop because every later value is at least as large. Set left = i + 1 and right = n - 1. Compare the sum with zero: move left rightward when the sum is too small, move right leftward when it is too large, and record the triplet when equal. After recording, move both pointers and skip repeated values so the same value triplet is not emitted again. Sorting costs O(n log n) and the nested scan costs O(n squared), which dominates. Extra space is O(1) apart from sorting and the output. Deduplicate by values, not indices, because different index combinations may represent the same required triplet.

Then expect these follow-ups

How would you generalize this to k-sum?
Tests: recursion pattern
Why can the scan stop when the fixed value is positive?
Tests: sorted reasoning

Hiring now

Sprinklr has 53 open roles right now

Also hiring: Acko

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Sales Development Representative (Large Enterprise), ASEAN and North Asia
Singapore
Program Manager Lead - Community
South Korea - Seoul
Sr. Customer Success Manager
Japan - Tokyo

Or practice this question first

Next question