Check if There is a Path With Equal Number of 0's And 1's - Problem

You're given a binary matrix grid of size m × n containing only 0's and 1's. Starting from the top-left corner (0, 0), you need to reach the bottom-right corner (m-1, n-1).

Movement Rules: You can only move right or down - that is, from cell (row, col) you can go to either (row + 1, col) or (row, col + 1).

Goal: Determine if there exists a path from start to destination that visits exactly the same number of 0's and 1's.

Example: In a 2×2 grid [[0,1],[1,0]], one valid path is (0,0)→(0,1)→(1,1) visiting [0,1,0], which has equal counts of 0's and 1's.

Input & Output

example_1.py — Basic 2x2 Grid

$ Input: grid = [[0,1],[1,0]]

› Output: false

💡 Note: Path (0,0)→(0,1)→(1,1) visits [0,1,0], which has 2 zeros and 1 one. Path (0,0)→(1,0)→(1,1) visits [0,1,0], which also has 2 zeros and 1 one. Neither path has equal counts, so the answer is false.

example_2.py — Balanced Path Exists

$ Input: grid = [[0,1],[0,1]]

› Output: false

💡 Note: Path (0,0)→(0,1)→(1,1) visits [0,1,1], which has 1 zero and 2 ones. Path (0,0)→(1,0)→(1,1) visits [0,0,1], which has 2 zeros and 1 one. Neither path has equal counts of 0s and 1s.

example_3.py — Single Cell

$ Input: grid = [[1]]

› Output: false

💡 Note: Only one cell exists with value 1, so we have 1 one and 0 zeros, which are not equal.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 100
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Asked in

G Google 35 a Amazon 28 ⊞ Microsoft 22 f Meta 18

The optimal approach uses dynamic programming with balance tracking. Instead of counting 0's and 1's separately, we track the balance (1's count - 0's count) at each cell. We propagate all possible balance states from each cell to its right and down neighbors. The answer is true if balance 0 is achievable at the destination, indicating equal counts of 0's and 1's along some path.

Common Approaches

✓ Two Pointers

⏱️ Time: N/A Space: N/A

Dynamic Programming with State Tracking

⏱️ Time: O(m*n*k) Space: O(m*n*k)

Instead of exploring individual paths, we use dynamic programming to track all possible 'balance' states (difference between 1's and 0's) that can be achieved at each cell. The key insight is that we only need to track the difference, not the absolute counts.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

static int grid[100][100];

// Structure to store a set of integers (balances)
typedef struct {
    int* values;
    int size;
    int capacity;
} IntSet;

static IntSet dp[100][100];

void initSet(IntSet* set) {
    set->values = malloc(4000 * sizeof(int));
    set->size = 0;
    set->capacity = 4000;
}

void freeSet(IntSet* set) {
    free(set->values);
    set->size = 0;
    set->capacity = 0;
}

bool containsValue(IntSet* set, int value) {
    for (int i = 0; i < set->size; i++) {
        if (set->values[i] == value) return true;
    }
    return false;
}

void addValue(IntSet* set, int value) {
    if (!containsValue(set, value)) {
        if (set->size < set->capacity) {
            set->values[set->size++] = value;
        }
    }
}

bool findPath(int m, int n) {
    // Initialize DP table
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            initSet(&dp[i][j]);
        }
    }
    
    // Initialize starting cell
    int initial_balance = (grid[0][0] == 1) ? 1 : -1;
    addValue(&dp[0][0], initial_balance);
    
    // Fill DP table
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            
            int current_val = (grid[i][j] == 1) ? 1 : -1;
            
            // From top cell
            if (i > 0) {
                for (int k = 0; k < dp[i-1][j].size; k++) {
                    int balance = dp[i-1][j].values[k];
                    addValue(&dp[i][j], balance + current_val);
                }
            }
            
            // From left cell
            if (j > 0) {
                for (int k = 0; k < dp[i][j-1].size; k++) {
                    int balance = dp[i][j-1].values[k];
                    addValue(&dp[i][j], balance + current_val);
                }
            }
        }
    }
    
    // Check if balance 0 is achievable at destination
    bool result = containsValue(&dp[m-1][n-1], 0);
    
    // Free memory
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            freeSet(&dp[i][j]);
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Strip newline if present
    int len = strlen(line);
    if (len > 0 && line[len-1] == '\n') {
        line[len-1] = '\0';
        len--;
    }
    
    int rows = 0, cols = 0;
    int pos = 0;
    
    // Skip initial '['
    while (pos < len && line[pos] != '[') pos++;
    if (pos < len) pos++; // skip '['
    
    // Check if this is a single element array like "[1]"
    bool is_single_element = true;
    int temp_pos = pos;
    while (temp_pos < len && line[temp_pos] != ']') {
        if (line[temp_pos] == '[') {
            is_single_element = false;
            break;
        }
        temp_pos++;
    }
    
    if (is_single_element) {
        // Single element case like "[1]"
        rows = 1;
        cols = 1;
        while (pos < len && (line[pos] < '0' || line[pos] > '1')) pos++;
        if (pos < len) {
            grid[0][0] = line[pos] - '0';
        }
    } else {
        // Multi-dimensional array
        while (pos < len) {
            // Look for inner '['
            while (pos < len && line[pos] != '[') pos++;
            if (pos >= len) break;
            pos++; // skip '['
            
            int current_cols = 0;
            
            // Parse numbers in this row
            while (pos < len && line[pos] != ']') {
                if (line[pos] >= '0' && line[pos] <= '1') {
                    grid[rows][current_cols] = line[pos] - '0';
                    current_cols++;
                }
                pos++;
            }
            
            if (current_cols > 0) {
                if (cols == 0) cols = current_cols;
                rows++;
            }
            
            if (pos < len && line[pos] == ']') pos++; // skip ']'
        }
    }
    
    bool result = findPath(rows, cols);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Check if There is a Path With Equal Number of 0's And 1's - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Algorithm Steps — Algorithm Steps

Code -

Time & Space Complexity

Select Compiler