Two-pointer technique in Data Structures Theory - Time & Space Complexity

Time Complexity: Two-pointer technique

O(n)

Understanding Time Complexity

The two-pointer technique helps solve problems by moving two markers through data.

We want to know how the time needed grows as the data size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function twoPointerSum(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === target) return true;
    else if (sum < target) left++;
    else right--;
  }
  return false;
}
    

This code checks if two numbers in a sorted list add up to a target by moving two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop moves pointers through the array.
• How many times: Each pointer moves at most once through the array, so up to n steps total.

How Execution Grows With Input

As the list gets bigger, the pointers move more steps but only once each.

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

Pattern observation: The steps grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the size of the input list.

Common Mistake

[X] Wrong: "Since there are two pointers, the time is doubled or squared."

[OK] Correct: The pointers move in one pass without nested loops, so steps add up linearly, not multiply.

Interview Connect

Understanding how two pointers move through data helps solve many real problems efficiently and shows clear thinking about performance.

Self-Check

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