Problem Understanding
You are given a matrix where each cell represents the signal strength of a communication tower.
There are two control stations:
A signal can travel from one tower to its neighboring tower (up, down, left, right) only if the neighbor's signal strength is less than or equal to the current tower's signal strength.
Your task is to count how many towers can send a signal to both Station P and Station Q.
Naive Approach
A simple approach would be:
Start DFS/BFS from every cell.
Check whether it can reach Station P.
Check whether it can reach Station Q.
If there are N × M cells, every DFS may visit all cells.
Time Complexity
O((N × M)²)
This is too slow for large matrices (1000 × 1000).
Optimized Idea
Instead of starting from every cell, we reverse the thinking.
Original Signal Flow
Signal flows:
Higher Height
↓
Lower or Equal Height
Suppose:
5 → 4 → 3 → 2
Signal can move:
5 → 4
4 → 3
3 → 2
Reverse Traversal
Instead of checking who reaches the station,
Start from the station and move in reverse.
If signal normally goes:
5 → 4
then reverse traversal goes:
4 → 5
That means while doing DFS/BFS, we only move to cells having:
Next Height >= Current Height
This reverse traversal finds every cell that can eventually send a signal to that station.
Algorithm
Step 1
Create two visited arrays.
boolean[][] p;
boolean[][] q;
Step 2
Start DFS/BFS from Station P boundaries.
Top Row
(0,0) (0,1) (0,2)...
Left Column
(0,0)
(1,0)
(2,0)
Mark every reachable cell inside p[][].
Step 3
Start DFS/BFS from Station Q boundaries.
Bottom Row
(n-1,0)
(n-1,1)
...
Right Column
(0,m-1)
(1,m-1)
...
Mark every reachable cell inside q[][].
Step 4
Finally, count cells where:
p[i][j] == true
&&
q[i][j] == true
Those cells can reach both stations.
Code Explanation
Direction Array
int[][] dir = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
Instead of writing four different cases, this array stores:
During DFS/BFS:
newRow = row + dir[k][0];
newCol = col + dir[k][1];
Creating Visited Arrays
boolean[][] p = new boolean[n][m];
boolean[][] q = new boolean[n][m];
These arrays remember which cells can reach:
Initially every value is:
false
Starting DFS for Station P
for(int j=0;j<m;j++)
dfs(mat,0,j,p);
Starts from:
Top Row
0 1 2 3
Then:
for(int i=0;i<n;i++)
dfs(mat,i,0,p);
Starts from:
Left Column
0
1
2
3
Now every reachable cell gets marked in:
p[][]
Starting DFS for Station Q
Bottom Row
for(int j=0;j<m;j++)
dfs(mat,n-1,j,q);
Right Column
for(int i=0;i<n;i++)
dfs(mat,i,m-1,q);
Now:
q[][]
contains all cells reaching Station Q.
DFS Function
private void dfs(int[][] mat,
int r,
int c,
boolean[][] vis)
Parameters:
matrix
current row
current column
visited array
Already Visited
if(vis[r][c])
return;
Avoids infinite recursion.
Mark Current Cell
vis[r][c]=true;
This cell can reach the station.
Visit Neighbors
for(int[] d:dir)
Checks:
Compute Neighbor
int nr=r+d[0];
int nc=c+d[1];
Check Boundary
nr>=0 &&
nr<n &&
nc>=0 &&
nc<m
Avoids ArrayIndexOutOfBounds.
Important Condition
mat[nr][nc] >= mat[r][c]
Why greater?
Because we are moving backwards.
Original signal rule:
Higher
↓
Lower
Reverse traversal becomes:
Lower
↓
Higher
Therefore:
Neighbor Height >= Current Height
Example
Original:
9 → 5 → 3
Reverse DFS:
3 → 5 → 9
Hence:
next >= current
Recursive Call
dfs(mat,nr,nc,vis);
Continue exploring.
Counting Answer
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(p[i][j] && q[i][j])
ans++;
}
}
If a cell is reachable from both traversals, increase answer.
Return
return ans;
Dry Run
Matrix
1 2 2
3 2 3
2 4 5
Station P DFS
Starts from:
Top Row
1 2 2
Left Column
1
3
2
Marks all reachable cells.
Station Q DFS
Starts from:
Bottom Row
2 4 5
Right Column
2
3
5
Marks reachable cells.
Finally
Intersection:
P Q
T T
T F
F T
Only cells marked true in both arrays are counted.
Complexity Analysis
Time Complexity
Each cell is visited at most once for Station P and once for Station Q.
O(N × M)
Space Complexity
Two visited arrays:
O(N × M)
Recursion stack (DFS):
O(N × M)
or queue size (BFS):
O(N × M)
Java Implementation
class Solution {
int n, m;
int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
public int countCoordinates(int[][] mat) {
n = mat.length;
m = mat[0].length;
boolean[][] p = new boolean[n][m];
boolean[][] q = new boolean[n][m];
// Station P (Top row)
for (int j = 0; j < m; j++) {
dfs(mat, 0, j, p);
}
// Station P (Left column)
for (int i = 0; i < n; i++) {
dfs(mat, i, 0, p);
}
// Station Q (Bottom row)
for (int j = 0; j < m; j++) {
dfs(mat, n - 1, j, q);
}
// Station Q (Right column)
for (int i = 0; i < n; i++) {
dfs(mat, i, m - 1, q);
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (p[i][j] && q[i][j]) {
ans++;
}
}
}
return ans;
}
private void dfs(int[][] mat, int r, int c, boolean[][] vis) {
if (vis[r][c]) return;
vis[r][c] = true;
for (int[] d : dir) {
int nr = r + d[0];
int nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m
&& !vis[nr][nc]
&& mat[nr][nc] >= mat[r][c]) {
dfs(mat, nr, nc, vis);
}
}
}
}
Key Points
Instead of starting DFS from every cell, reverse the traversal.
Use two traversals:
Move only to neighbors with greater than or equal height during reverse traversal.
The final answer is the intersection of both reachable sets.
Time Complexity: O(N × M)
Space Complexity: O(N × M)
This reverse-search technique is a common optimization pattern for matrix reachability problems and is the same idea used in the well-known Pacific Atlantic Water Flow problem.