Four Sum Problem All Unique Quadruplets in DSA C - 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 unique sets of four numbers that add up to a target grows as the input list grows.

How does the work increase when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void fourSum(int* nums, int numsSize, int target) {
    qsort(nums, numsSize, sizeof(int), compare);
    for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    // store quadruplet
                    left++; right--;
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
}
    

This code finds all unique groups of four numbers in a sorted array that add up to the target value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops and two-pointer traversal inside the while loop.
• How many times: Outer loop runs about n times, second loop about n times, and the two-pointer while loop runs up to n times in total for each pair.

How Execution Grows With Input

As the list size grows, the number of operations grows roughly by the cube of the input size.

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

Pattern observation: When input size increases 10 times, operations increase about 1000 times, showing cubic growth.

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows roughly with the cube of the input size, so doubling the input makes the work about eight times bigger.

Common Mistake

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

[OK] Correct: The innermost two-pointer loop does not run n times for each iteration; it moves pointers inward, so total work inside is linear, not quadratic, reducing complexity to O(n³).

Interview Connect

Understanding this time complexity helps you explain how nested loops and two-pointer techniques combine, a common pattern in coding problems.

Self-Check

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