Every Optimization Starts With One Question

Not "what data structure should I use?" Not "what is the time complexity?" One question comes before all of those, and the answer to it is the optimization.

There is a pattern behind almost every meaningful optimization in coding interviews, and once you see it, you will find it everywhere.

Not in the solution, but in the question that produces the solution.

Here it is: where am I doing the same work more than once?

That is the question.

Not “what is the clever trick?”

Not “which algorithm applies?”

Those come after.

First comes this question, applied honestly to whatever slow solution you already have, and the answer to it tells you exactly what to fix and how.

This is not a motivational framing. It is a mechanical description of how almost every O(n squared) to O(n) improvement happens, how memoization works, how sliding windows work, how prefix sums work, how hash maps replace nested loops.

Every one of these optimizations is the same move: find the repeated work, find a way to do it once and reuse the result, watch the complexity collapse.

This post walks through four concrete cases that prove it, shows you the question applied to each, and then explains how to train the habit so it becomes automatic in an interview.

The Question (precisely stated)

Before the examples, get the question exactly right, because the exact form matters.

“Where am I doing the same work more than once?” has two parts.

The first is where: find the specific computation that is being repeated.

The second is the same work: it has to be identical computation, not just similar computation.

If two loop iterations do different calculations on different data, that is not repeated work.

If they make the same comparison, recompute the same running total, or re-scan the same already-seen elements, that is.

The question is not “how do I make this faster?”

That is too vague to generate a useful answer.

“Where am I repeating myself?” is specific enough to point at a location in the code and a computation to cache. It turns an open-ended optimization problem into a focused search for a specific thing, and that focus is what makes it consistently useful under pressure.

Case 1: The duplicate check (O(n squared) to O(n))

Start with something simple. You have an array and you want to know whether it contains any duplicates.

The obvious approach checks every pair:

python

def has_duplicate_brute(a):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

This is O(n squared). Now apply the question: where is the repeated work?

At every step of the outer loop, you are re-scanning all the later elements to check whether any of them match the current one. But more precisely: you are asking “have I seen this value before?” on every element, using a fresh search each time.

The repeated work is that search. Every element asks the same question, and every time it has to re-examine what came before.

The fix is immediate once you see the repetition. Instead of scanning backward, remember what you have seen. A set answers “have I seen this?” in O(1):

python

def has_duplicate_set(a):
    seen = set()
    for x in a:
        if x in seen:
            return True
        seen.add(x)
    return False

One pass.

The repeated search is gone, replaced by a lookup that costs nothing.

The question identified the problem; the hash set was just the cheapest tool to fix it.

Case 2: The sliding window (O(n times k) to O(n))

Find the maximum sum of any K consecutive elements.

The naive approach re-sums each window from scratch:

python

def max_sum_brute(a, k):
    best = float('-inf')
    for i in range(len(a) - k + 1):
        best = max(best, sum(a[i:i+k]))   # re-sums k elements each time
    return best

This is O(n times k). For large k, it is nearly O(n squared).

Apply the question: where is the repeated work?

Look at what happens when the window moves one position. You drop the element that fell off the left and gain the one that entered from the right. Everything in between was in both windows.

The sum of those middle elements is being recomputed identically in consecutive iterations. That is the repeated work.

The fix: do not recompute the sum. Keep it running and update it by adding the entering element and subtracting the leaving one:

python

def max_sum_window(a, k):
    window = sum(a[:k])
    best = window
    for i in range(k, len(a)):
        window += a[i] - a[i - k]    # add entering, subtract leaving
        best = max(best, window)
    return best

O(n).

The entire sliding window pattern is this one move: instead of recomputing a window’s property from scratch, update it incrementally.

The question found the repeated computation; the incremental update removed it.

Case 3: Memoization (exponential to linear)

Compute the nth Fibonacci number recursively:

python

def fib_slow(n):
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

This is exponential. Computing fib(20) makes over 21,000 recursive calls. Apply the question: where is the repeated work?

fib(n) calls fib(n-1) and fib(n-2). But fib(n-1) also calls fib(n-2). And fib(n-2) calls fib(n-3), which fib(n-1) also called.

The same subproblems are computed over and over, independently, with no memory of prior results. Every branch of the recursion tree re-derives the same values from scratch.

The repeated work is computing a subproblem that was already computed elsewhere in the tree.

The fix is to remember: compute each subproblem once and store the result:

python

