DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 71: Python Three Sum – Two-Pointer O(n^2) Solution for Unique Zero-Sum Triplets (LeetCode #15 Vibes)

#challenge #python #algorithms #programming

Welcome to Day 71 of the #80DaysOfChallenges journey! This intermediate challenge tackles the classic Three Sum problem (LeetCode #15), finding all unique triplets in an array that sum to zero without duplicates, using sorting for O(n^2) efficiency and two pointers to scan pairs. It combines array sorting, pointer adjustments for sum targeting, and skip logic for duplicates, a staple pattern for sum-based problems in interviews and data processing. If you're advancing from basic arrays to optimized multi-pointer algos or prepping for questions like k-sum variants, this "Python three sum" script demonstrates a function that's robust, avoids brute O(n^3), and easy to extend for four-sum or non-zero targets.

💡 Key Takeaways from Day 71: Three Sum Function

This task features a function that sorts the array, fixes one element, and uses two pointers to find pairs summing to negation, with skips for uniqueness. It's a sorted two-pointer pattern: left/right move based on sum. We'll detail: function with sort and result list, outer loop with duplicate skip and pointers, and main with input parse.

1. Function Design: Sort and Result Init

The three_sum function takes nums, returns list of triplets:

def three_sum(nums: list[int]) -> list[list[int]]:
    """Return all unique triplets [a, b, c] such that a + b + c == 0."""
    nums.sort()                         # sort array for two-pointer logic
    result = []
    n = len(nums)
Enter fullscreen mode Exit fullscreen mode

Sort enables pointers and duplicate skips. Result collects unique triplets.

2. Outer Loop: Fix i, Skip Duplicates, Inner Pointers

Fix i, scan left/right for -nums[i]:

    for i in range(n):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                    # skip duplicate first elements

        left = i + 1
        right = n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])

                left += 1
                right -= 1

                # skip duplicate values for left pointer
                while left < right and nums[left] == nums[left - 1]:
                    left += 1

                # skip duplicate values for right pointer
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

            elif total < 0:
                left += 1               # need a larger sum
            else:
                right -= 1              # need a smaller sum

    return result
Enter fullscreen mode Exit fullscreen mode

Outer skips duplicate i. Inner while: if sum 0, append, move pointers, skip dups. If <0, left+; >0, right-. O(n^2) time.

3. Main Interactive: Space-Separated Input

Script reads nums, calls, prints:

raw = input("Enter numbers (space-separated): ").strip()
nums = list(map(int, raw.split()))

triplets = three_sum(nums)
print(f"Triplets with zero sum: {triplets}")
Enter fullscreen mode Exit fullscreen mode

Parses ints, computes, shows triplets. Simple testbed.

🎯 Summary and Reflections

This three sum uses sort and pointers for efficient unique triplets. It reinforced:

  • Duplicate skips: Essential for uniqueness without sets.
  • Pointer moves: Sum guides left/right.
  • Fixed i pattern: Reduces 3-sum to 2-sum.

Reflections: Handles negatives/dups. For closest sum, adjust logic.

Advanced Alternatives: Hash for 2-sum inner (O(n)). 4-sum nesting. Your sum trick? Share!

🚀 Next Steps and Resources

Day 71 summed triplets efficiently. In #80DaysOfChallenges? Non-zero? Post!

Top comments (0)