When you're standing at a whiteboard in a technical interview, it's easy to let the pressure push you toward the first solution that comes to mind. Usually, that first solution is the "brute force" approach. While it's often good to mention the naive way to show you understand the problem, staying there is a death sentence for your performance metrics. Today, I want to look at two patterns—Two-Pointer and Sliding Window—that turn $O(n^2)$ disasters into $O(n)$ elegances.

The Brute Force Trap

Let's start with a classic: you have a sorted array of integers and you need to find if any two numbers add up to a specific target. If you're thinking in nested loops, you're thinking in $O(n^2)$. You'd take the first element, then iterate through every other element to see if they hit the target. Then you'd take the second element and do it all over again. It works, sure, but it's incredibly wasteful because it ignores the most important piece of information we were given: the array is already sorted.

// The slow way: O(n^2)
for (int i = 0; i < nums.size(); ++i) {
    for (int j = i + 1; j < nums.size(); ++j) {
        if (nums[i] + nums[j] == target) return {i, j};
    }
}

In a real production environment, if that array has 100,000 elements, this code is going to hang your application. You're checking combinations that you already know, logically, can't possibly be the answer.

Shrinking the Search Space

Since the array is sorted, we can use two pointers—one at the very start and one at the very end. This is where the logic shifts from "check everything" to "eliminate the impossible." If the sum of the two pointers is greater than our target, there is no point in moving the left pointer forward, because that would only make the sum even larger. The only way to possibly hit the target is to move the right pointer inward, decreasing the sum. Conversely, if the sum is too low, we nudge the left pointer to the right.

// The optimized way: O(n)
int left = 0;
int right = nums.size() - 1;
while (left < right) {
    int currentSum = nums[left] + nums[right];
    if (currentSum == target) return {left, right};
    if (currentSum < target) {
        left++; // Need a larger value
    } else {
        right--; // Need a smaller value
    }
}

I love this approach because it's intuitive once you see it. We've reduced the complexity from quadratic to linear. We only touch each element at most once. That's the power of the Two-Pointer pattern: using the sorted nature of the data to prune the search space.

Doing the Same Work Twice

Now, let's shift to the "Sliding Window." Imagine you need to find the maximum sum of any contiguous subarray of size $k$. A common mistake is to use a loop that starts at every possible index and then runs another loop to sum the next $k$ elements. If $k$ is large, you're recalculating the sum of the middle elements over and over again. You're essentially treating it like the Two-Sum problem, but the "window" is fixed.

// The wasteful way: O(n * k)
int maxSum = 0;
for (int i = 0; i <= nums.size() - k; ++i) {
    int currentSum = 0;
    for (int j = i; j < i + k; ++j) {
        currentSum += nums[j];
    }
    maxSum = std::max(maxSum, currentSum);
}

If $k$ is 1,000, you're doing 1,000 additions for every single index. That's a lot of wasted CPU cycles for data you already processed in the previous iteration.

Maintaining a Running Total

The trick here is to realize that as the window slides one position to the right, only two things change: one element leaves the window on the left, and one element enters the window on the right. The rest of the sum stays exactly the same. Instead of re-summing everything, we just subtract the element that's falling off and add the new one coming in.

// The sliding window way: O(n)
int currentSum = 0;
for (int i = 0; i < k; ++i) currentSum += nums[i];

int maxSum = currentSum;
for (int i = k; i < nums.size(); ++i) {
    currentSum += nums[i] - nums[i - k];
    maxSum = std::max(maxSum, currentSum);
}

I always tell my juniors to think of this like a camera lens moving across a landscape. You don't need to redraw the whole picture; you just update the edges. This turns a potentially heavy computation into a simple subtraction and addition, regardless of how large $k$ is. Whether your window is 5 elements or 5 million, the cost per slide is constant.

📋 Practical Task

Exercise: Implement the Longest Substring Without Repeating Characters

Write a C++ function int lengthOfLongestSubstring(std::string s) that finds the length of the longest substring without repeating characters.

To do this efficiently, you'll need a dynamic sliding window. Instead of a fixed size $k$, your window should expand by moving a 'right' pointer until you hit a duplicate character. When a duplicate is found, you must shrink the window from the 'left' until the duplicate is removed. Use a std::unordered_set or a frequency array to track which characters are currently inside your window.

Requirements:

• The solution must run in $O(n)$ time.
• Do not use nested loops that restart the search from the beginning of the string.
• Handle edge cases like empty strings or strings where all characters are the same.