Unique Zero-Sum Triplets

Interview Problem Intermediate Medium Opposite-direction Pointers Two Pointers Array

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.threeSum(nums). Return each distinct three-value combination summing to zero. Indices within a triplet must be distinct; output group and value order do not matter.

Starter code

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

Test cases

duplicates-and-two-answers

{
  "args": [
    [
      -1,
      0,
      1,
      2,
      -1,
      -4
    ]
  ]
}

Expected: [[-1,-1,2],[-1,0,1]]

Wizard outline

Step 1: Initialize Solution.threeSum
Replace the empty starter with the first real state owned by Solution.threeSum. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the No Answer case
Complete the readable core algorithm for one representative Interview case. Sort once, reduce each anchor to a two-pointer search, and skip duplicates at every decision boundary.
Step 4: Harden the Duplicates And Two Answers boundary
Repair the reviewed boundary and pass the complete submission contract. For each distinct anchor, sorted order lets pointer moves eliminate sums that are respectively too small or too large; every zero sum is emitted once because equal anchors and matched pointer values are skipped.

Footguns and prerequisites

Skipping duplicate anchors but not duplicate pointer values can still emit repeated triplets.
arrays strings two pointers sliding window

Reviewed references

Practice prerequisites

Discard Pairs with Two Pointers(opens in a new tab)
Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing three sum as a complete Interview Problem.

Recommended approach and implementation

Sort, choose each distinct anchor, then move two pointers according to the three-value sum while skipping equal neighbors after a match.

Why it works: For each distinct anchor, sorted order lets pointer moves eliminate sums that are respectively too small or too large; every zero sum is emitted once because equal anchors and matched pointer values are skipped.

class Solution:
    def threeSum(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        nums.sort()
        result = []
        for index in range(len(nums) - 2):
            if index > 0 and nums[index] == nums[index - 1]:
                continue
            left = index + 1
            right = len(nums) - 1
            while left < right:
                total = nums[index] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[index], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
        return result

Similar exercises

Maximum Container Area(opens in a new tab)