Sort Colors Two Pointer Dutch Flag in DSA C - Time & Space Complexity

Time Complexity: Sort Colors Two Pointer Dutch Flag

O(n)

Understanding Time Complexity

We want to understand how the time needed to sort colors using two pointers changes as the list grows.

How does the number of steps grow when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low];
            nums[low++] = nums[mid];
            nums[mid++] = temp;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high--] = temp;
        }
    }
}
    

This code sorts an array containing 0s, 1s, and 2s by moving pointers and swapping elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves the mid pointer through the array.
• How many times: At most once per element, so up to n times where n is the array size.

How Execution Grows With Input

As the input size grows, the number of steps grows roughly in direct proportion.

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

Pattern observation: The steps increase linearly as the input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to sort grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Because there are nested ifs and swaps, the time must be quadratic O(n²)."

[OK] Correct: Each element is visited at most once by the mid pointer, and swaps do not cause repeated passes, so the total steps stay linear.

Interview Connect

Understanding this linear time sorting method shows you can handle efficient in-place algorithms, a skill valued in many coding challenges.

Self-Check

"What if we changed the array to contain more than three colors? How would the time complexity change?"