Find All Triplets with Zero Sum

JavaView on GFG

Time: O(n^2)

Space: O(1)

Problem Overview

Sort array.

See our study guide for structured GFG and LeetCode practice.

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?