Brute Force and When to Stop

Brute force is not an insult. It is the algorithm that enumerates the search space the statement already named: every pair, every subarray, every index. The amateur mistake is writing it when n is 2·10⁵. The expert mistake is *not* writing it when n is 2·10³ and the clock is running.

From the constraints lesson: about 10⁸ primitive operations per second. n ≤ 2·10³ makes n² ≈ 4·10⁶. That is cheap in C++ and comfortable in JavaScript. n ≤ 5·10³ is usually fine. n ≤ 10⁴ is the borderline where a heavy inner body starts to TLE. n ≤ 2·10⁵ means you do not open a second loop over n.

Every unordered pair — Θ(n²) iterations, i < j so you do not double-countjs

function allPairs(a) {
  const n = a.length;
  const pairs = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      pairs.push([a[i], a[j]]);
    }
  }
  return pairs; // n(n-1)/2 pairs
}

The inner start j = i + 1 is the whole convention. j = i includes a pair with itself. j = 0 with a skip on j === i still visits every ordered pair (i, j) and (j, i) — twice the work, and wrong if the problem asked for unordered pairs. Ordered pairs (i, j) with i ≠ j are n(n-1). Subarrays [l..r] inclusive are n(n+1)/2 choices of endpoints, which is still Θ(n²) to *list*, and Θ(n³) if you rescan each subarray naively.

That last sentence is the other time people TLE: they generate O(n²) ranges and then loop the range. Generating endpoints is legal at n = 2·10³; summing each range from scratch is O(n³) ≈ 8·10⁹. Prefix sums (next lesson) turn the inner scan into a subtraction.

CHECK

n ≤ 2000, time limit 2s. You need the number of pairs (i < j) with a[i] + a[j] equal to k. Values up to 10⁹. Which is a legal first submission?

TRACE

a = [2, 4, 5, 8] (already sorted). Count pairs with sum ≤ 9. Inner loop may break once the sum is too big.

i = 0 (2)

j = 1: 2+4=6 ≤ 9, count=1. j = 2: 2+5=7 ≤ 9, count=2. j = 3: 2+8=10 > 9, break. Further j only grow.

count = 2, pruned j = 3

1 / 4

Prune a sorted inner loop — still O(n²) worst casejs

function countSumAtMost(a, k) {
  const b = [...a].sort((x, y) => x - y);
  const n = b.length;
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (b[i] + b[j] > k) break;
      count++;
    }
  }
  return count;
}

CHECK

You need the mode of an array (most frequent value; ties → smaller value). n ≤ 10⁵, values in [−10⁹, 10⁹]. A teammate writes, for each i, a scan that counts how often a[i] appears. What do you do?

A working stop-rule:

- n ≤ 20 — exponential enumeration, including 2ⁿ and n·2ⁿ. Meet-in-the-middle if 2ⁿ is fat and n ≈ 40. - n ≤ 2·10³ — generate pairs / subarray endpoints. Nested loops are the default. - n ≤ 2·10⁵ — stop the second n-loop before you type it. Hash, sort, pointers, prefixes.

Play Complexity Clash until naming the nest is a reflex. Then solve Frequency Mode: it is the hashing replacement for the quadratic count, not a new idea.

Checks 0/2

Next lesson