thesarfo

Reference

Three Sum

Finding all unique triplets summing to zero — three-pointer plus set dedup, hashing to cut a loop, then sort + two pointers with no set needed at all.

views 0

Find all unique triplets summing to zero, no repeated indices, no duplicate triplets. [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]. (LeetCode 15)

Brute force — three pointers, dedupe via a set: generate every triplet, sort each one, and only keep it if its sorted form isn’t already in a Set. O(n³).

Better — hashing to cut one loop: fix i and j, and look up whether the required third value -(nums[i] + nums[j]) has already been seen for this i (tracked in a per-i set). O(n²) time, but still needs sets for both lookup and dedup.

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


        for(int i = 0; i < n; i++){
            Set<Integer> store = new HashSet<>();
            for(int j = i + 1; j < n; j++){
                int third = -(nums[i] + nums[j]);
                if(store.contains(third)){
                    List<Integer> temp = Arrays.asList(nums[i], nums[j], third);
                    Collections.sort(temp);
                    result.add(temp);
                }
                store.add(nums[j]);
            }
        }


        return new ArrayList<>(result);
    }
}

Optimal — sort, then two pointers: with the array sorted, fix i, then use j (right after i) and k (at the end) closing inward based on whether the current sum is too low or too high. Skip over duplicate values for i, j, and k to avoid duplicate triplets — no set needed at all, since sorted order means matching triplets are naturally adjacent.

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


        Arrays.sort(nums);
        for(int i = 0; i < n; i++){
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int j = i + 1;
            int k = n - 1;


            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum < 0){
                    j++;
                } else if (sum > 0){
                    k--;
                }
                else{
                    answer.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    while(j < k && nums[j] == nums[j-1]) j++;
                    while(j < k && nums[k] == nums[k-1]) k--;
                }
            }
        }
        return answer;
    }
}

Time: O(n log n) + O(n²). Space: O(number of unique triplets).