3 Sum

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.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        var n = nums.length;
        Set<List<Integer>> out = new HashSet<>();
        for (int i = 0; i < n; i ++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate
            var set = new HashSet<Integer>();
            for (int j = i + 1; j < n; j ++) {
                var comp = 0 - (nums[i] + nums[j]);
                if (set.contains(comp)) {
                    out.add(Arrays.asList(comp, nums[i], nums[j]));
                }
                set.add(nums[j]);
            } 
        }
        return new ArrayList<>(out);
    }
}

Time Complexity: O(NlogN)+O(N2), as The pointer i, is running for approximately N times. And both the pointers j and k combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N2).

Space Complexity: O(no. of quadruplets), This space is only used to store the answer. We are not using any extra space to solve this problem. So, from that perspective, space complexity can be written as O(1).