DevExCode

15. 3Sum

ArrayTwo PointersSorting

Explanation

To solve this problem, we can use the two-pointer technique along with sorting the input array. The idea is to fix one element and then find the other two elements using two pointers. We need to handle duplicates properly to avoid duplicate triplets in the result.

  1. Sort the input array nums.
  2. Iterate through the array, fixing one element at a time.
  3. Use two pointers (left and right) to find the other two elements that sum up to the target (0 - nums[i]).
  4. Handle duplicates by skipping equal elements while moving the pointers.
  5. Add the triplet to the result if found.
  6. Repeat the process until all possible triplets are checked.

Time complexity: O(n^2) where n is the length of the input array nums. Space complexity: O(log n) to O(n) depending on the sorting algorithm.

View Leetcode Problem
import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int target = 0 - nums[i];
                int left = i + 1, right = n - 1;

                while (left < right) {
                    if (nums[left] + nums[right] == target) {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return result;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question