Hopper Tower Problem using Dynamic Programming

Write a function to determine whether a person can reach the other end of the array if he starts at index 0 and if he cannot hop more than the value contained at that index.

var jumper = [];
var arr = [4, 0, 0, 1];

function hopper(index) {
  if (index + arr[index] >= arr.length) {
    jumper[index] = true;
    return;
  } else {
    for (var i = index + 1; i <= index + arr[index]; i++) {
      if (jumper[i]) {
        jumper[index] = true;
        return;
      }
    }
    jumper[index] = false;
  }
}

function isReachable() {
  for (var j = arr.length - 1; j >= 0; j--) {
    hopper(j);
  }
  return jumper[0];
}

isReachable()

Output

isReachable => true
jumper => [true, false, false, true]

Time Complexity: O(n^2)
Space Complexity: O(n)
Demo

Get Minimum Hops

To get the minimum hops, now we need to keep track of the hops at each index using another array or we can create a Data Structure (here Object) to keep track of them.

var jumper = [];
var mjumper = [];
var arr = [4, 1, 1, 1];

function hopper(index) {
  if (index + arr[index] >= arr.length) {
    jumper[index] = true;
    mjumper[index] = 1;
  } else {
    for (var i = index + 1; i <= index + arr[index]; i++) {
      if (jumper[i]) {
        if (jumper[index]) {
          mjumper[index] = Math.min(mjumper[i] + 1, mjumper[index]);
        } else {
          jumper[index] = true;
          mjumper[index] = mjumper[i] + 1;
        }
      }
    }
    if (!jumper[index]) {
      jumper[index] = false;
    }
  }
}

function getMinimumSteps() {
  for (var j = arr.length - 1; j >= 0; j--) {
    hopper(j);
  }

  if (jumper[0])
    return mjumper[0];
  else return -1;
}

getMinimumSteps();

Output

Time Complexity: O(n^2)
Space Complexity: O(n)
Demo

Get Minimum Hops

Related