Cracking The Coding Interview Together – Problem 8.2: Robot in a Grid

Picture this: you are building an automated warehouse fulfillment system. Your automated inventory robot needs to navigate a sprawling, grid-based warehouse floor from the loading dock at the top-left corner to the packing station at the bottom-right. But there is a catch—some aisles are blocked off due to ongoing maintenance or spilled inventory. The robot can only move in two directions: right and down. If it hits an off-limits cell, it's game over for that path. How do we program our robot to find a valid path efficiently without burning through CPU cycles exploring dead ends?

This is the classic Robot in a Grid problem (Problem 8.2 in Cracking the Coding Interview). It bridges basic recursive thinking with advanced memoization and dynamic programming. Today, we are going to build an optimal, production-ready solution together, examining the trade-offs at every step.

Problem Statement

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

Our operational goals are:

• Determine if a valid path exists from (0, 0) to (r-1, c-1).
• Return the actual sequence of coordinates representing the path if one exists.
• Optimize for time and space complexity, avoiding exponential blowups common in naive recursive searches.

Analyze the Problem Together

When we look at a grid-based movement problem, our minds naturally jump to graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS). Since the robot only moves right and down, our search space forms a Directed Acyclic Graph (DAG) or a tree of recursive choices.

Let's consider the naive recursive approach. From any cell (row, col), we can try moving right to (row, col + 1) or down to (row + 1, col). If either recursive call returns a valid path, we append our current cell and bubble the result up. What is the catch? Overlapping subproblems. Multiple paths can lead to the exact same cell (r, c). Without caching, our time complexity balloons to $O(2^{r+c})$, which is disastrous for large grids.

To fix this, we introduce memoization. By storing the results of cells we have already visited—specifically marking cells that yield no path as permanently "failed"—we prune redundant branches and drop our time complexity down to $O(r imes c)$.

Questions for the Interviewer

Before we write a single line of code, a senior engineer asks clarifying questions to bound the problem space:

• Scale: What are the constraints for r and c? If the grid is millions by millions, do we need to worry about memory limits for our memoization table or call stack?
• Path Optimization: Does the problem require the shortest path, or just any valid path? (Since we can only move right and down, any valid path will actually have the exact same number of steps: (r-1) + (c-1)).
• Grid Representation: How are off-limits cells represented in our input? Are they booleans, specific integer codes, or objects?

Think About the Solution

We will implement a top-down dynamic programming approach using recursion combined with a memoization set (or boolean matrix) to track visited dead ends.

Our algorithm works as follows:

1. Start at the destination cell (r-1, c-1) and recurse backward to (0, 0), OR start at (0, 0) and recurse forward. Working backward from the destination naturally aligns with how we build our path list from start to finish.
2. Check base cases: Is the cell out of bounds? Is it off-limits? Have we already visited this cell and found it to be a dead end?
3. If we are at the origin (0, 0), or if a recursive call from either the right or down direction succeeds, add the current point to our path and return true.
4. If neither direction yields a result, cache this failure in our visited set so we never revisit it, and return false.

Write Code and Explain

Here is our production-ready Java implementation:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class RobotInAGrid {

    public static class Point {
        public int row;
        public int col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }

        @Override
        public String toString() {
            return "(" + row + ", " + col + ";)";
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return row == point.row && col == point.col;
        }

        @Override
        public int hashCode() {
            return 31 * row + col;
        }
    }

    public static List<Point> findPath(boolean[][] grid) {
        if (grid == null || grid.length == 0) return null;
        
        List<Point> path = new ArrayList<>();
        HashSet<Point> failedPoints = new HashSet<>();
        
        int rows = grid.length;
        int cols = grid[0].length;
        
        if (findPathHelper(grid, rows - 1, cols - 1, path, failedPoints)) {
            return path;
        }
        
        return null;
    }

    private static boolean findPathHelper(boolean[][] grid, int row, int col, 
                                        List<Point> path, HashSet<Point> failedPoints) {
        // 1. Check bounds and validity
        if (col < 0 || row < 0 || !grid[row][col]) {
            return false;
        }

        Point p = new Point(row, col);

        // 2. Check if we've already visited this cell and know it fails
        if (failedPoints.contains(p)) {
            return false;
        }

        boolean isAtOrigin = (row == 0 && col == 0);

        // 3. If we're at the origin, or if a path can be found from the left or above
        if (isAtOrigin || 
            findPathHelper(grid, row, col - 1, path, failedPoints) || 
            findPathHelper(grid, row - 1, col, path, failedPoints)) {
            
            path.add(p);
            return true;
        }

        // 4. Cache failure
        failedPoints.add(p);
        return false;
    }
}

Let's break down how this works. We define a helper method findPathHelper that starts at the bottom-right corner (rows - 1, cols - 1) and attempts to reach (0, 0) by checking left and upward movements. When a valid subpath is found, points are added to our path list. Because we append after the recursive calls resolve, our list naturally populates from the start point to the destination.

Time & Space Complexity

Let's analyze the resource utilization of our solution:

• Time Complexity: $\mathcal{O}(r \times c)$ — Without memoization, exploring every right/down branch would take exponential time. By caching failed states in our failedPoints hash set, we visit each cell in the grid at most once.
• Space Complexity: $\mathcal{O}(r \times c)$ — In the worst-case scenario where nearly all cells are invalid, our failedPoints set stores up to $r \times c$ points. Additionally, the call stack depth goes up to $\mathcal{O}(r + c)$, and our result path stores $\mathcal{O}(r + c)$ elements.

Why This Problem Matters (The Senior Perspective)

Grid traversal problems are foundational building blocks in systems design, gaming AI (like pathfinding in real-time strategy games), and network packet routing. Understanding how to transition from a brute-force recursive approach to a memoized dynamic programming solution is a core competency for tackling complex state-space searches.

In production environments, recursion depth can become a bottleneck if grids are massive. For extremely large grids, engineers often pivot from recursive memoization to iterative bottom-up table filling, or employ heuristic algorithms like A* search when diagonal or unconstrained movements are permitted.

Final Thoughts

Mastering problems like Robot in-a Grid trains your brain to spot overlapping subproblems instantly. Practice modifying this algorithm to count the total number of possible paths instead of returning just one.

Happy coding, and keep building resilient systems!