algoadvance

Leetcode 15. 3Sum

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Clarifying Questions

1. Q: What should be returned if there are no such triplets? A: An empty list should be returned.

2. Q: Can the input include duplicate numbers? A: Yes, the input can contain duplicate numbers, but the solution must not contain duplicate triplets.

3. Q: Should the triplets be returned in any specific order? A: No, the order of the triplets does not matter.

Strategy

To solve the 3Sum problem, we can use a two-pointer approach with sorting:

1. Sort the Array: First, sort the input array. This makes it easier to avoid duplicates and use the two-pointer technique.

2. Iterate through the Array: For each element in the array (with the index i), treat it as the first element of the triplet and use two pointers to find pairs that add up to the negative of the first element.

3. Two-pointer Technique:
   • Initialize two pointers: one starting just after i (left) and one at the end of the array (right).
   • Move the left pointer to the right and the right pointer to the left based on the sum of nums[i] + nums[left] + nums[right].
   • If the sum is zero, record the triplet and adjust both pointers, being careful to skip over duplicates.
4. Avoid Duplicates: Skip duplicate values both when choosing the first element of the triplet and when adjusting the two pointers.

Code

import java.util.*;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicates for the first element.
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int left = i + 1;
            int 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]));
                    
                    // Skip duplicates for the second element.
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // Skip duplicates for the third element.
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return result;
    }
}

Time Complexity

• Sorting the array: O(n log n)
• Iterating through the array elements: O(n)
• Two-pointer approach for each element: O(n)

Therefore, the overall time complexity is O(n^2).

• Space Complexity:
  • The space complexity mainly depends on the sorting step, which typically takes O(n) auxiliary space if the sort implementation uses a non-in-place algorithm. However, most in-place sorts like QuickSort would use O(log n) auxiliary space.
  • Additionally, the output list can take up to O(n^2) space in the worst case if there are many triplets.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?