Skip to main content
Talentd

Disconnect Path in a Binary Matrix by at Most One Flip - Solution & Explanation

MediumArrayDynamic ProgrammingDepth-First SearchBreadth-First Search14 min readAsked at: Google
Practice this problem

Problem Statement

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1).

You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1).

Return true if it is possible to make the matrix disconnect or false otherwise.

Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

 

Example 1:

Input: grid = [[1,1,1],[1,0,0],[1,1,1]]
Output: true
Explanation: We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.

Example 2:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: false
Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 1

Approach Overview

Problem Overview: You are given a binary matrix where 1 represents a valid cell and 0 represents a blocked cell. Starting from the top‑left corner, you can only move right or down. The task is to determine whether flipping at most one 1 to 0 can disconnect all paths from the start cell to the bottom‑right cell.

Approach 1: BFS/DFS to Check and Remove One Path (O(m*n) time, O(m*n) space)

Run a DFS or BFS from (0,0) to see if a valid path to (m-1,n-1) exists. If no path exists, the grid is already disconnected, so return true. Otherwise, trace one discovered path and temporarily flip its intermediate cells to 0. Then run the traversal again. If another path still reaches the destination, the grid cannot be disconnected with a single flip. If no second path exists, one flipped cell along the original path is enough to break connectivity.

The key insight: if two independent paths exist that do not rely on the same intermediate cell, removing one cell will not disconnect the grid. Removing the cells of the first discovered path tests whether an alternative route exists. This technique relies heavily on grid traversal using Depth-First Search or Breadth-First Search.

Approach 2: Track Reachable and Critical Cells Separately (Dynamic Programming) (O(m*n) time, O(m*n) space)

Compute reachability from the start and from the end separately. A forward DP or BFS marks cells reachable from (0,0), while a reverse traversal marks cells that can reach (m-1,n-1). Any cell that appears in both sets lies on at least one valid path.

Next, count how many such cells appear on each "layer" defined by i + j. If a layer contains exactly one reachable cell that lies on every path, that cell becomes a critical bottleneck. Flipping it disconnects the grid. This method effectively identifies articulation-like points in the path structure using Dynamic Programming on a matrix.

Recommended for interviews: The DFS/BFS path-removal approach is the most common interview solution. It is simple, runs in O(m*n), and demonstrates strong understanding of grid traversal and path uniqueness. The DP reachability method shows deeper insight into path structure and critical cells but is slightly harder to reason about under interview pressure.

Approach 1: BFS/DFS to Check Initial Connectivity

Perform a BFS or DFS from the starting point (0, 0) to determine if there is a path to (m-1, n-1). Record reachable cells. If these cells all remain connected even after a potential flip, then the grid cannot be disconnected. Otherwise, assess if flipping a single cell can break the connection.

The function uses a BFS to check if the grid is initially connected from (0, 0) to (m-1, n-1). If it is connected, the code then explores flipping each 0 cell adjacent to the connected path to determine if the grid can be disconnected by such a flip.

Code

PythonJavaScript

Python

JavaScript

Complexity

  • Time Complexity: O(m * n), where m and n are rows and columns.
  • Space Complexity: O(m * n), due to the queue and visited set.
Try this approach in the editor →

Approach 2: Track Reachable and Critical Cells Separately

Identify critical cells that are necessary for maintaining a path from (0, 0) to (m-1, n-1). Implement union-find to manage connectivity dynamically, and then flip cells to test disconnection potential while keeping track of reachability separately.

This C++ solution introduces a function to assess path existence via BFS, and tries flipping all 0s to check disconnection result. The logic is parallel to the BFS approach deconstructed earlier but refactored into modular functions suitable for C++ patterns.

Code

C++Java

C++

Java

Complexity

  • Time Complexity: O(m * n), checking each cell once per BFS invocation.
  • Space Complexity: O(m * n), depending on queued elements for BFS.
Try this approach in the editor →

Approach 3: Two DFS Traversals

First, we perform a DFS traversal to determine whether there is a path from (0, 0) to (m - 1, n - 1), and we denote the result as a. During the DFS process, we set the value of the visited cells to 0 to prevent revisiting.

Next, we set the values of (0, 0) and (m - 1, n - 1) to 1, and perform another DFS traversal to determine whether there is a path from (0, 0) to (m - 1, n - 1), and we denote the result as b. During the DFS process, we set the value of the visited cells to 0 to avoid revisiting.

Finally, if both a and b are true, we return false, otherwise, we return true.

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
BFS/DFS to Check Initial Connectivity
  • Time Complexity: O(m * n), where m and n are rows and columns.
  • Space Complexity: O(m * n), due to the queue and visited set.
Track Reachable and Critical Cells Separately
  • Time Complexity: O(m * n), checking each cell once per BFS invocation.
  • Space Complexity: O(m * n), depending on queued elements for BFS.
Two DFS Traversals—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS/BFS Path Detection and RemovalO(m*n)O(m*n)General interview solution; simple traversal and easy to implement
Reachability + Critical Layer Tracking (DP)O(m*n)O(m*n)When analyzing path bottlenecks or identifying critical cells across all paths

Video Solution

Disconnect Path in a Binary Matrix by at Most One Flip | Biweekly Contest 97 | Leetcode • codingMohan • 2,063 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Disconnect Path in a Binary Matrix by at Most One Flip easy or hard?
This problem is rated Medium on LeetCode but feels tricky because it mixes grid traversal with reasoning about multiple paths. The implementation itself is straightforward once the insight about testing for a second independent path is understood.
Disconnect Path in a Binary Matrix by at Most One Flip Python/Java solution
Python and Java implementations typically use DFS or BFS for grid traversal. The algorithm first finds one path from start to end, blocks that path, and runs the search again. If the second search fails to reach the target, flipping one cell successfully disconnects the grid.
How to solve Disconnect Path in a Binary Matrix by at Most One Flip in O(m*n)?
First run DFS or BFS to check if a path from the top-left to bottom-right exists. If no path exists, return true. If a path exists, mark the cells of that path as blocked and run the traversal again. If the destination is still reachable, more than one independent path exists and one flip is insufficient; otherwise the grid becomes disconnected.
What is the best approach for Disconnect Path in a Binary Matrix by at Most One Flip?
The most practical approach uses DFS or BFS to find one valid path from the start to the end, temporarily removes that path, and then checks if another path still exists. If a second path is found, the grid cannot be disconnected with one flip. If no second path exists, flipping a cell from the first path breaks connectivity. This solution runs in O(m*n) time.
Is Disconnect Path in a Binary Matrix by at Most One Flip asked at Google/Amazon/Meta?
Grid traversal and path‑disconnection problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving DFS, BFS, or identifying critical cells in a grid are common because they test graph modeling and algorithmic reasoning.
What data structure is used in Disconnect Path in a Binary Matrix by at Most One Flip?
The core data structures are a matrix for the grid, a visited structure for traversal, and either a recursion stack (DFS) or queue (BFS). Some optimized solutions also use dynamic programming arrays to track cells reachable from the start and from the end.
What is the time complexity of Disconnect Path in a Binary Matrix by at Most One Flip?
Both common solutions run in O(m*n) time where m and n are the grid dimensions. The algorithm performs at most two full traversals of the matrix using DFS or BFS. Space complexity is also O(m*n) due to recursion stack or visited tracking structures.

Ready to solve this problem?

Practice Disconnect Path in a Binary Matrix by at Most One Flip with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Make at Least One Valid Path in a Grid

Next

Minimum Number of Days to Disconnect Island