15. 3Sum

#two-pointers

Problem

3Sum - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // n -> nums.length
        // Time Complexity: O(n^2)
        // O(n logn) [sorting] + O(n^2) (finding triplet) = O(n^2)
        
        // Space Complexity: O(n), for storing the triplets

        // Sort the array in ascending order
        Arrays.sort(nums);
        
        // Use a set to store unique triplets
        Set<List<Integer>> resultContainer = new HashSet<>();
        
        // Iterate through the array
        for (int i = 0; i < nums.length - 2; i++) {
            int start = i + 1, end = nums.length - 1;
            
            // Use two pointers to find the remaining two elements
            while (start < end) {
                int current = nums[i] + nums[start] + nums[end];
                
                if (current == 0) {
                    // Found a triplet with sum equal to zero
                    resultContainer.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    start++;
                    end--;
                } else if (current > 0) {
                    // The current sum is greater than zero, decrement end pointer
                    end--;
                } else {
                    // The current sum is less than zero, increment start pointer
                    start++;
                }
            }
        }
        
        // Convert the set to a list and return
        return new ArrayList<>(resultContainer);
    }
}