API tools faq
paste
titan2400

3Sum - LeetCode

titan2400
Nov 6th, 2025 (edited)
254
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.73 KB | Source Code | 0 0
raw download clone embed print report
  1. // 3Sum - https://leetcode.com/problems/3sum/description/
  2.  
  3. class Solution {
  4.     // Brute Force
  5.     // Time Complexity: O(n^3)
  6.     // Space Complexity: O(m) where m is number of triplets
  7.     // Below solution leads to TLE in LeetCode
  8.     // public List<List<Integer>> threeSum(int[] nums) {
  9.     //     List<List<Integer>> result = new ArrayList<>();
  10.     //     Set<String> set = new HashSet<>();
  11.  
  12.     //     for(int i = 0; i < nums.length; i++) {
  13.     //         for(int j = i + 1; j < nums.length; j++) {
  14.     //             for(int k = j + 1; k < nums.length; k++) {
  15.     //                 if(nums[i] + nums[j] + nums[k] == 0) {
  16.     //                     int[] triplet = new int[]{nums[i], nums[j], nums[k]};
  17.     //                     Arrays.sort(triplet);
  18.     //                     if(set.contains(Arrays.toString(triplet))) {
  19.     //                         continue;
  20.     //                     }
  21.     //                     set.add(Arrays.toString(triplet));
  22.     //                     result.add(Arrays.asList(nums[i], nums[j], nums[k]));
  23.     //                 }
  24.     //             }
  25.     //         }
  26.     //     }
  27.  
  28.     //     return result;
  29.     // }
  30.  
  31.     // Brute Force (Optimised)
  32.     // Time Complexity: O(n^3)
  33.     // Space Complexity: O(m) where m is number of triplets
  34.     // Below solution leads to TLE in LeetCode
  35.     // public List<List<Integer>> threeSum(int[] nums) {
  36.     //     List<List<Integer>> result = new ArrayList<>();
  37.     //     Arrays.sort(nums);
  38.     //     Set<String> set = new HashSet<>();
  39.     //     for(int i = 0; i < nums.length; i++) {
  40.     //         if (i > 0 && nums[i] == nums[i-1]) continue;
  41.     //         if(nums[i] > 0) {
  42.     //              break;
  43.     //         }
  44.     //         for(int j = i + 1; j < nums.length; j++) {
  45.     //             for(int k = j + 1; k < nums.length; k++) {
  46.     //                 if(nums[i] + nums[j] + nums[k] == 0) {
  47.     //                     int[] triplet = new int[]{nums[i], nums[j], nums[k]};
  48.     //                     if(set.contains(Arrays.toString(triplet))) {
  49.     //                         continue;
  50.     //                     }
  51.     //                     set.add(Arrays.toString(triplet));
  52.     //                     result.add(Arrays.asList(nums[i], nums[j], nums[k]));
  53.     //                 }
  54.     //             }
  55.     //         }
  56.     //     }
  57.  
  58.     //     return result;
  59.     // }
  60.  
  61.     // Two Pointers
  62.     // Time Complexity: O(n^2)
  63.     // Space Complexity: O(n)
  64.     // public List<List<Integer>> threeSum(int[] nums) {
  65.     //     List<List<Integer>> result = new ArrayList<>();
  66.     //     Set<String> set = new HashSet<>();
  67.     //     Arrays.sort(nums);
  68.  
  69.     //     for(int i = 0; i < nums.length; i++) {
  70.     //         int left = i + 1, right = nums.length - 1;
  71.     //         while (left < right) {
  72.     //             if(nums[i] + nums[left] + nums[right] == 0) {
  73.     //                 int[] triplet = new int[]{nums[i], nums[left], nums[right]};
  74.     //                 if(set.contains(Arrays.toString(triplet))) {
  75.     //                     left++;
  76.     //                     right--;
  77.     //                     continue;
  78.     //                 }
  79.     //                 set.add(Arrays.toString(triplet));
  80.     //                 result.add(Arrays.asList(nums[i], nums[left], nums[right]));
  81.     //                 left++;
  82.     //                 right--;
  83.     //             }
  84.     //             else if (nums[i] + nums[left] + nums[right] > 0) {
  85.     //                 right--;
  86.     //             } else {
  87.     //                 left++;
  88.     //             }
  89.     //         }
  90.     //     }
  91.  
  92.     //     return result;
  93.     // }
  94.  
  95.     // Two Pointers (Optimised)
  96.     // Time Complexity: O(n^2)
  97.     // Space Complexity: O(1)
  98.     public List<List<Integer>> threeSum(int[] nums) {
  99.         List<List<Integer>> result = new ArrayList<>();
  100.         Arrays.sort(nums);
  101.  
  102.         for(int i = 0; i < nums.length; i++) {
  103.             if(i > 0 && nums[i] == nums[i-1]) {
  104.                 continue;
  105.             }
  106.  
  107.             if(nums[i] > 0) {
  108.                 break;
  109.             }
  110.  
  111.             int left = i + 1, right = nums.length - 1;
  112.             while (left < right) {
  113.                 int sum = nums[i] + nums[left] + nums[right];
  114.                 if(sum == 0) {
  115.                     result.add(Arrays.asList(nums[i], nums[left], nums[right]));
  116.                     left++;
  117.                     right--;
  118.  
  119.                     while (left < right && nums[left] == nums[left - 1]) {
  120.                         left++;
  121.                     }
  122.                 }
  123.                 else if (sum > 0) {
  124.                     right--;
  125.                 } else {
  126.                     left++;
  127.                 }
  128.             }
  129.         }
  130.  
  131.         return result;
  132.     }
  133.  
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!