Java: Three Sum

Thought Process

The Three Sum problem can be solved efficiently using a two-pointer approach. First, sort the array to make it easier to handle duplicates and to use the two-pointer technique. Iterate through the array, and for each element, use two pointers to find pairs that sum up to the negative of the current element, ensuring that the sum of all three elements is zero. Skip duplicates to avoid redundant solutions. This approach ensures that we find all unique triplets that sum to zero. 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
  
        Set<List<Integer>> st = new HashSet<>();
        int sz = nums.length;
  
        Arrays.sort(nums);
  
        for(int i=0;i<sz-2;i++){
  
            int j = i+1;
            int k = sz-1;
  
            while(j<k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum==0){
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);   tmp.add(nums[j]);   tmp.add(nums[k]);
                  
                    st.add(tmp);
                    j++;
                    k--;
                }
                else if(sum<0){
                    j++;
                }
                else{
                    k--;
                }
            }
        }
        return new ArrayList<>(st);
          
    }
}

Code Complexity

Time Complexity: O(n2)

The algorithm iterates through the array once, and for each element, it uses a two-pointer approach to find pairs, resulting in a time complexity of O(n2).

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, ignoring the space required for the output.

Code copied!