Three Sum Problem All Unique Triplets in DSA Python - Time & Space Complexity

Time Complexity: Three Sum Problem All Unique Triplets

O(n²)

Understanding Time Complexity

We want to understand how the time needed grows when finding all unique triplets that sum to zero in a list.

How does the number of steps change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

nums.sort()
result = []
for i in range(len(nums)):
    if i > 0 and nums[i] == nums[i-1]:
        continue
    left, right = i + 1, len(nums) - 1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total < 0:
            left += 1
        elif total > 0:
            right -= 1
        else:
            result.append([nums[i], nums[left], nums[right]])
            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
    

This code finds all unique triplets in the list that add up to zero using sorting and two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs through each element once, and inside it, a while loop moves two pointers through the remaining elements.
• How many times: The outer loop runs n times, and the inner while loop moves pointers across the list, together covering the list roughly n times for each outer loop.

How Execution Grows With Input

As the list size grows, the number of steps grows much faster because for each element, we scan the rest with two pointers.

Input Size (n)	Approx. Operations
10	About 100 steps
100	About 10,000 steps
1000	About 1,000,000 steps

Pattern observation: The steps grow roughly with the square of the input size, meaning if the list size doubles, the work increases about four times.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the list size, so doubling the list makes the work about four times bigger.

Common Mistake

[X] Wrong: "The time complexity is O(n³) because there are three nested loops."

[OK] Correct: The code uses sorting and two pointers inside a single loop, not three nested loops. The inner while loop moves pointers forward without restarting, so total work is less than cubic.

Interview Connect

Understanding this problem's time complexity helps you explain how to handle searching pairs efficiently after sorting, a skill useful in many coding challenges.

Self-Check

"What if we used three nested loops instead of two pointers? How would the time complexity change?"