3 Sum

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

Solution

Nobody could possibly derive this during an interview.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        var ans = new ArrayList<List<Integer>>();
        for (var i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            twoSum(nums, i, ans);
        }
        return ans;
    }

    public void twoSum(int[] nums, int i, List<List<Integer>> ans) {
        var li = i + 1;
        var ri = nums.length - 1;
        while (li < ri) {
            var sum = nums[li] + nums[ri] + nums[i];
            if (sum == 0) {
                ans.add(List.of(nums[i], nums[li], nums[ri]));
                li += 1;
                ri -= 1;
                while (li < ri && nums[li] == nums[li - 1]) {
                    li += 1;
                }
            } else if (sum < 0) {
                li += 1;
            } else {
                ri -= 1;
            }
        }
    }
}

Recent posts from blogs that I like

An Introduction to Google’s Approach to AI Agent Security

via Simon Willison

Notes on Cramer's rule

Cramer's rule is a clever solution to the classical system of linear equations Ax=b: \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\] Usi...

via Eli Bendersky

Brandjes: Paintings as witnesses to fires 1640-1813

Dramatic paintings of towns and cities on fire, usually at night, were popular during the Dutch Golden Age, and known as brandjes. Examples to well into the 19th century.

via The Eclectic Light Company