Three Sum - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Sorting, Two-Pointer Technique

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is an integer array nums.

• Q: What is the expected output of the function?

  • A: The function should return a list of all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

• Q: How should the function handle duplicates?

  • A: The solution set must not contain duplicate triplets. The function should ensure that the same triplet is not added more than once.

• Q: What if the array is empty or contains fewer than three elements?

  • A: If the array is empty or contains fewer than three elements, the function should return an empty list.

• The function three_sum() should return all unique triplets from the array nums such that the sum of the triplets equals zero.

HAPPY CASE
Input: [-1, 0, 1, 2, -1, -4]
Expected Output: [-1, -1, 2], [-1, 0, 1](/codepath/compsci_guides/wiki/-1,--1,-2],-[-1,-0,-1)

UNHAPPY CASE
Input: [0, 1, 1]
Expected Output: []

EDGE CASE
Input: [0, 0, 0]
Expected Output: [0, 0, 0](/codepath/compsci_guides/wiki/0,-0,-0)

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the array, then use a loop with a two-pointer approach to find the triplets that sum to zero.

1. Sort the input array `nums`.
2. Initialize an empty list `result` to store the unique triplets.
3. Loop through the array with index `i` from 0 to len(nums) - 2:
   a. Skip duplicates for the current `i`.
   b. Initialize two pointers: `left` at `i + 1` and `right` at the end of the array.
   c. While left is less than right:
      i. Calculate the sum of nums[i], nums[left], and nums[right].
      ii. If the sum is zero, add the triplet to `result`, then skip duplicates for `left` and `right`, and adjust both pointers.
      iii. If the sum is less than zero, increment `left`.
      iv. If the sum is greater than zero, decrement `right`.
4. Return the `result` list

⚠️ Common Mistakes

• Not skipping duplicates correctly.
• Mismanaging pointer positions leading to incorrect results or infinite loops.

I-mplement

Implement the code to solve the algorithm.

def three_sum(nums):
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:  # Skip duplicate values for i
            continue
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            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 for left
                    left += 1
                while left < right and nums[right] == nums[right - 1]:  # Skip duplicates for right
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result