15. 3Sum - Leetcode Solution

LeetCode problem Solution code

Solution: HashMap

  1. Create a Hash Map

    • We initialize an empty dictionary h to map each number to its index.
    • This allows for O(1) lookups when searching for a complement number.
    • h[num] = i for each index i and value num in nums.

  2. Use a Set to Avoid Duplicates

    • We initialize a set s to store unique triplets.
    • Sets automatically eliminate duplicate entries.

  3. Iterate Over All Pairs of Elements

    • We use two nested loops with indices i and j to select every unique pair of elements from nums.

  4. Compute the Desired Complement

    • For each pair (nums[i], nums[j]), compute the third number desired = -nums[i] - nums[j].
    • We're trying to find a third number that makes the sum of all three equal to 0.

  5. Check If the Third Number Exists

    • Check if desired exists in the hash map and is not the same as i or j.
    • This ensures that the same element is not reused.
    • If found, add the triplet to the set after sorting it to avoid permutations of the same values.

  6. Return the Set

    • After all iterations, return the set s containing all unique triplets that sum to 0.

  7. Time and Space Complexity

    • Time Complexity: O(n²) — Two nested loops over the array, each taking O(n).
    • Space Complexity: O(n) — Due to the hash map and set.

Code Solution (HashMap)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        h = {}
        n = len(nums)
        s = set()

        for i, num in enumerate(nums):
            h[num] = i

        for i in range(n):
            for j in range(i + 1, n):
                desired = -nums[i] - nums[j]
                if desired in h and h[desired] != i and h[desired] != j:
                    s.add(tuple(sorted([nums[i], nums[j], desired])))

        return s

# Time Complexity: O(n^2)
# Space Complexity: O(n)


#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> indexMap;
        set<vector<int>> result;
        int n = nums.size();

        // Build the index map
        for (int i = 0; i < n; ++i) {
            indexMap[nums[i]] = i;
        }

        // Iterate over each pair
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int desired = -nums[i] - nums[j];
                if (indexMap.find(desired) != indexMap.end() &&
                    indexMap[desired] != i && indexMap[desired] != j) {
                    vector<int> triplet = {nums[i], nums[j], desired};
                    sort(triplet.begin(), triplet.end());
                    result.insert(triplet);
                }
            }
        }

        return vector<vector<int>>(result.begin(), result.end());
    }
};

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        Map<Integer, Integer> indexMap = new HashMap<>();
        int n = nums.length;

        // Build the index map
        for (int i = 0; i < n; i++) {
            indexMap.put(nums[i], i);
        }

        // Iterate over each pair
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int desired = -nums[i] - nums[j];
                if (indexMap.containsKey(desired) && indexMap.get(desired) != i && indexMap.get(desired) != j) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], desired);
                    Collections.sort(triplet);
                    result.add(triplet);
                }
            }
        }

        return new ArrayList<>(result);
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const indexMap = new Map();
    const result = new Set();
    const n = nums.length;

    // Build the index map
    for (let i = 0; i < n; i++) {
        indexMap.set(nums[i], i);
    }

    // Iterate over each pair
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const desired = -nums[i] - nums[j];
            if (indexMap.has(desired) && indexMap.get(desired) !== i && indexMap.get(desired) !== j) {
                const triplet = [nums[i], nums[j], desired].sort((a, b) => a - b);
                result.add(triplet.toString());
            }
        }
    }

    return Array.from(result, str => str.split(',').map(Number));
};

💡 Optimal Solution (Preferred): Two Pointers

  1. Sort the Array
    • Sorting helps simplify duplicate checking and allows use of the two-pointer technique.
    • nums.sort()
  2. Iterate Through the Array
    • Loop through the array with index i from 0 to n - 1.
    • For each index, treat nums[i] as the first element of the triplet.
  3. Break Early If Current Number Is Positive
    • If nums[i] > 0, break the loop since the array is sorted and no triplet can sum to 0.
  4. Skip Duplicate Elements
    • If nums[i] is the same as nums[i - 1], skip it to avoid duplicate triplets.
  5. Use Two Pointers to Find Remaining Two Elements
    • Initialize two pointers: lo = i + 1 and hi = n - 1.
    • While lo < hi, compute the sum of nums[i] + nums[lo] + nums[hi].
  6. Check the Sum
    • If the sum is 0:
      • Add the triplet to the result list.
      • Move both lo and hi pointers inward.
      • Skip any duplicate values using while loops.
    • If the sum is less than 0, increment lo.
    • If the sum is greater than 0, decrement hi.
  7. Return the Result
    • After the loop ends, return the answer list containing all unique triplets.
  8. Time and Space Complexity
    • Time: O(n²) – Outer loop runs in O(n), inner two-pointer loop in O(n).
    • Space: O(n) – Excluding the result, the space is constant, but output may take O(n) in the worst case.

Code Solution (Two Pointers)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        answer = []
        for i in range(n):
            if nums[i] > 0:
                break
            elif i > 0 and nums[i] == nums[i-1]:
                continue
            lo, hi = i+1, n-1
            while lo < hi:
                summ = nums[i] + nums[lo] + nums[hi]
                if summ == 0:
                    answer.append([nums[i], nums[lo], nums[hi]])
                    lo, hi = lo+1, hi-1
                    while lo < hi and nums[lo] == nums[lo-1]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi+1]:
                        hi -= 1
                elif summ < 0:
                    lo += 1
                else:
                    hi -= 1
        
        return answer
        # Time: O(n^2)
        # Space: O(n) (Excluding the output)

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> answer;

        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == 0) {
                    answer.push_back({nums[i], nums[lo], nums[hi]});
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                } else if (sum < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return answer;
    }
};


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1, hi = n - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == 0) {
                    answer.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                } else if (sum < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return answer;
    }
}

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let answer = [];

    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            break;
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let lo = i + 1, hi = n - 1;
        while (lo < hi) {
            let sum = nums[i] + nums[lo] + nums[hi];
            if (sum === 0) {
                answer.push([nums[i], nums[lo], nums[hi]]);
                lo++;
                hi--;
                while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
                while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
            } else if (sum < 0) {
                lo++;
            } else {
                hi--;
            }
        }
    }

    return answer;
};

