Bounding Total Complexity via Monotonic Pointer Movement

Good to see you again. Previously, you separated total work from maximum simultaneous work when analyzing recursion: many calls over time do not necessarily mean a deep stack. The same care is needed for pointer loops. A loop inside another loop does not automatically mean $O(n^2)$.

In this lesson, you will learn to prove the total complexity of a monotonic-pointer algorithm by counting how far each pointer can move over the entire execution. This is a core interview skill behind two pointers, sliding windows, merging, and several greedy scans.

---

Syntax can look quadratic while the work is linear

Consider this familiar shape:

int left = 0;
int right = 0;

while (right < n) {
    // Do constant-time work involving nums[left..right]

    while (/* window is invalid */) {
        // Do constant-time work
        left++;
    }

    right++;
}

There is a while loop inside another while loop, so a mechanical analysis might say:

• outer loop runs $n$ times;
• inner loop runs up to $n$ times;
• therefore $O(n^2)$.

That conclusion is often wrong.

The missing question is:

Does the inner-loop pointer start over from the beginning for every outer-loop iteration?

Here, left is not reset. It only moves forward. Once it passes an index, it never returns to that index. Therefore, across the whole algorithm, it can advance at most $n$ times.

Meanwhile, right also advances at most $n$ times. So the total number of pointer advances is at most:

$$n+n=2n$$

Dropping the constant factor gives:

$$O(n)$$

This is called an amortized or aggregate analysis: rather than trying to bound the cost of one particular outer-loop iteration, you add up the costs over the full run.

A monotonic pointer is simply one that moves in only one direction:

• it increases but never decreases, or
• it decreases but never increases.

The principle to remember is:

A pointer that can cross an array only once contributes at most $O(n)$ total movements, even when its movement occurs inside a nested loop.

---

A proof pattern you can state in an interview

For a pointer-based loop, give a short proof in four parts.

1. State each pointer’s range.
   For an array of length $n$, an index usually remains between $0$ and $n$, inclusive or exclusive depending on the implementation.

2. Show monotonic movement.
   Explain that each pointer moves in one direction only and is never reset.

3. Bound total movements.
   Each pointer can cross at most $n$ array positions, so it moves at most $n$ times.

4. Verify constant work per movement.
   Adding or removing one value from a running sum, comparing two values, and updating an answer are all $O(1)$.

For the nested-window shape above:

• right advances at most $n$ times.
• left advances at most $n$ times across all executions of the inner loop.
• Each advance performs constant work.

Therefore:

$$T(n)=O(n)+O(n)=O(n)$$

A concise explanation is:

“Although there is a nested loop, left never moves backward. The outer loop advances right at most $n$ times, and all inner-loop iterations combined advance left at most $n$ times. Since each pointer movement does constant work, total time is $O(n)$.”

Read the USACO Guide’s worked sliding-window reasoning. Do not focus on the specific “Books” problem yet; focus on the argument that moving left forward never requires right to move backward.

---

Opposing pointers: use the shrinking gap

Pointers do not need to travel in the same direction to be monotonic. Consider a sorted-array scan:

static boolean hasPairWithSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        long sum = (long) nums[left] + nums[right];

        if (sum == target) {
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return false;
}

This loop has two pointers moving toward each other:

• left only increases;
• right only decreases;
• on every non-returning iteration, exactly one pointer moves.

A particularly clean proof uses the gap:

$$\text{gap}=\text{right}-\text{left}$$

Initially, the gap is at most $n-1$. Every loop iteration reduces it by one:

• left++ makes the gap smaller;
• right-- also makes the gap smaller.

The loop stops when the gap reaches zero. Therefore, it has at most $n-1$ iterations:

$$O(n)$$

This argument is stronger than merely saying “there are two pointers.” It identifies a quantity that always moves toward termination.

Notice the long cast in the sum:

long sum = (long) nums[left] + nums[right];

It prevents addition from overflowing before comparison when nums can contain large int values. The pointer-loop complexity remains $O(n)$.

If this method first sorts an unsorted array, distinguish the costs:

Part	Time
Sort the array	$O(n\log n)$
Opposing-pointer scan	$O(n)$
Total	$O(n\log n)$

Do not describe the entire solution as $O(n)$ merely because the pointer loop is linear. The loop is $O(n)$; preprocessing may dominate the complete algorithm.

