Grid Paths Around Blocked Cells
Updated
Problem statement
You are given a grid of n rows and m columns. A cell with 0 is open and a cell with 1 is blocked. You start in the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, m - 1). Each move goes one cell to the right or one cell down, and a path may only use open cells (including its first and last cell).
Return the number of different paths. The number can be very large, so return it modulo 10^9 + 7. If the start or the end is blocked, the answer is 0.
Function
countGridPaths(grid: int[][]) → intExamples
Example 1
grid = [[0,0,0,0],[0,1,0,0],[0,0,0,1],[1,0,0,0]]return = 3Moving only right or down, a path makes 3 right moves and 3 down moves. Of the 20 such orders, the ones that avoid the blocked cells (1,1), (2,3) and (3,0) number 3.
Example 2
grid = [[1,0],[0,0]]return = 0The starting cell is blocked, so no path can begin and the answer is 0.
Example 3
grid = [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]return = 333606206With no blocked cells, an 18 x 18 grid has 2333606220 paths (choose which 17 of the 34 moves go down). That is more than 10^9 + 7, so the answer is 2333606220 - 2 * (10^9 + 7) = 333606206.
Constraints
1 <= n, m <= 100, wherenis the number of rows andmthe number of columns- every row of
gridhasmcells grid[r][c]is0or1
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Find Robots by Blocker DistancesUber · PHONE SCREENUber interview questions
- Factory Cost — Minimum Cost Across StagesStripe · PHONE SCREENStripe interview questions
- Path Through an O/X Grid Using Only Right and DownAmazon · PHONE SCREEN
- Maximum Rocks on a North-or-East Grid PathGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Maximal SquareAirwallex · PHONE SCREENAirwallex interview questions
- Maximal SquareSalesforce · PHONE SCREENSalesforce interview questions
- Minimum Path SumBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Falling Path SumIMC Trading · PHONE SCREENIMC Trading interview questions
- Largest Diamond of Ones in a GridRippling · PHONE SCREENRippling interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)