NeetCode 150: 3Sum

Table of contents

The Problem

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.

The Approach

The goal is to get ALL (without duplicates) the triplets that add up to 0, which is slightly different when compared to similar problems such as Two Sum which had exactly one solution for each input.

By analysing each triplet, the problem is reduced to Two Sum where the first integer is “locked” & Two Sum is applied on the last two integers.

By sorting, we enable the use of the Two Pointer method. Keeping track of the previous element that was “locked” (& skipping it in subsequent iterations), we also remove the consideration of the same set of triplets originating from this “locked” element.

My Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // Sort the array so that the two-pointer method is possible.
        Arrays.sort(nums);

        // Initialize prev which tracks the previous element & result.
        int prev = Integer.MIN_VALUE;
        Set<List<Integer>> result = new HashSet();

        // If the current element is the same as the previous, continue
        // as its triplets solution has been considered previously.
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != prev) {
                // "Lock" the 1st element & apply twoSum on the other two.
                twoSum(i, nums, result);  
                prev = nums[i];

            } else {
                continue;
            }
        }
        return new ArrayList(result);
    }

    // Two pointer method, where the target = 0 & an addtional constant,
    //  nums[index] (i.e. the "locked" element), is part of currentSum.
    private void twoSum(int index, int[] nums, Set<List<Integer>> result) {
        int l = index + 1;
        int r = nums.length - 1;

        while (l < r) {
            int currentSum = nums[index] + nums[l] + nums[r];

            if (currentSum == 0) {
                List<Integer> triplets = new ArrayList();
                triplets.add(nums[index]);
                triplets.add(nums[l]);
                triplets.add(nums[r]);
                result.add(triplets);
                // Do not return as all triplets must be considered.
                l++;

            } else if (currentSum < 0) {
                l++;

            } else {
                r--;
            }
        }
    }
}

Firstly we sort the array to enable the use of Two Pointers method for twoSum(). We then initialize:

• int prev: Keeps track of the previous element that was “locked” & twoSum() was applied on.
• Set<List<Integer>> result: A Set of Lists. The Set prevents duplicate entries for the same “locked” element.

We then loop over all the elements in nums, applying twoSum() on if it was not considered before (current element != previous element).

We then convert result to List<List<Integer>> to match the return type of the method signature.