Skip to content
Brute force first

Lesson 3.4

Spot repeated work

7 min · 7 steps

  1. Step 1 of 7 · Explanation

    Problem: "Return an array where out[i] is the sum of nums[0] through nums[i]."

    The brute force adds everything up again from the start for each i, with an inner j loop from 0 to i. For [3, 1, 4, 2], out[2] computes 3 + 1 + 4 from zero, even though 3 + 1 was already worked out for out[1]. Each round redoes the additions the previous round already did.

  2. Step 2 of 7 · Predict the result

    How many additions happen for 4 items?

    function solution(nums) {  let adds = 0  for (let i = 0; i < nums.length; i++) {    for (let j = 0; j <= i; j++) {      adds++    }  }  return adds}
    1. 10
    2. 4
    3. 16

  3. Step 3 of 7 · Pick the approach

    A brute force running sum: the outer loop i visits every item. Inside it, sum starts at 0, a j loop adds nums[0] through nums[i], then out.push(sum).
    What work keeps getting repeated?

    1. Adding up nums[0] through nums[i - 1] again, when the previous round already had that sum
    2. out.push(sum) on every round
    3. The outer loop i
    4. Reading nums.length

  4. Step 4 of 7 · Arrange the code

    Build the O(n) running sum, where out[i] is the sum of nums[0] through nums[i]. Keep the sum so far. Two lines don't belong.

    return outsum += nums[i]out.push(sum)}const out = []}for (let i = 0; i < nums.length; i++) {let sum = 0function solution(nums) {sum = nums[i]for (let i = 1; i < nums.length; i++) {

  5. Step 5 of 7 · Pick the approach

    Another brute force: "For each i, use an inner loop to check whether nums[i] appeared earlier." That's O(n²).
    What can answer "seen it before?" in one step?

    1. A Set or Map that stores every number you've passed
    2. Re-sort the array on every round
    3. An inner loop with j = i + 1
    4. One variable holding the previous number

  6. Step 6 of 7 · Predict the result

    What does it return for [5, 3, 5, 3]?

    function solution(nums) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    if (seen.has(nums[i])) {      return [seen.get(nums[i]), i]    }    seen.set(nums[i], i)  }  return []}
    1. [0, 2]
    2. [1, 3]
    3. [2, 0]
    4. []

  7. Step 7 of 7 · Recap

    • Once the brute force works, look for an inner loop that recomputes something.
    • Keep the result so far, like a running total, so it's never recounted.
    • "Seen it before?" can be answered in one step with a Set or Map.

    Pattern card

    Repeated work
    When to use it: When your brute force is right but too slow. Ask: what does the inner loop compute that you already knew?
    let sum = 0for (const x of nums) {  sum += x      // simpan / keep it  out.push(sum)}