Towers Reaching Both Stations

Problem Overview

Station 1 sits on the top and left borders; station 2 on the bottom and right.

Intuition

Station 1 sits on the top and left borders; station 2 on the bottom and right. A tower can receive a signal from a border if there is a path of adjacent cells with non-decreasing heights from that border. Run two DFS flood-fills and count cells marked by both.

Algorithm

1DFS from every top-row and left-column cell into station1[][] (vis1).
2DFS from every bottom-row and right-column cell into station2[][] (vis2).
3In DFS at (i,j), visit unvisited neighbors where mat[ni][nj] >= mat[i][j].
4Count cells where station1[i][j] && station2[i][j].

Example Walkthrough

Input: heights matrix with border stations

1. From top/left borders, flood all cells reachable via non-decreasing steps.
2. From bottom/right borders, flood similarly for station 2.
3. Cells in the intersection are towers reached by both stations.

Output: count of overlapping cells

Common Pitfalls

• Movement rule is mat[neighbor] >= mat[current] — you can only step uphill or level.
• Seed DFS from entire borders, not just corners.
• Mark visited in the boolean grid to avoid infinite loops on cycles of equal height.

Towers Reaching Both Stations.java

Java

// Approach: DFS from station-1 borders (top row + left col) and station-2 borders (bottom row
// + right col). Move only to neighbors with height >= current; count cells reachable from both.
// Time: O(n * m) Space: O(n * m)

class Solution {

    private static final int[][] DIRS = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };

    int n, m;

    public int countCoordinates(int[][] mat) {
        n = mat.length;
        m = mat[0].length;

        boolean[][] station1 = new boolean[n][m];
        boolean[][] station2 = new boolean[n][m];

        // DFS from Station 1 (top row)
        for (int j = 0; j < m; j++) {
            dfs(0, j, mat, station1);
        }

        // DFS from Station 1 (left column)
        for (int i = 0; i < n; i++) {
            dfs(i, 0, mat, station1);
        }

        // DFS from Station 2 (bottom row)
        for (int j = 0; j < m; j++) {
            dfs(n - 1, j, mat, station2);
        }

        // DFS from Station 2 (right column)
        for (int i = 0; i < n; i++) {
            dfs(i, m - 1, mat, station2);
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (station1[i][j] && station2[i][j]) {
                    ans++;
                }
            }
        }

        return ans;
    }

    private void dfs(int i, int j, int[][] mat, boolean[][] vis) {
        if (vis[i][j]) {
            return;
        }

        vis[i][j] = true;
        for (int[] d : DIRS) {
            int ni = i + d[0];
            int nj = j + d[1];

            if (ni < 0 || ni >= n || nj < 0 || nj >= m) {
                continue;
            }

            // Reverse traversal:
            // Move only to towers with height >= current tower
            if (mat[ni][nj] >= mat[i][j]) {
                dfs(ni, nj, mat, vis);
            }
        }
    }
}

Was this solution helpful?