4Sum Better

import java.util.*;

        public class FourSumBetter {
            public List> fourSum(int[] nums, int target) {
                int n = nums.length;
                Set> set = new HashSet<>();
                for (int i = 0; i < n; i++) {
                    for (int j = i + 1; j < n; j++) {
                        HashSet seen = new HashSet<>();
                        for (int k = j + 1; k < n; k++) {
                            long sum = (long) nums[i] + nums[j] + nums[k];
                            long needed = (long) target - sum;
                            if (seen.contains(needed)) {
                                List temp = Arrays.asList(nums[i], nums[j], nums[k], (int) needed);
                                Collections.sort(temp);
                                set.add(temp);
                            }
                            seen.add((long) nums[k]);
                        }
                    }
                }
                return new ArrayList<>(set);
            }

            public static void main(String[] args) {
                FourSumBetter sol = new FourSumBetter();
                int[] nums = {1, 0, -1, 0, -2, 2}; // Example input
                int target = 0;
                List> result = sol.fourSum(nums, target);
                System.out.println("Quadruplets that sum to target: " + result);
            }
        }
                

Largest Subarray With 0 Sum - Brute Approach

class Solution {
            int maxLength(int arr[]) {
                int n = arr.length;
                int maxLen = 0; 
                // This will store the answer
                for(int i = 0; i < n; i++) {
                    int sum = 0;       // IMPORTANT: Reset sum for every new starting index i
                    for(int j = i; j < n; j++) {     // Fixed: j < n (not i < n)
                      sum+= arr[j];
                      if(sum == 0){
                          int currL = j-i+1;
                          if(currL > maxLen){
                              maxLen = currL;
                          }
                      }
                    }
                }
                return maxLen;         // Don't forget to return the result
            }
        }
                

4Sum Optimal

import java.util.*;

        public class FourSumOptimal {
            public List> fourSum(int[] nums, int target) {
                int n = nums.length;
                List> ans = new ArrayList<>();
                Arrays.sort(nums);
                for (int i = 0; i < n - 3; i++) {
                    if (i > 0 && nums[i] == nums[i - 1]) continue;
                    for (int j = i + 1; j < n - 2; j++) {
                        if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                        int k = j + 1;
                        int l = n - 1;
                        while (k < l) {
                            long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
                            if (sum == target) {
                                ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                                while (k < l && nums[k] == nums[k + 1]) k++;
                                while (k < l && nums[l] == nums[l - 1]) l--;
                                k++;
                                l--;
                            } 
                            else if (sum < target) {
                                k++;
                            } 
                            else {
                                l--;
                            }
                        }
                    }
                }
                return ans;
            }

            public static void main(String[] args) {
                FourSumOptimal sol = new FourSumOptimal();
                int[] nums = {1, 0, -1, 0, -2, 2}; // Example input
                int target = 0;
                List> result = sol.fourSum(nums, target);
                System.out.println("Quadruplets that sum to target: " + result);
            }
        }
                

3Sum Brute

import java.util.*;

public class 3sumBrute{
    public List> threeSum(int[] nums) {
        int n = nums.length;
        List> store = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triplet);
                        if (!store.contains(triplet)) {
                            store.add(triplet);
                        }
                    }
                }
            }
        }
        return store;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-1, 0, 1, 2, -1, -4}; // Example input
        List> result = sol.threeSum(nums);
        System.out.println("Triplets that sum to zero: " + result);
    }
}
        

3Sum Better

import java.util.*;

public class ThreeSumBetter {
    public List> threeSum(int[] nums) {
        Set> ans = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            Set seen = new HashSet<>();   
            for (int j = i + 1; j < nums.length; j++) {
                int third = -(nums[i] + nums[j]);
                if (seen.contains(third)) {
                    List temp = Arrays.asList(nums[i], nums[j], third);
                    Collections.sort(temp);        
                    ans.add(temp);
                }
                seen.add(nums[j]);               
            }
        }
        return new ArrayList<>(ans);
    }

    public static void main(String[] args) {
        ThreeSumBetter sol = new ThreeSumBetter();
        int[] nums = {-1, 0, 1, 2, -1, -4}; // Example input
        List> result = sol.threeSum(nums);
        System.out.println("Triplets that sum to zero: " + result);
    }
}
        

3Sum Optimal

import java.util.*;

// LeetCode-style: Implement the threeSum method
class Solution {
    public List> threeSum(int[] nums) {
        List> result = new ArrayList<>();
        Arrays.sort(nums);

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

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

                    while(j < k){
                        j++;
                        if(nums[j] != nums[j-1]) break;
                    }

                    while(j < k){
                        k--;
                        if(nums[k] != nums[k+1]) break;
                    }
                }
            }
        }
        return result;
    }
}