Skip to content

Instantly share code, notes, and snippets.

@kishan-dhankecha
Last active August 5, 2022 17:12
Show Gist options
  • Save kishan-dhankecha/0dac8c3e9ba22971c15c3ac3b92497be to your computer and use it in GitHub Desktop.
Save kishan-dhankecha/0dac8c3e9ba22971c15c3ac3b92497be to your computer and use it in GitHub Desktop.
Grid Traveler function with memoization [JAVASCRIPT]
/// Say that you are a traveler on a 2D grid. You begin in the
/// top-left corner and your goal is to travel to the bottom-right
/// corner. You may only move down or right.
/// In how many ways can you travel to the goal on a grid with
/// dimensions m * n?
/// Write a function 'gridTraveler(m, n)' that calculates this.
const gridTraveler = (n, m, memory = {}) => {
// LTR check in memory.
if (`${n},${m}` in memory) return memory[`${n},${m}`];
// RTL check in memory.
if (`${m},${n}` in memory) return memory[`${m},${n}`];
// Return obvious values to stop recursion.
if (n == 1 || m == 1) return 1;
if (n == 0 || m == 0) return 0;
// Store current value in memory.
memory[`${n},${m}`] = gridTraveler(n - 1, m, memory) + gridTraveler(n, m - 1, memory);
// Return value.
return memory[`${n},${m}`];
}
console.log(gridTraveler(18, 18)); // prints => 2333606220
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment