The O(n) Club: Unique Paths—How Many Ways Can a Robot Survive the Grid?

The O(n) Club: Unique Paths—How Many Ways Can a Robot Survive the Grid?

⚡ TL;DR

Counting how many ways a robot can go from the top-left to bottom-right corner of an m x n grid, moving only right and down. Recursion will murder your run time, DP will save your bacon. Here’s a Java DP solution to keep your CPU and reputation intact:

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

🧠 How Devs Usually Mess This Up

Every junior (and a few seniors who should know better) reaches right for recursion, because ‘divide and conquer’ sounds clever until your call stack smashes into the Earth’s core. You’ll end up visiting the same subproblems over and over—imagine a robot who regularly forgets where it’s been and just wanders in circles. Fun for the robot, less fun for your interview. Oh, and please: don’t allow diagonal or backtracking. Robot’s not auditioning for Dance Dance Revolution.

🔍 What’s Actually Going On

Let’s pretend our robot is a pizza delivery guy in a perfectly gridded town. Every route from the origin to the house at (m-1, n-1) must be a shuffle of exactly m-1 downs and n-1 rights. You can think of the grid like a choose-your-own-adventure, only there are no bad endings, just a lot of redundant ones if you code it badly.
Dynamic programming shines here: the number of paths to any cell is the sum of the ways to reach the cell from above and from the left. Less recursion, fewer regrets.

🛠️ PseudoCode

• Initialize a 2D array dp with size m x n. These are your memory cells, not your hopes and dreams.
• Set the first row and column to 1. Robot can only get here by going all the way right or all the way down. Go robot go.
• For every remaining cell (i,j):
  dp[i][j] = dp[i-1][j] + dp[i][j-1]
  Translation: Ways from above + ways from left. No secret tunnels.
• Return dp[m-1][n-1] — bottom-right, triumphant, slightly exhausted robot.
• Combinatorics trick:
  The number of arrangements of steps = number of ways to pick order for m-1 downs among m+n-2 moves:
  binomial(m+n-2, m-1).

💻 The Code

// 1D space-optimized DP
int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
}
 // Binomial coefficient approach: O(1) (unless you hate integers)
int uniquePathsCombo(int m, int n) {
    int N = m + n - 2, k = Math.min(m - 1, n - 1);
    long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (N - k + i) / i;
    }
    return (int) res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Diagonal Dreams: No, the robot can’t zigzag. Right and down. That’s it.
• Off-by-One Errors: On a 3×3 grid, you get 2 downs and 2 rights (m-1 and n-1), not 3 of each. Wake up.
• Forgetful Initialization: Only the first row and first column get 1s in DP, not the entire thing.
• Combinatorial Pride: For truly gigantic grids, use the math trick and cast to long if you don’t want a number-theory headache.
• Interview Pressure: DP = O(mn) time, combinatorics = O(1). But O(1) does not mean “one line and done,” unless you like integer overflow parties.

🧠 Interviewer Brain-Tattoo

“Only robots—and junior devs—try every path; real programmers let DP do the walking.”