2510. Check if There is a Path With Equal Number of 0's And 1's
Problem Description
The problem provides us with an m x n
binary matrix, grid
, indexed at 0
. We can navigate this grid, moving either right to the next column or down to the next row from our current position. The goal is to determine whether there exists a path from the top-left cell (0, 0)
to the bottom-right cell (m - 1, n - 1)
where the number of 0
s encountered is exactly equal to the number of 1
s encountered along the path.
Intuition
To solve this problem, we can employ a depth-first search (DFS) that keeps track of our position in the grid and the count of 1
s that we've seen so far. We define a criterion for a successful path: it has to reach the bottom-right corner of the grid and, upon reaching it, the count of 1
s must be equal to the count of 0
s. Since any path from (0, 0)
to (m - 1, n - 1)
is m + n - 1
steps long and we want equal numbers of 1
s and 0
s, the total number of each must be half of m + n - 1
. This is only possible if m + n - 1
is even, hence we check for that early on and return False
if it's not.
If the condition is met, we perform the DFS. The key to making the DFS manageable is to cache the results of previous paths using the @cache
decorator to prevent re-computation and to cut off paths early if they become impossible. This happens if too many 1
s or 0
s are encountered before reaching the end, indicated by our counts exceeding half of m + n - 1
.
The recursive DFS is defined as such:
- We increase our count of
1
s (k
) as we encounter them along the path. - If our current position is out of bounds, we return
False
. - If the count of
1
s or0
s exceeds half of the length of a potential correct path (s
), we also returnFalse
. - If we reach the bottom-right corner, we confirm if our count of
1
s is equal tos
(as0
s will automatically be equal due to path length constraints) and returnTrue
orFalse
accordingly. - At each cell, we explore both possible next cells (right and down), if either returns
True
, we have found a valid path.
The solution is initialized by setting m
and n
to the grid dimensions and computing s
, which is half of the path length. DFS starts at (0, 0)
with an initial count of 0
. If a path that satisfies the conditions is found, dfs
will eventually return True
, otherwise, False
.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution approach uses a recursive depth-first search (DFS) technique to navigate through the matrix. The DFS is augmented with memoization through the @cache
decorator, which is a way to store the results of expensive function calls and return the cached result when the same inputs occur again, ensuring that each state is only computed once. This is critical for efficiency, especially in a matrix where there could be overlapping subproblems.
Here's the breakdown of the implementation:
- We initialize two variables
m
andn
to store the number of rows and columns of the grid, respectively. Then we calculates
as half the length of a balanced path from(0, 0)
to(m - 1, n - 1)
, which is(m + n - 1) / 2
. This division by 2 is represented by the right shift operators >>= 1
, which is an efficient way to divide by 2. - We use the
dfs(i, j, k)
function wherei
andj
are the current row and column in the grid, andk
is the current count of1
s encountered on the path. - Inside the
dfs
function:- We first check if the current position is out of bounds (
i >= m or j >= n
), returningFalse
since it is not a valid path. - We update the count of
1
s found (k += grid[i][j]
). - If the number of
1
s (k
) exceedss
or the number of0
s (i + j + 1 - k
) exceedss
, the path cannot be balanced, so we returnFalse
. - When the bottom-right corner (
i == m - 1 and j == n - 1
) is reached, we check if the number of1
s is exactlys
. If it is, we've found a valid path, otherwise, the path is invalid. - For all other cases, we recurse to the right
dfs(i, j + 1, k)
and downdfs(i + 1, j, k)
. If either of these paths returnTrue
, we returnTrue
, indicating a valid path has been found.
- We first check if the current position is out of bounds (
- Before starting the DFS, we check if
s & 1
is truthy, meaningm + n - 1
is odd and thus cannot be evenly split between0
s and1
s. In such a case, we returnFalse
. - Finally, we call the
dfs(0, 0, 0)
function to start the path search from the top-left corner with0
1
s counted so far. If the function eventually returnsTrue
, then a balanced path exists, and we returnTrue
; otherwise, we returnFalse
.
The use of recursion and memoization (through @cache
) is the key algorithmic pattern. This combination ensures that once a certain state (in terms of location and current count of 1
s) has been computed, it won't be recomputed unnecessarily, thus reducing the overall time complexity from exponential to polynomial.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the described solution approach, let's consider a small 3x3
binary matrix example:
1grid = [ 2 [0, 1, 0], 3 [0, 0, 1], 4 [1, 0, 1] 5]
- First, we determine
m
andn
. In this case,m = 3
andn = 3
. - We calculate
s
as half the length of a balanced path. Since the path from(0, 0)
to(m - 1, n - 1)
hasm + n - 1 = 5
steps, and5
is odd, we can conclude right away that it's not possible to have a balanced path with an equal number of0
s and1
s. Therefore, in this situation, our algorithm would returnFalse
.
Suppose we had a scenario where m + n - 1
is even. Let's change the grid to make that possible:
1grid = [ 2 [0, 1], 3 [1, 0] 4]
m = 2
,n = 2
, ands = (2 + 2 - 1) / 2 = 1.5
. Since we deal with whole numbers, we can only have an equal number of0
s and1
s ifs
is an integer, so3
would be rounded down to1
.
Now, let's walk through a successful step-by-step DFS:
- Start DFS with
dfs(0, 0, 0)
. - At
[0][0]
, our countk
remains0
. We calldfs(0, 1, 0)
to move right anddfs(1, 0, 0)
to move down. - The right move leads to
[0][1]
, which is a1
, sok
is incremented. The countk
is now1
, so we cannot move right anymore as it would leave the grid. We move down withdfs(1, 1, 1)
. - The down move from step 2 leads to
[1][0]
, which is a1
, so we incrementk
. We move right to[1][1]
withdfs(1, 1, 1)
. - Now at
[1][1]
, we are in the bottom-right corner. Herek
is1
, and sinces
is1
, we have an equal number of0
s and1
s, which satisfies the conditions of the path.
Therefore, a valid path exists, and the function dfs(0, 0, 0)
eventually returns True
.
Solution Implementation
1from typing import List
2from functools import lru_cache
3
4class Solution:
5 def is_there_a_path(self, grid: List[List[int]]) -> bool:
6 # Calculate rows and columns for the provided grid
7 rows, cols = len(grid), len(grid[0])
8 # Compute the sum value for comparison during DFS
9 target_sum = rows + cols - 1
10
11 # Return False immediately if target_sum is odd, since we can't split into two equal integers
12 if target_sum % 2 != 0:
13 return False
14 # The actual sum we need one of the paths to equal
15 target_sum //= 2
16
17 # Using memoization to avoid recomputing for the same cell
18 @lru_cache(None)
19 def dfs(row, col, path_sum):
20 # If we are out of bounds, return False
21 if row >= rows or col >= cols:
22 return False
23
24 # Increment path_sum by the value of the current cell
25 path_sum += grid[row][col]
26
27 # If the path_sum exceeds target_sum or if
28 # the remaining cells aren't enough to complete the sum, return False
29 if path_sum > target_sum or row + col + 1 - path_sum > target_sum:
30 return False
31
32 # If we've reached the bottom-right cell, check if the path sum equals the target sum
33 if row == rows - 1 and col == cols - 1:
34 return path_sum == target_sum
35
36 # Recursively explore the path to the right and down
37 return dfs(row + 1, col, path_sum) or dfs(row, col + 1, path_sum)
38
39 # Initiate the recursive depth-first search from the top-left corner of the grid
40 return dfs(0, 0, 0)
41
1public class Solution {
2 // Variable 's' represents the target sum for the subsets.
3 private int targetSum;
4 // Variables 'rows' and 'cols' represent the dimensions of the grid.
5 private int rows;
6 private int cols;
7 // The 'grid' stores the input grid.
8 private int[][] grid;
9 // The 'memo' stores previously computed results to avoid re-calculation during the DFS.
10 private Boolean[][][] memo;
11
12 // Method to determine if there is a path such that the sum of grid values is half the perimeter sum.
13 public boolean isThereAPath(int[][] grid) {
14 this.grid = grid;
15 rows = grid.length;
16 cols = grid[0].length;
17 // Compute the sum of elements on the perimeter of the grid.
18 targetSum = rows + cols - 1;
19 // Initialize memoization array.
20 memo = new Boolean[rows][cols][targetSum];
21 // If the perimeter sum is odd, it's impossible to have two subsets with equal sum, return false.
22 if (targetSum % 2 == 1) {
23 return false;
24 }
25 // Halve the target sum since we want to find a subset with a sum equal to half the perimeter sum.
26 targetSum >>= 1;
27 // Start DFS search from the top-left corner of the grid.
28 return dfs(0, 0, 0);
29 }
30
31 // Helper method to perform DFS on the grid.
32 private boolean dfs(int i, int j, int currentSum) {
33 // If the current cell is out of the grid bounds, return false.
34 if (i >= rows || j >= cols) {
35 return false;
36 }
37 // Add the value of the current cell to 'currentSum'.
38 currentSum += grid[i][j];
39 // If result has been computed before, return the stored value.
40 if (memo[i][j][currentSum] != null) {
41 return memo[i][j][currentSum];
42 }
43 // If the current sum exceeds half of the target sum or the complement exceeds it, return false.
44 if (currentSum > targetSum || i + j + 1 - currentSum > targetSum) {
45 return false;
46 }
47 // If we've reached the bottom-right corner, check if currentSum equals half of the target sum.
48 if (i == rows - 1 && j == cols - 1) {
49 return currentSum == targetSum;
50 }
51 // Perform DFS on the next element to the right and the bottom. Store result in 'memo' to avoid re-calculation.
52 memo[i][j][currentSum] = dfs(i + 1, j, currentSum) || dfs(i, j + 1, currentSum);
53 // Return the stored result.
54 return memo[i][j][currentSum];
55 }
56}
57
1class Solution {
2public:
3 // Check if there is a path in the grid where the sum equals the sum of leftover elements
4 bool isThereAPath(vector<vector<int>>& grid) {
5 int numRows = grid.size(); // Number of rows in the grid
6 int numCols = grid[0].size(); // Number of columns in the grid
7 int targetSum = numRows + numCols - 1; // Total possible sum for a path
8
9 // Check if the targetSum is even, as we are looking for equal partition
10 if (targetSum & 1) return false; // If the sum is odd, cannot be split equally
11
12 targetSum >>= 1; // Divide the sum by 2 since we are looking for two equal halves
13
14 // A 3D cache to store the states (result) of subproblems
15 int cache[numRows][numCols][targetSum];
16 memset(cache, -1, sizeof(cache)); // Initialize cache with -1
17
18 // Define a recursive DFS function to explore the grid
19 function<bool(int, int, int)> dfs = [&](int row, int col, int runningSum) -> bool {
20 if (row >= numRows || col >= numCols) return false; // Out of grid bounds
21
22 // Add the current grid value to the runningSum
23 runningSum += grid[row][col];
24
25 // Check if we already have a computed result for the current state in cache
26 if (cache[row][col][runningSum] != -1) return cache[row][col][runningSum];
27
28 // If the runningSum or the sum of the leftover elements exceeds the targetSum, return false
29 if (runningSum > targetSum || row + col + 1 - runningSum > targetSum) return false;
30
31 // Check if we reached the last cell and if the runningSum equals half the targetSum
32 if (row == numRows - 1 && col == numCols - 1) return runningSum == targetSum;
33
34 // Recur for the cells directly right and below the current cell
35 cache[row][col][runningSum] = dfs(row + 1, col, runningSum) || dfs(row, col + 1, runningSum);
36 // Save the result in cache
37
38 return cache[row][col][runningSum]; // Return the cached result
39 };
40
41 // Start DFS from the top-left corner with an initial runningSum of 0
42 return dfs(0, 0, 0);
43 }
44};
45
1// Define the type for a grid as a 2D array of numbers
2type Grid = number[][];
3
4// Define a function to check the existence of a path with sum equals to the sum of leftover elements
5function isThereAPath(grid: Grid): boolean {
6 const numRows: number = grid.length; // Number of rows in the grid
7 const numCols: number = grid[0].length; // Number of columns in the grid
8 let targetSum: number = numRows + numCols - 1; // Total possible sum for a path
9
10 // Check if the targetSum is even, as we are looking for an equal partition
11 if (targetSum % 2 !== 0) return false; // If the sum is odd, it cannot be split equally
12
13 targetSum /= 2; // Divide the sum by 2 since we are looking for two equal halves
14
15 // A 3D array cache to store the states (results) of subproblems
16 const cache: number[][][] = Array.from({ length: numRows }, () =>
17 Array.from({ length: numCols }, () => Array(targetSum + 1).fill(-1))
18 );
19
20 // Define a recursive DFS function to explore the grid
21 const dfs = (row: number, col: number, runningSum: number): boolean => {
22 if (row >= numRows || col >= numCols) return false; // Out of grid bounds
23
24 // Add the current grid value to the runningSum
25 runningSum += grid[row][col];
26
27 // Check if we already have a computed result for the current state in cache
28 if (cache[row][col][runningSum] !== -1) return cache[row][col][runningSum] === 1;
29
30 // If the runningSum or the sum of the leftover elements exceeds the targetSum, return false
31 if (runningSum > targetSum || row + col + 1 - runningSum > targetSum) return false;
32
33 // Check if we reached the last cell and if the runningSum equals half the targetSum
34 if (row === numRows - 1 && col === numCols - 1) return runningSum === targetSum;
35
36 // Recur for the cells directly to the right and below the current cell
37 const result = dfs(row + 1, col, runningSum) || dfs(row, col + 1, runningSum);
38 cache[row][col][runningSum] = result ? 1 : 0; // Save the result in cache
39
40 return result; // Return the result
41 };
42
43 // Start DFS from the top-left corner of the grid with an initial runningSum of 0
44 return dfs(0, 0, 0);
45}
46
Time and Space Complexity
Time Complexity
The time complexity of the isThereAPath
function is O(mns), where m
is the number of rows, n
is the number of columns, and s
is half the perimeter of the grid (sum of rows m
and columns n
, minus 1, all divided by 2).
This is because in the worst case, the dfs
function is called for every possible position (i, j)
and for every possible sum k
up to s
. Since there are m*n
positions and up to s
possible values for k
, the result is m*n*s
.
The recursive function might visit each cell multiple times with different values of k
, but the memoization using @cache
ensures that it will only recompute if it finds a cell with a distinct k
value that it has not yet explored.
Space Complexity
The space complexity of the solution is O(mns), which comes from the call stack used in recursion and the cache used for memoization.
The recursive depth of the stack can go as deep as m + n
in the worst case (if a path involves all rows and columns). Additionally, the memoization employed by @cache
will store results for each (i, j, k)
tuple which has been computed and not yet been visited.
Since there are m*n
positions and up to s
distinct values for each position's sum k
, the memoization cache can take up as much space as there are combinations of positions and sums, leading to a space complexity of O(mns).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first