From Brute Force to Optimization

Hello. In the previous lesson, you learned to use input constraints as a performance budget: when $n$ can reach $10^5$, an $O(n^2)$ idea is normally too costly, while $O(n)$ or $O(n\log n)$ is a realistic target.

That does not mean you should try to jump directly to a clever solution. This lesson builds the next habit: derive the simplest solution that is unquestionably correct, analyze exactly where it repeats work, and only then choose an optimization. This is how you avoid both blank-page paralysis and “pattern guessing” in interviews.

---

Brute force is a baseline, not a failure

A brute-force solution systematically considers every legal candidate answer and checks whether it satisfies the problem’s condition.

It is not “try random things until something works.” It is a complete, direct method:

1. Define what a possible answer looks like.
2. Enumerate every legal possibility exactly once.
3. Check each possibility against the requirement.
4. Return the required result when a valid possibility is found, or report that none exists.

The method can be slow, but its value is substantial:

• It turns vague English into precise loops, recursion, or state.
• It gives you an immediate correctness baseline.
• It exposes the expensive repeated operation.
• It lets you explain an optimization as a response to a specific bottleneck rather than as a memorized trick.

Sometimes brute force is also the final answer. If $n\le 30$, for example, an $O(n^2)$ pair scan may be completely appropriate. The goal is not “always optimize”; it is “choose an approach justified by the constraints.”

---

Deriving brute force from the problem statement

Consider the classic Two Sum problem:

Given an array nums and a target, return the indices of two different elements whose values add up to the target.

For example:

nums = [4, 5, 2, 3]
target = 8

The valid answer is [1, 3], because nums[1] + nums[3] is 5 + 3, which equals 8.

Do not begin by thinking “hash map.” Begin with the literal condition:

I need two distinct indices $i$ and $j$ such that

$$nums[i]+nums[j]=target$$

A candidate answer is therefore a pair of indices. The direct way to find one is to inspect every pair.

The crucial design detail is that the pair is unordered: checking (0, 1) already checks the same two elements as (1, 0). And an index cannot be used twice, so (2, 2) is illegal even if nums[2] * 2 equals the target.

These two facts give the loop structure:

• Choose a first index $i$.
• Choose a second index $j$ strictly after $i$.
• Test whether the values at those indices sum to the target.

function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return [];
}

The function returns an empty array when no pair exists. Some interview prompts guarantee that a solution exists, in which case the final return [] is unreachable for valid inputs, but keeping it makes the function’s behavior complete.

Why the inner loop begins at i + 1

This one expression, j = i + 1, encodes the legality rules of the problem.

Choice of inner-loop start	Consequence
j = 0	Checks each pair twice and permits the same index when i === j.
j = i	Permits an element to be paired with itself.
j = i + 1	Checks only distinct pairs, and checks each unordered pair once.

For nums = [4, 5, 2, 3], the algorithm checks:

1. Indices (0, 1), (0, 2), and (0, 3)
2. Indices (1, 2) and (1, 3)
3. Indices (2, 3)

That is every legal pair, once each.

This simple derivation also handles duplicates correctly. With:

nums = [3, 3]
target = 6

the algorithm tests indices (0, 1) and returns them. The values are equal, but the indices are distinct, which is exactly what the problem requires.

---

Analyze the baseline before trying to improve it

Once the brute-force solution is clear, measure it.

For an array of length $n$, the number of distinct pairs is:

$$\frac{n(n-1)}{2}$$

That quantity grows proportionally to $n^2$, so the time complexity is:

$$O(n^2)$$

The function uses only the loop variables i and j plus a few temporary values. Its auxiliary space is:

$$O(1)$$

We normally exclude the returned answer itself from auxiliary-space analysis.

An early return can make some inputs fast. If the first pair works, the function stops almost immediately. But complexity is usually stated in the worst case. If no pair exists, or the matching pair appears near the end of the enumeration, the code performs nearly all pair checks.

For the $n\le 10^5$ scale from the previous lesson:

$$\frac{100000\cdot 99999}{2}\approx 5\cdot 10^9$$

So brute force is correct, easy to reason about, and unacceptable at that scale. All three statements can be true at once.

---

Find the repeated work

Optimization should answer a concrete question:

What does the brute-force version keep doing again and again?

In Two Sum, once we choose nums[i], the condition determines the only value we need:

