Road to Genius: advanced #30

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function canJump(nums) {
  let max = 0; 
  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; 
      max = Math.max(nums[i] + i, max);
  }
  return max >= nums.length - 1
}

let A = canJump([5,0,0,6,4,6]);

// A = ? (boolean)

This challenge's code is pretty short, let's see what it's all about. We have to figure out A's boolean value:
let A = canJump([5,0,0,6,4,6]);

On first sight I have no clue what the function canJump does, so we'll have to analyze it more closely.

for (let i = 0; i < nums.length; i++) {
    if (max < i) return false; 
    max = Math.max(nums[i] + i, max);
}

These three lines of code are doing the following: iterating over each number in the array nums; checking if max is lesser than i, if so the function immediately returns falsely; finally it determines the new max value. The if-condition actually ensures that the max jump size is greater than current index i of the for-loop.

This algorithm is actually about determining if it's able to "jump" to a certain position, where each number represents the max jump length.

The last line of code reveals its final condition:
return max >= nums.length - 1
It checks if max is greater or equal to nums' array size, meaning this whole algorithm checks if one can reach the end of the array starting at the first index.

Below is some pseudo-code to illustrate this:

nums = [5, 0, 0, 6, 4, 6]

-> i = 0
   nums[i] = 5
   max = max(5+0, 0) = 5
   * from this index, we can jump max 5 positions further

-> i = 1
   nums[i] = 0
   max = max(0+1, 5) = 5
   * if we jump to here, we cannot jump any further (= 0)

-> i = 2
   nums[i] = 0
   max = max(0+2, 5) = 5
   * if we jump to here, we cannot jump any further (= 0)

-> i = 3
   nums[i] = 6
   max = max(6+3, 5) = 9
   * if we jump to here, we can jump max 6 positions further

-> i = 4
   nums[i] = 4
   max = max(4+4, 9) = 9
   * if we jump to here, we can jump max 4 positions further

-> i = 5
   nums[i] = 6
   max = max(6+5, 9) = 11
   * if we jump to here, we can jump max 6 positions further

This challenge is pretty trivial and in our favor, because we can reach the end of the array (i = 5) from the very first index; because the first number is 5.

We can even optimize this algorithm a lot by doing the following:

function canJump(nums) {
  let max = 0; 
  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; 
      else if (max >= nums.length - 1) return true;
      max = Math.max(nums[i] + i, max);
  }
  return max >= nums.length - 1
}

let A = canJump([5,0,0,6,4,6]);

The additional else-statement makes the function return much sooner if it detects that the end can be reached, so it doesn't have to iterate over all numbers.

An alternative way of writing this code is this:

function canJump(nums) {
  let max = 0; 
  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; 
      max = Math.max(nums[i] + i, max);
      if (max >= nums.length - 1) return true;
  }
  return false;
}

let A = canJump([5,0,0,6,4,6]);

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Join me on the Road to Genius and upgrade your programming skills, at https://nevolin.be/codr/