FOR LOOP, a (almost) guaranteed, "brute force" solution

This tutorial is a part of the Data Structures and Algorithms class:

• Why is FOR LOOP a (almost) guaranteed solution?
• Single FOR LOOP lists all possible options
• Nested FOR LOOPs lists all possible subsets
• FOR LOOP is usually a "brute force" solution

Why is FOR LOOP a (almost) guaranteed solution?

• FOR LOOP lists all available options.
• Once you have all available possibilities, you can pick the one asked for.
• Top 4/5 classes: 1. max, 2. min, 3. find all options, 4. find the most optimal solution -> can be solved by listing out all possibilities and picking the suitable one.

Single FOR LOOP lists all possible options

Single FOR LOOP gives you all available options. Then you can pick the one you need. Time complexity O(n).

// Find max element in given array
const arr = [2, 4, 3, 9, 1]

const findMax = arr => {
  let curMax = arr[0]

  for(let i = 0; i < arr.length; i++) {
    console.log(`arr[${i}]:`, arr[i])
    ;(arr[i] > curMax) && (curMax = arr[i])
  }

  return curMax
}

console.log(findMax(arr)) // 9

$ node single-for-loop.js
arr[0]: 2
arr[1]: 4
arr[2]: 3
arr[3]: 9
arr[4]: 1
9

Nested FOR LOOPs lists all possible subsets

Nested FOR LOOPs lists all possible subsets containing k elements. With k is the number of for loops. Then you can pick the subset you need. Time complexity O(n^k).

// Find subset of 3 elements, whose sum equals 15
const arr = [2, 4, 3, 9, 1]

const findSubArray3 = (arr, sum) => {
  const result = []

  for(let i = 0; i < arr.length - 2; i++) {
    for(let j = i+1; j < arr.length - 1; j++) {
      for(let m = j+1; m < arr.length; m++) {
        console.log(`subset: [${[arr[i], arr[j], arr[m]]}]`)
        ;(arr[i] + arr[j] + arr[m] == sum) && result.push([arr[i], arr[j], arr[m]])
      }
    }
  }

  return result
}

console.log(findSubArray3(arr, 15)) // [ [ 2, 4, 9 ] ]

$ node nested-for-loops.js
subset: [2,4,3]
subset: [2,4,9]
subset: [2,4,1]
subset: [2,3,9]
subset: [2,3,1]
subset: [2,9,1]
subset: [4,3,9]
subset: [4,3,1]
subset: [4,9,1]
subset: [3,9,1]
[ [ 2, 4, 9 ] ]

FOR LOOP is usually a "brute force" solution

• Why call it brute force? Because it's bluntly straight forward: just list all options, then pick the suitable one. It's simple to understand and easy to implement.
• But nested FOR LOOPs is expensive in terms of CPU time, O(n^k) with k nested loops.
• Note: listing all options and choosing the suitable one is actually how software solves many classes of problem. You'll see that better algorithms will try not to visit unmeaningful options, hence more CPU efficient.

// Given sorted array of integers, find the index of number `65`
[1, 2, 4, 7, 9, 15, 21, 23, 34, 42, 48, 59, 60, 65, 70]

// FOR LOOP: O(n) -> loop through all options.
// Binary search: O(logn) -> much faster, does not visit unmeaningful options.

Real life interview questions

1. In term of human language, what does FOR LOOP offer?
2. In term of human language, what does nested FOR LOOP offer?
3. What is a brute force solution and why is it called brute force?
4. Why can we think of FOR LOOP as an almost guaranteed solution for many classes of software problem?
5. Find4: given an array of integers and a number sum, find the first subset of 4 numbers which sums up to sum. Ex: array: [1, 3, 4, 5, 6, 2], sum: 10 -> answer: [1, 3, 4, 2]. Optional challenge: can you do it better than O(n^4)?
6. 4x4 sudoku solver: create a solution for a 4x4 sudoku.
7. Leetcode #509: Fibonacci number
8. Leetcode #344: Reverse String
9. Leetcode #394: Decode String
10. Leetcode #206: Reverse Linked List
11. Leetcode #203: Remove Linked List Elements
12. Leetcode #234: Palindrome Linked List
13. Leetcode #125: Valid Palindrome