Problem statement

The problem is defined in the book as following:

8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

— Cracking the Coding Interview (6th edition)

Feedback I am looking for

Here's the list of things I am interested to hear back (in order of significance):

1. Design decisions and improvements (as in "better approach(es) performance- and memory-wise").


2. Code readability.


3. JavaScript (ES6) language idioms.


4. Whatever you find important to say that does not fall into three categories mentioned above.

My approach, design, implementation, and performance description

I've solved a similar problem in the past and recalling the way I attacked it back then. To reach the bottom right cell, we need to either reach its upper neighbor and move down, or reach its left neighbor and move right. By induction, for the upper (or left) neighbor to be reached, we in turn need to first reach their upper or left neighbor and make a single move. And so on, until we find that we're at the top left position of the grid. If the "neighbor reachability moves" were recorded, replaying them in the reverse order results in the path we are after.

Graphically it can be represented like this

State I) represents the final cell the robot needs to reach, and the arrows in neighboring cells show the direction of the move.

States II) and III) show how the neighbors referred in I) can be reached.

States IV), V), VI), and VII) show the same for the neighbors referred in II) and III).

This picture can go on and on, but there are three (four?) more special cases:

In LI) the upper cell is known to be unreachable (grid boundary, restricted cell, or learnt to be unreachable from the top-left cell by down/right moves). LII) is the similar, but describes the left neighbor cell as unreachable. The current cells might only get reached from left or upper neighbor, respectively.

Finally, LIII) is a special case which either denotes the complete "unreachability" of the cell from the top-left corner. However, it may also indicate the robot has now reached to top-left corner itself (rowIndex === 0, columnIndex === 0).

Recursive solution

The code looks almost trivial if problem is solved recursively.

export type X = 'x'; // Forbidden cell
export type _ = ' '; // Allowed cell
export type Grid = (X | _);
export type Move = 'down' | 'right';

export function findPathRecursively(grid: Grid, rowIndex?: number, columnIndex?: number): Move | null 

The obvious issues with this approach are:

• Horrible time complexity ⇒ impractically slow execution even on reasonable size grids. I haven't deeply analyzed it yet, but it's gotta be something like $ O(rc!) $, (r and c are as defined in problem statement). The root cause of this is the fact the same grid cell can be visited multiple times as a part of different paths. (E.g. states V) and VI) on the picture above are essentially the same, but discovered by arriving from different cells...


• Quick call stack exhaustion (StackOverflow 😏) ⇒ breaking while executing.

Non-recursive solution

So, to solve the mentioned issue, I'm doing two things:

1. "Linearizing" the solution (i.e. getting rig of the recursive calls by using a single loop);


2. Applying memoization, which is recording the cells which are known to be unreachable from the target cell and avoiding further visits of such cells.

This is hugely improving the time complexity, which looks $ O(rc) $ to me, at the cost of $ O(rc) $ memory used for unreachable cells recording.

My main question here is whether I can further optimize the algorithm time performance AND reduce the memory usage?

Code to review

export function findPath(grid: Grid): Move | null 
 if (!grid 

function markNoPath(hintTable: string, rowIndex: number, columnIndex: number): void 
 if (!hintTable[rowIndex])
 hintTable[rowIndex] = ;
 hintTable[rowIndex][columnIndex] = '*'; 


function lookUp(
 grid: Grid,
 hintTable: string,
 rowIndex: number,
 columnIndex: number,
): boolean 
 return rowIndex > 0 &&
 (hintTable[rowIndex - 1] 

function lookLeft(
 grid: Grid,
 hintTable: string,
 rowIndex: number,
 columnIndex: number,
): boolean 
 return columnIndex > 0 &&
 (hintTable[rowIndex] 

Unit tests

The tests are provided for illustration purpose only. The review is NOT necessary, but if you see a mistake, feel free to point it out.

import 
 findPath,
 findPathRecursively,
 Grid,
 from '../src/cracking-the-coding-interview/8-recursion-and-dynamic-programming/8-2-robot-in-a-grid';

const nullGrid: Grid = null;

const gridWithSingleBlockedCell: Grid = [['x']];

const emptyGrid: Grid = [];

const oneByOneGrid: Grid = [[' ']];

const oneByTwoGrid: Grid = [[' ', ' ']];
const twoByOneGrid: Grid = [[' '], [' ']];

const twoByTwoGridA: Grid = [[' ', 'x'], [' ', ' ']];
const twoByTwoGridB: Grid = [[' ', ' '], ['x', ' ']];

const stairGrid: Grid = [
 [' ', 'x', ' ', ' ', ' '],
 [' ', ' ', 'x', ' ', ' '],
 ['x', ' ', ' ', 'x', ' '],
 [' ', 'x', ' ', ' ', 'x'],
 [' ', ' ', 'x', ' ', ' '],
];

const wellGrid: Grid = [
 [' ', 'x', ' ', ' ', ' '],
 [' ', ' ', ' ', 'x', ' '],
 [' ', ' ', 'x', ' ', ' '],
 [' ', 'x', ' ', ' ', ' '],
 [' ', ' ', ' ', ' ', ' '],
];

const cliffGrid: Grid = [
 [' ', ' ', ' ', ' ', ' '],
 ['x', ' ', ' ', 'x', ' '],
 [' ', ' ', 'x', ' ', ' '],
 [' ', 'x', ' ', ' ', ' '],
 [' ', ' ', ' ', ' ', ' '],
];

describe(`$findPathRecursively.name & $findPath.name`, () => 
 [
 grid: nullGrid, expectedPath: null ,
 grid: gridWithSingleBlockedCell, expectedPath: null ,
 grid: emptyGrid, expectedPath: null ,
 grid: oneByOneGrid, expectedPath: ,
 grid: oneByTwoGrid, expectedPath: ['right'] ,
 grid: twoByOneGrid, expectedPath: ['down'] ,
 grid: twoByTwoGridA, expectedPath: ['down', 'right'] ,
 grid: twoByTwoGridB, expectedPath: ['right', 'down'] ,
 
 grid: stairGrid,
 expectedPath: [ 'down', 'right', 'down', 'right', 'down', 'right', 'down', 'right' ],
 ,
 
 grid: wellGrid,
 expectedPath: [ 'down', 'down', 'down', 'down', 'right', 'right', 'right', 'right' ],
 ,
 
 grid: cliffGrid,
 expectedPath: [ 'right', 'right', 'right', 'right', 'down', 'down', 'down', 'down' ],
 ,
 ].forEach(( grid, expectedPath ) => 
 const path = expectedPath == null ? 'null' : expectedPath.join('->');
 const gridText = JSON.stringify(grid, null, 2);

 it(`[Recursive] Should return "$path" for gridn$gridText`, () => 
 expect(findPathRecursively(grid)).toEqual(expectedPath);
 );

 it(`[Non-recursive] Should return "$path" for gridn$gridText`, () => 
 expect(findPath(grid)).toEqual(expectedPath);
 );
 );
);