algoadvance

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]]

Clarifying Questions

1. What should we return if there are no triplets that sum up to zero?
   • Return an empty list [].
2. Do we need to consider the order of the elements in the triplets in the output?
   • No, the order within each triplet does not matter, but the triplet should be in ascending order.
3. Can the input array contain duplicates?
   • Yes, the input array can contain duplicates, but the output should not contain duplicate triplets.

Strategy

1. Sorting - First, sort the array. This helps in efficiently finding the triplets and also in skipping duplicates.
2. Two-Pointer Technique - Use a fixed pointer to iterate through the array and use a two-pointer approach to find pairs that sum up to the negative value of the current fixed-point value.
3. Skip Duplicates - Ensure that we skip duplicates by checking the current value against the previous one after moving the pointers.

Time Complexity

• Sorting the array takes (O(n \log n)).
• The two-pointer approach runs in (O(n^2)) because we have an outer loop iterating through each element and the inner loop using two pointers iterating through the rest of the list.
• Thus, the overall time complexity is (O(n^2)).

Code

def threeSum(nums):
    nums.sort()  # Step 1: Sort the array
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:  # Skip duplicate elements
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:  # Apply two-pointer approach
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:  # Skip duplicates
                    left += 1
                while left < right and nums[right] == nums[right - 1]:  # Skip duplicates
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:  # Move the left pointer to increase the total sum
                left += 1
            else:  # Move the right pointer to decrease the total sum
                right -= 1
    
    return result

# Example usage
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))  # Output: [[-1, -1, 2], [-1, 0, 1]]

This solution effectively handles the input, uses sorting and two-pointer techniques to find the required triplets, and ensures no duplicates in the output.

Try our interview co-pilot at AlgoAdvance.com

• 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?