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 0s encountered is exactly equal to the number of 1s 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 1s 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 1s must be equal to the count of 0s. Since any path from (0, 0) to (m - 1, n - 1) is m + n - 1 steps long and we want equal numbers of 1s and 0s, 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 1s or 0s 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 1s (k) as we encounter them along the path.
  • If our current position is out of bounds, we return False.
  • If the count of 1s or 0s exceeds half of the length of a potential correct path (s), we also return False.
  • If we reach the bottom-right corner, we confirm if our count of 1s is equal to s (as 0s will automatically be equal due to path length constraints) and return True or False 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 and n to store the number of rows and columns of the grid, respectively. Then we calculate s 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 operator s >>= 1, which is an efficient way to divide by 2.
  • We use the dfs(i, j, k) function where i and j are the current row and column in the grid, and k is the current count of 1s encountered on the path.
  • Inside the dfs function:
    • We first check if the current position is out of bounds (i >= m or j >= n), returning False since it is not a valid path.
    • We update the count of 1s found (k += grid[i][j]).
    • If the number of 1s (k) exceeds s or the number of 0s (i + j + 1 - k) exceeds s, the path cannot be balanced, so we return False.
    • When the bottom-right corner (i == m - 1 and j == n - 1) is reached, we check if the number of 1s is exactly s. 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 down dfs(i + 1, j, k). If either of these paths return True, we return True, indicating a valid path has been found.
  • Before starting the DFS, we check if s & 1 is truthy, meaning m + n - 1 is odd and thus cannot be evenly split between 0s and 1s. In such a case, we return False.
  • Finally, we call the dfs(0, 0, 0) function to start the path search from the top-left corner with 0 1s counted so far. If the function eventually returns True, then a balanced path exists, and we return True; otherwise, we return False.

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 1s) 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 Evaluator

Example Walkthrough

To illustrate the described solution approach, let's consider a small 3x3 binary matrix example:

grid = [
  [0, 1, 0],
  [0, 0, 1],
  [1, 0, 1]
]
  • First, we determine m and n. In this case, m = 3 and n = 3.
  • We calculate s as half the length of a balanced path. Since the path from (0, 0) to (m - 1, n - 1) has m + n - 1 = 5 steps, and 5 is odd, we can conclude right away that it's not possible to have a balanced path with an equal number of 0s and 1s. Therefore, in this situation, our algorithm would return False.

Suppose we had a scenario where m + n - 1 is even. Let's change the grid to make that possible:

grid = [
  [0, 1],
  [1, 0]
]
  • m = 2, n = 2, and s = (2 + 2 - 1) / 2 = 1.5. Since we deal with whole numbers, we can only have an equal number of 0s and 1s if s is an integer, so 3 would be rounded down to 1.

Now, let's walk through a successful step-by-step DFS:

  1. Start DFS with dfs(0, 0, 0).
  2. At [0][0], our count k remains 0. We call dfs(0, 1, 0) to move right and dfs(1, 0, 0) to move down.
  3. The right move leads to [0][1], which is a 1, so k is incremented. The count k is now 1, so we cannot move right anymore as it would leave the grid. We move down with dfs(1, 1, 1).
  4. The down move from step 2 leads to [1][0], which is a 1, so we increment k. We move right to [1][1] with dfs(1, 1, 1).
  5. Now at [1][1], we are in the bottom-right corner. Here k is 1, and since s is 1, we have an equal number of 0s and 1s, 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many times is a tree node visited in a depth first search?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More