---

Same-direction pointers: charge each element at most twice

A sliding window usually has pointers moving left to right. The relevant accounting view is often simpler than tracking iterations:

• an element is added when the right boundary reaches it;
• an element is removed when the left boundary passes it;
• no element can be added more than once;
• no element can be removed more than once.

That means each array element causes at most two constant-time updates.

For a fixed-size window, the running sum update is conceptually:

windowSum += nums[right];
windowSum -= nums[left];

The window’s middle elements are not re-summed. That reuse of overlap is what avoids $O(nk)$ work for a window of size $k$.

For a variable-size window, the code can look more intimidating because the left pointer may advance several times after one right movement:

int left = 0;
long windowSum = 0;

for (int right = 0; right < nums.length; right++) {
    windowSum += nums[right];

    while (/* the current window must be shrunk */) {
        windowSum -= nums[left];
        left++;
    }

    // Evaluate the current window in O(1).
}

But the complexity proof is unchanged:

• The for loop advances right exactly $n$ times.
• Every execution of the inner loop advances left.
• left never moves backward and cannot pass the array more than once.
• Thus, all executions of the inner loop together take at most $n$ iterations.

So, provided the window updates and condition checks are $O(1)$, the total is:

$$O(n)$$

Watch this segment of “Sliding Window Technique” by Profound Academy. It visualizes a variable-size window and explicitly connects linear time to each item entering and leaving the window no more than once.

---

When the nested-loop argument is actually quadratic

Monotonicity must hold globally, not just briefly within one loop execution.

This really is quadratic:

for (int start = 0; start < n; start++) {
    int end = 0; // Reset on every outer iteration.

    while (end < n) {
        // Constant-time work
        end++;
    }
}

For every value of start, end travels through all $n$ positions again:

$$n\cdot n=O(n^2)$$

The difference is the reset:

• In a linear sliding window, left preserves its progress while right advances.
• In the quadratic example, end repeatedly returns to zero.

Also, monotonic pointers alone do not guarantee linear total time. You must inspect the work performed per pointer movement.

for (int right = 0; right < n; right++) {
    int sum = 0;

    for (int i = left; i <= right; i++) {
        sum += nums[i];
    }
}

Even if left and right are monotonic, repeatedly scanning the entire current window is not constant work. In the worst case, it can cost $O(n^2)$.

For the pointer-bound proof to establish $O(n)$, these conditions must all be true:

Requirement	Why it matters
Pointers do not move backward	Prevents revisiting positions.
Pointers are not reset inside an outer loop	Prevents repeating a full scan.
Every loop pass advances a pointer or terminates	Ensures progress.
Per-movement work is $O(1)$	Prevents a hidden scan from dominating.
Preprocessing is counted separately	Sorting or building another structure may change total complexity.

A good debugging question when you see nested loops is:

“Can I charge every execution of the inner loop to a distinct pointer movement or distinct array element?”

If the answer is yes, and that movement cannot repeat, you likely have an $O(n)$ aggregate bound.

---

A compact analysis template

Use this template during a timed interview:

“left and right are monotonic. right moves from $0$ to $n-1$ once, so it advances at most $n$ times. Although left is moved in an inner loop, it never moves backward, so all of its movements combined are also at most $n$. Each movement updates the maintained state in constant time. Hence the total pointer-loop time is $O(2n)$, which is $O(n)$, with $O(1)$ auxiliary space unless the algorithm uses additional structures.”

For opposing pointers, substitute the gap argument:

“Each iteration either increments left or decrements right, reducing right - left. Since the initial gap is at most $n-1$, the loop runs at most $n-1$ times, so the scan is $O(n)$.”

---

Key takeaways

• Nested loops are not automatically $O(n^2)$; analyze total work rather than indentation.
• A pointer that moves monotonically across an array can move at most $n$ times.
• For same-direction pointers, total time is often bounded by counting how often elements enter and leave the active range.
• For opposing pointers, the distance $right-left$ is often the cleanest termination and complexity measure.
• The pointer-movement proof requires $O(1)$ work per movement and no hidden pointer resets or repeated range scans.
• Always include costs outside the loop, such as sorting, in the total complexity.

Next, you will make Java comparisons safe in the presence of extreme integer values, including comparators for sorting and priority queues.