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

Time Complexity: Three Sum Problem All Unique Triplets

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to find all unique triplets that sum to zero grows as the input list gets bigger.

How does the number of steps change when we have more numbers to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs through each element, and inside it, the two-pointer while loop scans the remaining elements.
• How many times: The outer loop runs about n times, and the inner while loop runs up to n times in total for each outer iteration.

How Execution Grows With Input

As the input size grows, the number of steps grows roughly by the square of the input size.

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 by the square of the input size, so doubling the input makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n2)

This means the time needed grows roughly with the square of the number of elements in the input.

Common Mistake

[X] Wrong: "Because there are three numbers, the time complexity must be O(n³)"

[OK] Correct: The sorting and two-pointer approach reduces the inner search to linear time, so the total is O(n²), not cubic.

Interview Connect

Understanding this problem's time complexity helps you explain how to handle nested loops efficiently and shows your skill in optimizing search problems.

Self-Check

"What if the input array was already sorted? How would that affect the time complexity?"