Four Sum Problem All Unique Quadruplets in DSA Python - Time & Space Complexity

Time Complexity: Four Sum Problem All Unique Quadruplets

O(n³)

Understanding Time Complexity

We want to understand how the time needed to find all sets of four numbers that add up to a target grows as the input list gets bigger.

How does the number of steps change when the list size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

nums.sort()
quadruplets = []
n = len(nums)
for i in range(n - 3):
    for j in range(i + 1, n - 2):
        left, right = j + 1, n - 1
        while left < right:
            total = nums[i] + nums[j] + nums[left] + nums[right]
            if total == target:
                quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1

This code finds all groups of four numbers in a list that add up to a given target value.

Identify Repeating Operations

• Primary operation: Nested loops and a two-pointer scan inside the innermost loop.
• How many times: The outer two loops run roughly n² times, and for each pair, the two-pointer scan runs up to n times.

How Execution Grows With Input

As the list size grows, the number of steps grows much faster because of the nested loops and the two-pointer scan inside.

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

Pattern observation: The steps grow roughly by the cube of the input size, so doubling the list size makes the work about eight times bigger.

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows roughly with the cube of the input size, so bigger lists take much more time.

Common Mistake

[X] Wrong: "Because we use two pointers inside, the time complexity is O(n²)."

[OK] Correct: The two-pointer scan runs inside two nested loops, so the total work multiplies, making it O(n³), not just O(n²).

Interview Connect

Understanding this time complexity helps you explain how nested loops and scanning affect performance, a key skill in solving real problems efficiently.

Self-Check

"What if we changed the problem to find unique triplets instead of quadruplets? How would the time complexity change?"