4Sum - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Arrays, Two-Pointer Technique, Sorting

1: U-nderstand

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

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Can the same number be used multiple times in a quadruplet?

  • No, each quadruplet must contain distinct indices.

• Can there be duplicate quadruplets in the result?

  • No, we need to ensure that the output contains unique quadruplets only.

• How do we ensure unique quadruplets?

  • Use sorting and duplicate checks while iterating through the array.

HAPPY CASE
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [-2,-1,1,2],[-2,0,0,2],[-1,0,0,1](/codepath/compsci_guides/wiki/-2,-1,1,2],[-2,0,0,2],[-1,0,0,1)
Explanation: These are the only valid quadruplets whose sum is equal to 0.

Input: nums = [2,2,2,2,2], target = 8
Output: [2,2,2,2](/codepath/compsci_guides/wiki/2,2,2,2)
Explanation: There is only one unique quadruplet that sums to 8.

EDGE CASE
Input: nums = [], target = 0
Output: []

Input: nums = [1,2,3], target = 6
Output: []
Explanation: There are not enough elements to form a quadruplet.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Sorting or Two Pointers, and strategies or patterns in those categories.

For Four-Sum Problems, consider the following approaches:

• Sorting and Two-Pointer Technique: Helps to reduce the search space when looking for quadruplets.
• Avoiding Duplicates with Conditions: Skip over duplicate elements to ensure unique quadruplets.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Approach: Sorting + Two Pointers

General Idea:
Sort the array first. Use two nested loops to fix the first two elements, then apply the two-pointer technique to find the remaining two elements that make up the target sum.

Steps:

1) Sort the input array to simplify duplicate checks.
2) Use two loops to iterate over the first two elements (`nums[i]` and `nums[j]`).
3) Use a two-pointer approach to find the remaining two elements (`nums[left]` and `nums[right]`).
4) If the sum matches the target, store the quadruplet.
5) Use conditions to skip duplicate values to ensure uniqueness.
6) Return the list of unique quadruplets.

⚠️ Common Mistakes

• Forgetting to skip over duplicate elements to avoid duplicate quadruplets.
• Not handling cases where the input array has fewer than four elements.

4: I-mplement

Implement the code to solve the algorithm.

def four_sum(nums, target):
    nums.sort()  # Step 1: Sort the array
    res = []     # To store the result quadruplets
    n = len(nums)
    
    # Step 2: Iterate through the array with two loops for nums[i] and nums[j]
    for i in range(n):
        # Avoid duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n):
            # Avoid duplicates for the second element
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            
            # Step 3: Two-pointer technique for the remaining two numbers
            left, right = j + 1, n - 1
            while left < right:
                current_sum = nums[i] + nums[j] + nums[left] + nums[right]
                
                if current_sum == target:
                    res.append([nums[i], nums[j], nums[left], nums[right]])
                    
                    # Move pointers and avoid duplicates
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    left += 1
                    right -= 1
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1
    
    return res

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: nums = [1,0,-1,0,-2,2], target = 0

  • Sorted: [-2, -1, 0, 0, 1, 2]
  • Quadruplets: [-2, -1, 1, 2], [-2, 0, 0, 2], -1, 0, 0, 1
  • Output: [-2, -1, 1, 2], [-2, 0, 0, 2], -1, 0, 0, 1

• Input: nums = [2,2,2,2,2], target = 8

  • Output: 2,2,2,2

• Input: nums = [], target = 0

  • Output: []

• Input: nums = [1,2,3], target = 6

  • Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the input array.

• Time Complexity: O(N^3) since we have two nested loops and the two-pointer search takes linear time.
• Space Complexity: O(1) for the extra space used in storing results (excluding the output list).