Pages

3SUM Problem

 

Here's the correct approach for 3Sum:

In the 3Sum problem, you're looking for unique triplets that sum to zero. So, once you find a triplet, you need to skip over duplicate values from both the left pointer (l) and the right pointer (r) to avoid considering the same triplet more than once.

Correct Deduplication Logic for 3Sum:




def threeSum(nums):
    nums.sort()  # Sort the array
    n = len(nums)
    res = []

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:  # Skip duplicates for 'i'
            continue

        l, r = i + 1, n - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if total < 0:
                l += 1
            elif total > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])

                # Skip duplicates for 'l' and 'r'
                while l < r and nums[l] == nums[l + 1]:
                    l += 1
                while l < r and nums[r] == nums[r - 1]:
                    r -= 1

                l += 1
                r -= 1

    return res

Key Deduplication Points:

  1. Skip duplicates for i:

    • Before moving the i pointer forward, check if nums[i] is equal to nums[i - 1]. This avoids considering the same starting element multiple times.

  2. Skip duplicates for l:

    • After finding a valid triplet, use while l < r and nums[l] == nums[l + 1] to skip over duplicates on the left side (to avoid reusing the same value for l).

  3. Skip duplicates for r:

    • Similarly, use while l < r and nums[r] == nums[r - 1] to skip duplicates on the right side.

Important:

  • The check while l < r and nums[l] == nums[l+1] is valid after finding a valid triplet and moving l or r. It's there to ensure that you don't pick the same number twice for l and r.

    Without it, you might end up including the same triplet multiple times (e.g., if nums[l] == nums[l+1], the triplet formed with both values would be identical).

Example Walkthrough:

For an input like:

nums = [-1, 0, 1, 2, -1, -4]
  • After sorting: [-4, -1, -1, 0, 1, 2]
  • You would start by selecting i = -4 and try to find pairs that sum to 4 (to make a total of 0).
  • After finding a valid triplet (like [-1, 0, 1]), you'd use the deduplication logic to skip duplicate values of l and r, ensuring that each triplet is unique.

Conclusion:

Yes, while l < r and nums[l] == nums[l+1] can be used in 3Sum, but only after finding a valid triplet and ensuring no duplicate triplets are added to the result. The right logic here is to carefully avoid revisiting the same values when adjusting the l and r pointers.

Let me know if you'd like a detailed step-by-step example of how the function works for a specific input!




Remove Nth Node from End of List – LeetCode #19

Use two pointers to remove the Nth node from the end of the linked list in one pass.

Tags