Skip to content
Brute force first

Lesson 3.3

Read the constraints

6 min · 7 steps

  1. Step 1 of 7 · Explanation

    Constraints quietly tell you how fast your solution must be. Use a budget of about 10⁸ simple steps per second, then look at the limit on n.

    • n ≤ 10³: O(n²) is fine, about 10⁶ steps.
    • n ≤ 10⁵: you need O(n) or O(n log n).
    • n ≤ 10⁹: even one loop is too slow. Find a formula, or O(log n).

  2. Step 2 of 7 · Pick the approach

    "Return how many pairs add up to target." Constraints: 2 ≤ nums.length ≤ 1000.
    Is brute force over every pair enough?

    1. Yes, about 5 × 10⁵ checks, well under budget
    2. No, nested loops are always too slow
    3. No, you must use a hash map to be safe

  3. Step 3 of 7 · Pick the approach

    "Return how many pairs add up to target." Constraints: 2 ≤ nums.length ≤ 10⁵.
    What do you do?

    1. Find an O(n) or O(n log n) way, like a hash map or sorting first
    2. Still brute force, but stop early when you find one
    3. Brute force with j = i + 1 to halve it

  4. Step 4 of 7 · Pick the approach

    "Return 1 + 2 + ... + n." Constraints: 1 ≤ n ≤ 10⁹. What's the right choice?

    1. The formula n * (n + 1) / 2, one step
    2. A loop from 1 to n
    3. Store every number in an array, then add them up

  5. Step 5 of 7 · Predict the result

    What does it return for n = 100?

    function solution(n) {  return n * (n + 1) / 2}
    1. 5050
    2. 10100
    3. 5000

  6. Step 6 of 7 · Find the bug

    "Return the largest number, or 0 if the array is empty." Constraints: 0 ≤ nums.length ≤ 10⁵.
    For [], this code returns undefined. Tap the wrong line.

    function solution(nums) {  let best = nums[0]  for (let i = 1; i < nums.length; i++) {    if (nums[i] > best) best = nums[i]  }  return best}

  7. Step 7 of 7 · Recap

    • Budget about 10⁸ steps per second. Compare that with your solution's step count.
    • n ≤ 10³ allows O(n²). n ≤ 10⁵ needs O(n log n) or O(n). n ≤ 10⁹ needs a formula or O(log n).
    • The lower bound matters too. 0 ≤ length means the empty array will be tested.

    Pattern card

    Constraints set the speed
    When to use it: After reading the problem, before choosing an approach. The upper bound gives the speed, the lower bound gives the edge cases.
    // n ≤ 10³  -> O(n²)// n ≤ 10⁵  -> O(n log n), O(n)// n ≤ 10⁹  -> O(log n), O(1)