Quick Overview

Find unique zero-sum triplets with distinct indices, deterministic ordering, careful duplicate suppression, and explicit time and space analysis.

Find Unique Zero-Sum Triplets

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an integer array, return every distinct triplet of values whose sum is zero. Each triplet must use three different array indices. Return duplicate value-triplets only once. Implement `three_sum(nums: int[]) -> int[][]`. ### Constraints & Assumptions - `0 <= len(nums) <= 3000`; values range from -1,000,000 through 1,000,000. - Sort values within each returned triplet in ascending order. Sort the outer list lexicographically to make the output deterministic. - Equal values may be used when they come from different indices. For example, three zeros require at least three zero elements. - You may reorder the input or sort a copy. Return values, not indices. ### Examples ```text nums = [-1,0,1,2,-1,-4] result = [[-1,-1,2],[-1,0,1]] ``` ```text nums = [0,0,0,0] result = [[0,0,0]] ``` Explain how the algorithm avoids reusing an index and suppresses duplicate triplets. Give its time and auxiliary-space complexity, distinguishing output storage and any sorted copy from the search state. ```hint Make the remaining sum monotone After fixing one value in sorted order, consider how moving either endpoint of the remaining search interval changes the pair sum. ```

Overview: Find unique zero-sum triplets with distinct indices, deterministic ordering, careful duplicate suppression, and explicit time and space analysis.

Read the full Microsoft Software Engineer interview experience this question came from

Given an integer array, return every distinct triplet of values whose sum is zero. Each triplet must use three different array indices. Return duplicate value-triplets only once. Implement `three_sum(nums: int[]) -> int[][]`. ### Constraints & Assumptions - `0 <= len(nums) <= 3000`; values range from -1,000,000 through 1,000,000. - Sort values within each returned triplet in ascending order. Sort the outer list lexicographically to make the output deterministic. - Equal values may be used when they come from different indices. For example, three zeros require at least three zero elements. - You may reorder the input or sort a copy. Return values, not indices. ### Examples ```text nums = [-1,0,1,2,-1,-4] result = [[-1,-1,2],[-1,0,1]] ``` ```text nums = [0,0,0,0] result = [[0,0,0]] ``` Explain how the algorithm avoids reusing an index and suppresses duplicate triplets. Give its time and auxiliary-space complexity, distinguishing output storage and any sorted copy from the search state. ```hint Make the remaining sum monotone After fixing one value in sorted order, consider how moving either endpoint of the remaining search interval changes the pair sum. ```

Constraints

  • 0 <= len(nums) <= 3000.
  • Every input value is an integer from -1,000,000 through 1,000,000 inclusive.
  • Each triplet uses three distinct input indices; equal values require sufficient input multiplicity.
  • Return each value triplet once, internally ascending; sort the outer result lexicographically.
  • Reordering the input or sorting a copy is allowed; return values, not indices.

Examples

Input: ([-1, 0, 1, 2, -1, -4],)

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

Explanation: The source example contains exactly these two distinct triplets, in lexicographic order.

Input: ([0, 0, 0, 0],)

Expected Output: [[0, 0, 0]]

Explanation: Four available indices permit a zero triplet; all choices have the same values.

Hints

  1. Check that each output triplet uses three distinct indices and that both required ordering rules are satisfied.

Loading coding console...

Show the approach

Approach

Sort a copy of the input. Choose each distinct value at index i as the smallest value of a prospective triplet. Search the suffix with left = i + 1 and right = n - 1. When the total is negative, move left rightward. Every pair using the old left and a right no larger than the current right also has a negative total, so none can be an answer. When the total is positive, move right leftward: pairing the old right with any left no smaller than the current left cannot lower that total to zero. On equality, append the three values and skip all remaining copies of both endpoint values. Skip repeated anchors as well. A positive anchor permits stopping because all later values are positive too.

Throughout the search, i < left < right, so every reported triplet uses three distinct positions even when values are equal. The monotonicity arguments discard only impossible pairs. After an equality, a fixed endpoint value requires exactly the matched opposite value, so skipping its duplicates removes no distinct value triplet. Every possible smallest value is considered once; together these facts establish completeness and uniqueness.

Sorted positions make each triplet ascending. Anchors increase between searches; for a fixed anchor, successful left values increase. This produces the required lexicographic outer order without an additional result sort. Inputs shorter than three yield an empty result, and fewer than three zeros cannot produce [0, 0, 0]. The permitted three-value sums lie in [-3,000,000, 3,000,000], which fits Java and C++ int and is represented exactly by JavaScript Number.

Sorting takes O(n log n), followed by O(n) pointer work per anchor, for O(n^2) total time. If t triplets are returned, output storage is O(t). The search uses O(1) state; these references own an O(n) sorted copy, including the C++ by-value parameter. Sorting workspace is library-dependent and bounded by O(n) here, so auxiliary space excluding the result is O(n). An in-place variant can avoid the copy but must still account for its sorting workspace.

Time complexity:
O(n^2), including O(n log n) sorting.
Space complexity:
O(n) auxiliary space for the sorted copy and sorting workspace; O(1) search state and O(t) additional output storage.