def fib_fast(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_fast(n - 1) + fib_fast(n - 2)
    return memo[n]

Now fib(20) makes roughly 40 calls instead of 21,000. That is what memoization is, not a trick, not a data structure, but the answer to “where am I solving the same subproblem more than once?” applied to a recursive computation. Every dynamic programming problem is this pattern at larger scale.

Case 4: Prefix sums (O(n) per query to O(1) per query)

You have an array and receive many range-sum queries: “what is the sum of elements from index i to j?” The naive answer recomputes each range:

python

def range_sum_brute(a, i, j):
    return sum(a[i:j+1])     # O(j - i + 1) per query

For many queries over a large array this is slow.

Apply the question: where is the repeated work?

Every query scans some portion of the array. Many queries will scan overlapping portions.

The sum of elements from index 2 to 8 is computed again when you query 0 to 8 and subtract 0 to 1.

The overlapping partial sums are the repeated work.

The fix: precompute all prefix sums once, then answer any query as a single subtraction:

python

def build_prefix(a):
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    return pre

def range_sum_fast(pre, i, j):
    return pre[j + 1] - pre[i]    # O(1) per query

Pay once to build the prefix array, answer every subsequent query in O(1).

The repeated work was partial sums computed fresh on each query; the fix moved that work to a single upfront pass.

The Pattern Underlying All Four

Look at what the four cases have in common. In every one, the brute-force solution has an inner loop or a recursive call that re-does work the outer loop already did.

In every one, the optimization is to extract that repeated work, do it once, and store the result for instant reuse. In every one, the complexity improvement is dramatic, not a constant-factor speedup but an order-of-magnitude change.

The tools used to store the result differ: a hash set in case one, a running sum in case two, a memo dictionary in case three, a precomputed array in case four. But these are just the cheapest available containers for each kind of repeated work.

The optimization logic in all four cases is identical: find the repeated computation, store its result, retrieve it in O(1).

This is why the question matters more than the answer.

Once you have identified the repeated work, the right data structure to cache it is usually obvious.

A repeated membership check stores in a set or hash map.

A repeated sum stores as a running total. A repeated subproblem stores in a memo table.

The choice of tool is downstream of the diagnosis, not upstream of it.

Why this Matters Specifically in Interviews

In an interview, you are expected to optimize.

“Can you make it faster?” is among the most common follow-up questions after a working brute-force solution.

Most candidates hear this and freeze, because they have not built a reliable method for finding optimizations and are waiting for inspiration.

The question gives you a method.

When the interviewer asks “can you make it faster?”, your next move is not to think about data structures or algorithms in the abstract. It is to look at your current solution and ask, out loud, “where is this doing the same computation more than once?”

Then trace through a small example and watch for any step that re-examines data the previous iteration already processed.

This narration does two things simultaneously. It gives you a systematic way to find the optimization rather than waiting for it to appear. And it makes your reasoning visible to the interviewer, which is part of what is being graded.

An interviewer who hears “the inner loop is re-scanning elements the outer loop already saw, so if I remember what I’ve seen in a hash set I can remove the inner loop entirely” is hearing exactly the kind of thinking they are looking for, regardless of whether you arrived at it in ten seconds or two minutes.

The brute force is not something to be embarrassed about. It is the starting point from which the optimization becomes visible. You cannot apply the question without a slow solution to apply it to.

State the brute force clearly, trace through it, find the repetition, and the optimization surfaces.

The Sub-questions that Help

The main question (”where am I doing the same work more than once?”) is usually enough. When it is not, two sub-questions narrow the search.

Am I scanning something I already scanned?

If the brute force has a nested loop where the inner loop rescans part of the array the outer loop already processed, the fix is almost always a hash map, a running value, or a pointer. The inner loop is the repeated work, and the tool is whatever stores the result of one pass in a form the next step can use in O(1).

Am I solving a subproblem I already solved?

If the brute force is recursive and the call tree has the same inputs appearing multiple times, the fix is almost always memoization or bottom-up DP. The repeated subproblem is the work; the memo table is the cache.

Almost every interview optimization falls under one of these two. Recognizing which one applies tells you what kind of cache to reach for, and that is usually all you need to implement the solution.

A Note on What this Question Does Not Solve

The honest version: not every optimization comes from eliminating repeated work.

Some improvements come from choosing a different algorithmic approach entirely (a divide-and-conquer where you had a greedy, a sort where you had a scan, a mathematical shortcut where you had an iterative computation).

Some improvements come from reducing unnecessary memory allocation or improving cache behavior in a way that does not change the asymptotic complexity.

And some problems are already optimal and the interviewer is testing whether you recognize that.

The question is not universal. It is a highly reliable first move, the right place to look before anywhere else, because the repeated-work pattern covers such a large fraction of the optimizations that matter in interviews.

When it does not apply, you will know, because an honest search for the repetition will come up empty, and that itself is useful information about where to look next.

Frequently asked questions

Why start with the brute force instead of jumping to the optimal solution?

Because the optimal solution is hard to see from nothing and easy to see from the brute force. The repeated work is invisible until you have a concrete slow solution to look at. The brute force is not a detour to the optimization; it is the mechanism that reveals it.

What if I can not find the repeated work?

Trace through a small example step by step and ask at each step: “has this exact calculation happened before in this execution?” If yes, you have found it. If not after a thorough trace, the optimization might not follow from this question, and that is useful to know.

Does this work for all complexity improvements?

It works reliably for the most common class: improvements that involve storing a previously computed result so it does not have to be recomputed. This covers hash maps replacing inner loops, memoization, sliding windows, prefix sums, and caching of all kinds. It does not cover algorithmic restructuring or greedy insights, which require different questions.

How do I practice this?

On every brute-force solution you write, before looking for the optimization, apply the question explicitly and trace the answer. Over time, the repeated-work pattern becomes recognizable by sight without needing the trace. That automatic recognition is the goal.

Is this the same as memoization?

Memoization is one specific application of the principle: cache a recursive subproblem’s result so it is not recomputed. The broader principle applies to non-recursive repeated work too, as cases one and two show. Memoization is where “where am I doing the same work more than once?” meets recursion.

The Bottom Line

Almost every optimization that matters in coding interviews is the answer to one question: where am I doing the same work more than once?

The brute force re-scans, recomputes, or re-solves something it has already handled.

The optimization identifies that repetition and removes it, storing the result of the first computation in whatever form makes the second retrieval O(1).

The tools vary: hash sets and maps for membership and lookup, running values for sums and counts, memo tables for recursive subproblems, prefix arrays for range queries. But the question is always the same, and the answer to it is always the optimization.

Learn the question, apply it to every slow solution you write, and the clever trick stops being something you wait for and becomes something you find.

---

Which optimization surprised you most when you first understood why it worked?