$$needed=target-nums[i]$$

But the brute-force code looks through many other array positions to determine whether that required value exists. It repeats a search through part of the array for each choice of i.

In the brute-force method	What it costs	Information an optimization needs
Choose a first value	One outer-loop iteration	The current value and its index
Search other positions for a partner	Up to $O(n)$ work for each first value	Whether the needed complement has already appeared
Repeat for many first values	Total $O(n^2)$ work	Fast membership lookup

This is the bridge from the baseline to an optimization. You are not yet required to write the improved solution, but you can now describe the direction precisely:

• Store information about values already seen.
• For each current value, calculate its complement.
• Check whether that complement is already stored.
• Preserve the original index so you can return indices, not merely values.

A hash-based lookup structure supports this efficiently, at the cost of extra memory. In JavaScript, that will be a Map when you need to retain indices or a Set when you only need existence. You will implement these tools later; for now, recognize the reasoning that makes them relevant.

There is another possible direction: sort the values and use a disciplined scan from opposite ends. That reduces the pair search after sorting, but sorting costs $O(n\log n)$, can mutate the input unless copied, and loses original positions unless you retain each value’s index. The “best” optimization therefore depends on the required output and allowed trade-offs.

The important sequence is:

1. Brute force establishes the complete candidate space.
2. Complexity shows the baseline misses the performance target.
3. Repeated work identifies the information you need to retain or exploit.
4. The problem’s requirements decide which optimization preserves correctness.

---

Brute force is broader than nested loops

Two Sum is a pair-enumeration problem, so its direct version uses nested loops. Other problems have different candidate spaces.

Problem shape	Candidate answer	Typical brute-force enumeration
Find a pair with a property	Two indices	Every pair with $i<j$
Find a contiguous subarray	Start and end positions	Every valid start/end boundary pair
Choose some elements	A subset	Include or exclude each element
Arrange all distinct items	A permutation	Try every ordering
Find a path through choices	A sequence of moves	Recursively explore every legal next move

The common structure remains the same: make the candidate explicit, generate every legal candidate, and validate it.

For example, if a prompt asks for the longest contiguous subarray satisfying a property, a natural baseline is:

• choose each possible start position;
• choose each possible end position at or after that start;
• examine whether the resulting subarray is valid;
• track the best valid length.

That may lead to $O(n^2)$, $O(n^3)$, or worse depending on the cost of validating each subarray. The value of deriving it is that you can point to the exact operation an optimization must avoid: repeatedly recomputing information about overlapping ranges.

---

A repeatable interview routine

Before naming a familiar technique, use this compact routine:

1. State the witness. Identify what proves an answer exists: a pair, interval, path, subset, index, or value.
2. Describe exhaustive enumeration. Specify exactly how you would generate every legal witness.
3. Prevent invalid duplicates. Use constraints such as $i<j$, a visited set, or a start boundary to avoid repeated or illegal candidates.
4. Write the validation condition. State the exact test that makes a candidate valid.
5. Give the baseline complexity. Relate the number of candidates and cost per validation to the input constraints.
6. Name the repeated work. This is the only part you should try to eliminate.
7. Select an optimization that preserves the contract. Make sure it still handles distinct indices, duplicates, input mutation rules, and the required output format.

A concise interview explanation for Two Sum might sound like this:

“The direct solution checks every distinct index pair. I use an outer index and an inner index beginning at the next position, so every unordered pair is checked once and no element is reused. This is $O(n^2)$ time and $O(1)$ auxiliary space. With large $n$, the repeated work is scanning for the complement of each value, so I would use a fast lookup structure to avoid those repeated scans.”

This communicates correctness, complexity awareness, and a grounded reason for optimizing.

---

Key takeaways

A brute-force solution is a systematic proof-of-concept: it enumerates every legal candidate and checks the literal problem condition. For Two Sum, that means every pair of distinct indices with $i<j$, implemented using nested loops.

From there:

• The number of pairs is $\frac{n(n-1)}{2}$, giving $O(n^2)$ worst-case time.
• Starting j at i + 1 prevents self-pairing and duplicate pair checks.
• An optimization should be driven by the repeated work in the baseline, not selected by pattern memorization.
• Brute force may be the final solution when constraints are small enough.

Next, you will make this analysis more mechanical: determine the time and auxiliary-space complexity of JavaScript code containing loops and recursion.