Sort Colors Two Pointer Dutch Flag in DSA Python - 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 the two-pointer Dutch Flag method changes as the list grows.

How does the number of steps grow when we have more colors to sort?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

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

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 it runs about n times where n is the number of elements.

How Execution Grows With Input

As the list gets longer, the number of steps grows roughly the same as the number of elements.

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

Pattern observation: The steps increase linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to sort grows directly in proportion to the number of elements.

Common Mistake

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

[OK] Correct: The loop moves through the list only once, and swaps happen in constant time without extra loops, so the total steps grow linearly.

Interview Connect

Understanding this linear time sorting method shows you can handle problems efficiently with clever pointer use, a skill valued in many coding challenges.

Self-Check

"What if we used three separate loops to sort each color instead of one loop with pointers? How would the time complexity change?"