Find All Triplets with Zero Sum

JavaView on GFG

Time: O(n^2)

Space: O(1)

Intuition

Sort array. For each element, use two pointers to find pairs summing to negation of that element.

Algorithm

1Sort. For each i from 0 to n-3: lo=i+1, hi=n-1.
2While lo<hi: if sum==0 record, lo++, hi--. Skip duplicates. If sum<0: lo++. If sum>0: hi--.

Common Pitfalls

•Skip duplicates to avoid repeated triplets. Same as 3Sum (LC 15).

Find All Triplets with Zero Sum.java

Java

// Approach: Sort, then for each element use two pointers to find pairs summing to its negation.
// Time: O(n^2) Space: O(1)
class Solution {
    public List<List<Integer>> findTriplets(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();

        int len = arr.length;

        Map<Integer, ArrayList<Integer>> map = new HashMap<>();

        for (int i = 0; i < len; i++) {
            int val = arr[i];
            if (!map.containsKey(val)) {
                map.put(val, new ArrayList<>());
            }
            map.get(val).add(i);
        }

        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                int target = -(arr[i] + arr[j]);
                if (map.containsKey(target)) {
                    for (int idx : map.get(target)) {
                        if (idx > j) {
                            List<Integer> al = new ArrayList<>(Arrays.asList(i, j, idx));
                            // Collections.sort(al);
                            result.add(al);
                        }
                    }
                }
            }
        }
        return result;
    }
}

Was this solution helpful?