Brute-Force Solutions and Performance Bottlenecks

Hello! You’ve already agreed on a contract for two-sum and built tests for empty inputs, duplicates, negative values, missing solutions, and pairs at the ends of the vector. Those tests give you a way to check an algorithm; they do not yet tell you which algorithm to write.

Today you’ll derive a brute-force baseline: a direct solution that considers every possible pair. You’ll establish why it is correct, implement it in C++, and identify precisely which work makes it slow on large inputs. In a coding interview, a sound baseline is useful even when you expect to improve it later.

Turn the manual method into an algorithm

Suppose you have nums = [8, 1, 4, 6] and a target of 10. Without code, you might pair 8 with each later value, then pair 1 with each value after it, and continue until you find 4 + 6. That is already a procedure you can implement.

The Tech Interview Handbook describes this move from a manual procedure to a working initial solution:

For our agreed two-sum contract, a candidate answer is a pair of distinct, increasing indices $(i,j)$ such that $0\le i<j<n$, where $n$ is the vector length. A candidate succeeds when nums[i] + nums[j] equals the target. The most direct complete procedure is therefore to test all such candidates until one succeeds.

Why insist on $j>i$? It prevents using one element twice and avoids testing both $(i,j)$ and $(j,i)$. It also gives the required increasing index order automatically. If no candidate succeeds, the agreed output is (-1, -1).

See the pair search, then implement it

Watch NeetCode’s Two Sum - Leetcode 1 - HashMap - Python for its visual account of the direct search. The video assumes exactly one solution exists; our contract does not. Keep the pair-checking method, but retain our required (-1, -1) result when there is no pair and allow either valid answer when several exist.

Here is that procedure in C++ under our contract:

#include <utility>
#include <vector>

std::pair<int, int> twoSumBruteForce(
    const std::vector<int>& nums, int target) {
    const int n = static_cast<int>(nums.size());

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            const long long sum =
                static_cast<long long>(nums[i]) + nums[j];

            if (sum == target) {
                return {i, j};
            }
        }
    }

    return {-1, -1};
}

The outer loop chooses the first index; the inner loop tries every later second index. Starting j at i + 1 is the important boundary decision. When the vector has zero or one element, the inner body never runs, so the function returns (-1, -1) without accessing an invalid index. The const reference avoids copying or modifying the input.

The conversion to long long happens before addition. Two valid int values can have a mathematical sum outside the int range; adding them as int could cause signed overflow. Under our agreed maximum vector length of 100,000, converting nums.size() to int is safe for the indices used here.

Trace the code on [8, 1, 4, 6] with target 10. It tries sums of 9, 12, and 14 with i = 0; then 5 and 7 with i = 1; finally 10 with (i, j) = (2, 3). The return value is (2, 3), matching the endpoint test from your previous lesson.

The correctness argument is short but important. Whenever the function returns (i, j), the loop bounds guarantee $i<j$, and the condition guarantees the values sum to the target. If it reaches the final return instead, the loops have tested every distinct pair in increasing index order, and none matched. Thus both kinds of return satisfy the contract.

Count the work that limits performance

A nested loop does not, by itself, give a precise account of this code. For i = 0, the inner loop can test $n-1$ pairs. For i = 1, it can test $n-2$. The counts continue down to one, giving

That count applies when no pair succeeds; an early match stops the search sooner. Each test performs a constant amount of work, so worst-case time is $\Theta (n^2)$, commonly stated in interviews as $O(n^2)$. If (0, 1) is a solution, this implementation can return after one test, but that favorable case does not change its worst-case classification.

At the agreed maximum of 100,000 elements, a no-solution input makes the code test 4,999,950,000 pairs. No particular runtime follows from that number alone—it depends on the machine and execution environment—but it makes the source of the scaling problem concrete.

The bottleneck is the number of candidate pairs, not an unusually expensive addition. Each sum takes constant time, but each index may have to be checked against many later indices. Avoiding reversed pairs cuts unnecessary work, yet it still leaves roughly half of $n^2$ checks. It does not change the quadratic growth class.

The function’s auxiliary space is $O(1)$: beyond the input, it stores a few variables and one fixed-size return value. This is a useful trade-off statement: the baseline uses little extra memory but may take substantial time.

Recognize the same reasoning in another brute-force solution

“Try every candidate” is a starting principle, not a promise that every brute-force algorithm is quadratic. You must also ask how much work it takes to check one candidate.

CodePath’s minimum-size subarray example provides a contrast. Its direct method considers every contiguous subarray, then calculates each subarray’s sum. Read only its baseline; its later improvements belong to future pattern lessons.

There are quadraticly many possible subarrays because each is selected by a start and an end position. In CodePath’s initial method, checking one of them may require walking through up to $n$ values to calculate its sum. That produces $O(n^3)$ worst-case time. In our two-sum code, there are also quadraticly many candidates, but checking a pair reads just two values and adds them, so the total is $O(n^2)$.

This distinction is a practical way to diagnose a baseline. Describe what you enumerate, how you evaluate each candidate, and which of those operations repeats enough to dominate runtime. For two-sum, the repeated work is searching across many possible partners. We do not recompute the sum of the same unordered pair: the $j>i$ rule already prevents that.

State the baseline clearly

You now have enough to explain the approach without jumping prematurely to an optimization:

“I’ll check each pair of distinct indices once, returning the first pair whose values sum to the target. If none matches, I’ll return (-1, -1). This covers all valid pairs, takes $O(n^2)$ worst-case time and $O(1)$ auxiliary space. Its bottleneck is the number of partner checks on large inputs.”

That statement connects the contract, correctness, and performance. Your earlier tests then check the implementation against the contract—for example, [4, 4] confirms that equal values at different indices work, while a one-element vector confirms that the same index is never used twice.

Takeaways

A brute-force solution begins with a complete set of candidate answers and a reliable way to check each one. For two-sum, increasing index pairs give a correct, compact C++ baseline. Its repeated partner checks produce $O(n^2)$ worst-case time; its extra memory stays $O(1)$. Counting candidates and the cost of checking each one lets you locate a bottleneck rather than merely labeling code “slow.”

Next, you’ll begin working with unordered_map to count frequencies and retrieve matching elements—tools that will give you new options when repeated searches become costly.