Count Good Integers on a Grid Path - Solution & Explanation

Problem Overview: You move from the top-left to the bottom-right of a grid while forming an integer from the digits along the path. The goal is to count how many paths produce a good integer (usually defined by a divisibility or remainder constraint). Since each step extends the number with a new digit, the solution must efficiently track partial results while exploring grid paths.

Approach 1: Brute Force DFS Enumeration (Exponential Time, O(2^(m+n)) time, O(m+n) space)

The most direct idea is to enumerate every possible path from the top-left to the bottom-right using depth‑first search. While traversing, append the current grid digit to the growing number. When you reach the destination, check if the constructed integer satisfies the "good" condition. This approach is easy to implement but quickly becomes impractical because the number of paths in a grid grows combinatorially.

Approach 2: DFS with Memoization on Remainders (O(m*n*k) time, O(m*n*k) space)

Instead of storing the full integer, track its remainder with respect to the constraint (for example mod k). Each state becomes (row, col, remainder). When you move to the next cell, update the remainder using (remainder * 10 + digit) % k. Memoization avoids recomputing results for the same state. This dramatically reduces the search space because there are only m * n * k possible states.

Approach 3: Bottom-Up Dynamic Programming (O(m*n*k) time, O(m*n*k) space)

A tabulation approach builds results iteratively. Maintain a DP table where dp[i][j][r] represents the number of ways to reach cell (i,j) with remainder r. Transition from the top or left neighbor by updating the remainder after appending the current digit. This avoids recursion overhead and often runs faster in practice. The technique closely follows standard grid traversal patterns seen in dynamic programming and grid problems.

Approach 4: Space Optimized DP (O(m*n*k) time, O(n*k) space)

Because each row only depends on the previous row and the current row’s left neighbor, the 3D DP table can be compressed. Keep rolling arrays for the current and previous rows while still tracking remainder states. This reduces memory usage significantly while preserving the same transition logic used in the standard DP approach. The idea is similar to optimization techniques commonly used in dynamic programming and path counting problems.

Recommended for interviews: Start by describing the brute-force DFS to demonstrate understanding of path enumeration. Then transition to the remainder-based DP state (i, j, remainder). Interviewers typically expect the optimized dynamic programming solution because it reduces exponential exploration to O(m*n*k) by reusing subproblem results.