// 3Sum - https://leetcode.com/problems/3sum/description/

class Solution {
    // Brute Force
    // Time Complexity: O(n^3)
    // Space Complexity: O(m) where m is number of triplets
    // Below solution leads to TLE in LeetCode
    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> result = new ArrayList<>();
    //     Set<String> set = new HashSet<>();

    //     for(int i = 0; i < nums.length; i++) {
    //         for(int j = i + 1; j < nums.length; j++) {
    //             for(int k = j + 1; k < nums.length; k++) {
    //                 if(nums[i] + nums[j] + nums[k] == 0) {
    //                     int[] triplet = new int[]{nums[i], nums[j], nums[k]};
    //                     Arrays.sort(triplet);
    //                     if(set.contains(Arrays.toString(triplet))) {
    //                         continue;
    //                     }
    //                     set.add(Arrays.toString(triplet));
    //                     result.add(Arrays.asList(nums[i], nums[j], nums[k]));
    //                 }
    //             }
    //         }
    //     }

    //     return result;
    // }

    // Brute Force (Optimised)
    // Time Complexity: O(n^3)
    // Space Complexity: O(m) where m is number of triplets
    // Below solution leads to TLE in LeetCode
    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> result = new ArrayList<>();
    //     Arrays.sort(nums);
    //     Set<String> set = new HashSet<>();
    //     for(int i = 0; i < nums.length; i++) {
    //         if (i > 0 && nums[i] == nums[i-1]) continue;
    //         if(nums[i] > 0) {
    //              break;
    //         }
    //         for(int j = i + 1; j < nums.length; j++) {
    //             for(int k = j + 1; k < nums.length; k++) {
    //                 if(nums[i] + nums[j] + nums[k] == 0) {
    //                     int[] triplet = new int[]{nums[i], nums[j], nums[k]};
    //                     if(set.contains(Arrays.toString(triplet))) {
    //                         continue;
    //                     }
    //                     set.add(Arrays.toString(triplet));
    //                     result.add(Arrays.asList(nums[i], nums[j], nums[k]));
    //                 }
    //             }
    //         }
    //     }

    //     return result;
    // }

    // Two Pointers
    // Time Complexity: O(n^2)
    // Space Complexity: O(n)
    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> result = new ArrayList<>();
    //     Set<String> set = new HashSet<>();
    //     Arrays.sort(nums);

    //     for(int i = 0; i < nums.length; i++) {
    //         int left = i + 1, right = nums.length - 1;
    //         while (left < right) {
    //             if(nums[i] + nums[left] + nums[right] == 0) {
    //                 int[] triplet = new int[]{nums[i], nums[left], nums[right]};
    //                 if(set.contains(Arrays.toString(triplet))) {
    //                     left++;
    //                     right--;
    //                     continue;
    //                 }
    //                 set.add(Arrays.toString(triplet));
    //                 result.add(Arrays.asList(nums[i], nums[left], nums[right]));
    //                 left++;
    //                 right--;
    //             }
    //             else if (nums[i] + nums[left] + nums[right] > 0) {
    //                 right--;
    //             } else {
    //                 left++;
    //             }
    //         }
    //     }

    //     return result;
    // }

    // Two Pointers (Optimised)
    // Time Complexity: O(n^2)
    // Space Complexity: O(1)
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }

            if(nums[i] > 0) {
                break;
            }

            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;

                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                }
                else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return result;
    }

}