Pacific Atlantic Water Flowmedium

Pacific Atlantic Water Flow

medium

There is an `m x n` rectangular island that borders both the Pacific Ocean and the Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. Water can only flow in four directions (up, down, left, right) from a cell to an adjacent one with height **less than or equal** to the current cell's height. Return a list of grid coordinates `result` where `result[i] = [ri, ci]` denotes that rain water can flow from cell `(ri, ci)` to **both** the Pacific and Atlantic oceans. **Hint:** Do reverse BFS from both ocean borders.

Examples

Example 1

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

← Prev Next →

using System;
using System.Collections.Generic;

class Program {
    static bool[][] Bfs(int[][] heights, List<int[]> starts) {
        int m = heights.Length, n = heights[0].Length;
        bool[][] vis = new bool[m][];
        for (int i = 0; i < m; i++) vis[i] = new bool[n];
        var queue = new Queue<int[]>(starts);
        foreach (var s in starts) vis[s[0]][s[1]] = true;
        int[][] dirs = {new[]{0,1},new[]{0,-1},new[]{1,0},new[]{-1,0}};
        while (queue.Count > 0) {
            var cur = queue.Dequeue();
            foreach (var d in dirs) {
                int nr=cur[0]+d[0], nc=cur[1]+d[1];
                if (nr>=0&&nr<m&&nc>=0&&nc<n&&!vis[nr][nc]&&heights[nr][nc]>=heights[cur[0]][cur[1]]) {
                    vis[nr][nc]=true; queue.Enqueue(new[]{nr,nc});
                }
            }
        }
        return vis;
    }

static IList<IList<int>> PacificAtlantic(int[][] heights) {
        int m=heights.Length, n=heights[0].Length;
        var pac=new List<int[]>(); var atl=new List<int[]>();
        for(int r=0;r<m;r++){pac.Add(new[]{r,0});atl.Add(new[]{r,n-1});}
        for(int c=0;c<n;c++){pac.Add(new[]{0,c});atl.Add(new[]{m-1,c});}
        var pv=Bfs(heights,pac); var av=Bfs(heights,atl);
        var result=new List<IList<int>>();
        for(int r=0;r<m;r++) for(int c=0;c<n;c++) if(pv[r][c]&&av[r][c]) result.Add(new List<int>{r,c});
        return result;
    }

static void Main() {
        var h = new[]{new[]{1,2,2,3,5},new[]{3,2,3,4,4},new[]{2,4,5,3,1},new[]{6,7,1,4,5},new[]{5,1,1,2,4}};
        foreach (var p in PacificAtlantic(h)) Console.WriteLine($"[{p[0]},{p[1]}]");
    }
}

💻

Click Run to execute your code

Or Submit to run against all hidden test cases

Pacific Atlantic Water Flow

medium

Examples

Example 1

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Pacific Atlantic Water Flow — C# Coding Problem

Problem Description

Examples

Example 1

Pacific Atlantic Water Flow — C# Coding Problem

Problem Description

Examples

Example 1