Two Pointer Technique on Arrays in DSA C - Time & Space Complexity

Time Complexity: Two Pointer Technique on Arrays

O(n)

Understanding Time Complexity

We want to understand how fast the two pointer technique works on arrays.

Specifically, how the number of steps changes as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int left = 0, right = n - 1;
while (left < right) {
    if (arr[left] + arr[right] == target) {
        // found pair
        break;
    } else if (arr[left] + arr[right] < target) {
        left++;
    } else {
        right--;
    }
}
    

This code uses two pointers moving from both ends of a sorted array to find a pair that sums to a target.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop moving pointers left and right.
• How many times: Each pointer moves at most n times combined, so up to n steps.

How Execution Grows With Input

As the array size grows, the total steps grow roughly in a straight line.

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

Pattern observation: The steps increase directly with input size, not faster or slower.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the pair grows in a straight line with the array size.

Common Mistake

[X] Wrong: "Since there are two pointers, the time is O(n²)."

[OK] Correct: The pointers move towards each other and each element is visited at most once, so total steps are linear, not squared.

Interview Connect

Understanding this technique shows you can solve problems efficiently by smartly scanning arrays.

Self-Check

"What if the array was not sorted? How would the time complexity change?"