Detailed Explanation

Understanding the Problem: 3Sum

The “3Sum” problem presents a common computational challenge: finding all unique triplets in an array of integers such that their sum equals zero. Given an input array nums, the goal is to identify all sets of three elements (a, b, c) where a + b + c = 0, with each triplet returned in non-descending order and without duplication.

Consider the input [-1, 0, 1, 2, -1, -4]. A valid output would be [[-1, -1, 2], [-1, 0, 1]]. While there are several possible combinations of three numbers, only these two sum to zero and are unique in terms of value composition. The duplicates and permutations such as [0, -1, 1] are not allowed in the final result.

This problem blends combinatorics with efficiency constraints and is best solved with a well-thought-out algorithm. The naive brute-force approach is intuitive but inefficient, making this a great opportunity to practice optimizing solutions through sorting, early pruning, and the two-pointer technique.

Why This Problem Matters

3Sum is often considered a rite of passage for software engineers preparing for technical interviews. While the problem itself may appear simple at first glance, crafting an optimal solution requires balancing correctness with efficiency. It demands a deep understanding of array traversal, pointer manipulation, and duplicate avoidance — all under time and space constraints that make brute-force methods infeasible in large-scale scenarios.

Beyond the realm of interviews, 3Sum teaches foundational strategies used in many other algorithmic problems, such as 4Sum, kSum, and variants of subset or combination sums. It’s also a subtle introduction to constraint satisfaction — a key concept in more advanced computational fields like dynamic programming, backtracking, and search algorithms.

Initial Approach: Brute Force

The most direct way to solve the 3Sum problem is by using three nested loops to consider every possible combination of three distinct elements. For each such triplet, we check whether the sum of the numbers is zero. If so, we store it in a result set, ensuring that duplicates are filtered out either via sorting or using a hash-based set.

While this method is conceptually simple, it performs poorly on large inputs. With three levels of iteration, the time complexity is O(n³), making it impractical for arrays with more than a few hundred elements. Additionally, the overhead required to eliminate duplicate triplets further degrades performance and complicates implementation. Thus, we seek a more efficient strategy.

Optimal Strategy: Sorting and Two Pointers

To optimize the solution, we first observe that sorting the array allows us to use a two-pointer approach for the inner search, reducing time complexity dramatically. The overall strategy is to fix one number and find the other two such that their sum equals the negative of the fixed number.

By sorting the array, we gain the ability to efficiently skip duplicates, ensure non-descending order, and perform binary-like traversal through pointer narrowing. This transformation turns a triple nested loop into a single outer loop with a linear inner loop — a common and powerful optimization pattern.

Step-by-Step Breakdown:

  1. Sort the input array nums in ascending order.
  2. Iterate over the array with index i from 0 to nums.length - 3.
  3. For each nums[i], skip it if it's the same as the previous number to avoid duplicates.
  4. Initialize two pointers: left = i + 1 and right = nums.length - 1.
  5. While left < right:
    • Compute the sum: total = nums[i] + nums[left] + nums[right].
    • If total == 0, record the triplet, then increment left and decrement right, skipping duplicates.
    • If total < 0, increment left to increase the sum.
    • If total > 0, decrement right to decrease the sum.

This method ensures that each triplet is checked only once and that no duplicates enter the final output. Since each element is touched at most once per outer iteration, the time complexity is reduced to O(n²).

Example Walkthrough

Let's walk through the example input [-1, 0, 1, 2, -1, -4]. First, we sort the array: [-4, -1, -1, 0, 1, 2].

Starting at i = 0 with nums[i] = -4, we set left = 1 and right = 5. The sum is -4 + (-1) + 2 = -3, which is too low. We move left forward. We continue this process until no zero-sum triplet is found for this index.

At i = 1 with nums[i] = -1, left = 2, right = 5. We find that -1 + (-1) + 2 = 0, which is valid. We store [-1, -1, 2]. After skipping duplicates, we then find [-1, 0, 1] as the next valid triplet. We continue until all positions have been scanned.

The final result is [[-1, -1, 2], [-1, 0, 1]].

Time and Space Complexity

The dominant factor in this algorithm is the nested loop formed by the outer index i and the two-pointer scan inside. Since the array is scanned once and the pointers traverse it linearly per iteration, the overall time complexity is O(n²).

The space complexity is O(1) if we disregard the space used to store the output triplets. We only use a few variables for indexing and no additional data structures beyond the result list.

Edge Cases to Consider

  • Arrays with fewer than three elements should immediately return an empty result.
  • If all numbers are positive or all are negative, no valid triplet will sum to zero.
  • Cases like [0, 0, 0, 0] must return only one triplet [0, 0, 0], even though there are many duplicates.
  • Properly skipping duplicates after finding a valid triplet is essential to avoiding repeat results.

Conclusion

The 3Sum problem elegantly demonstrates the evolution of problem-solving approaches — from naive brute force to optimized two-pointer strategies. It is a classic example of how sorting and constraint-based iteration can simplify a seemingly combinatorial problem.

By mastering this problem, developers gain confidence in dealing with variations like 4Sum and kSum, and deepen their understanding of how space and time complexity shape the choice of algorithm. Efficient use of sorting and pointer narrowing, paired with careful handling of edge cases, is the essence of algorithmic problem-solving.

NEW!Need help landing software roles? 💡