#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static void dfs(int **heights, bool *ocean, int rows, int cols, int r, int c,
int prevHeight) {
if (r < 0 || c < 0 || r >= rows || c >= cols)
return;
if (ocean[r * cols + c] || heights[r][c] < prevHeight)
return;
ocean[r * cols + c] = true;
for (int d = 0; d < 4; d++)
dfs(heights, ocean, rows, cols, r + dirs[d][0], c + dirs[d][1],
heights[r][c]);
}
int **pacificAtlantic(int **heights, int heightsSize, int *heightsColSize,
int *returnSize, int **returnColumnSizes) {
int rows = heightsSize, cols = heightsColSize[0];
// flattened rows x cols grids
bool *pacific = calloc(rows * cols, sizeof(bool));
bool *atlantic = calloc(rows * cols, sizeof(bool));
for (int i = 0; i < rows; i++) {
dfs(heights, pacific, rows, cols, i, 0, INT_MIN);
dfs(heights, atlantic, rows, cols, i, cols - 1, INT_MIN);
}
for (int j = 0; j < cols; j++) {
dfs(heights, pacific, rows, cols, 0, j, INT_MIN);
dfs(heights, atlantic, rows, cols, rows - 1, j, INT_MIN);
}
// at most every cell qualifies
int **result = malloc(rows * cols * sizeof(int *));
*returnColumnSizes = malloc(rows * cols * sizeof(int));
*returnSize = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (pacific[i * cols + j] && atlantic[i * cols + j]) {
int *cell = malloc(2 * sizeof(int));
cell[0] = i, cell[1] = j;
(*returnColumnSizes)[*returnSize] = 2;
result[(*returnSize)++] = cell;
}
free(pacific);
free(atlantic);
return result;
}
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
rows = heights.size();
cols = heights[0].size();
vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
for (int i = 0; i < rows; i++) {
dfs(heights, pacific, i, 0, INT_MIN);
dfs(heights, atlantic, i, cols - 1, INT_MIN);
}
for (int j = 0; j < cols; j++) {
dfs(heights, pacific, 0, j, INT_MIN);
dfs(heights, atlantic, rows - 1, j, INT_MIN);
}
vector<vector<int>> result;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (pacific[i][j] && atlantic[i][j])
result.push_back({i, j});
return result;
}
private:
int rows, cols;
static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void dfs(vector<vector<int>> &heights, vector<vector<bool>> &ocean, int r,
int c, int prevHeight) {
if (r < 0 || c < 0 || r >= rows || c >= cols)
return;
if (ocean[r][c] || heights[r][c] < prevHeight)
return;
ocean[r][c] = true;
for (auto [dr, dc] : dirs)
dfs(heights, ocean, r + dr, c + dc, heights[r][c]);
}
};
package graphs
import "math"
var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
func pacificAtlantic(heights [][]int) [][]int {
rows, cols := len(heights), len(heights[0])
pacific, atlantic := newGrid(rows, cols), newGrid(rows, cols)
var dfs func(ocean [][]bool, r, c, prevHeight int)
dfs = func(ocean [][]bool, r, c, prevHeight int) {
if r < 0 || c < 0 || r >= rows || c >= cols {
return
}
if ocean[r][c] || heights[r][c] < prevHeight {
return
}
ocean[r][c] = true
for _, d := range dirs {
dfs(ocean, r+d[0], c+d[1], heights[r][c])
}
}
for i := 0; i < rows; i++ {
dfs(pacific, i, 0, math.MinInt)
dfs(atlantic, i, cols-1, math.MinInt)
}
for j := 0; j < cols; j++ {
dfs(pacific, 0, j, math.MinInt)
dfs(atlantic, rows-1, j, math.MinInt)
}
var result [][]int
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if pacific[i][j] && atlantic[i][j] {
result = append(result, []int{i, j})
}
}
}
return result
}
func newGrid(rows, cols int) [][]bool {
g := make([][]bool, rows)
for i := range g {
g[i] = make([]bool, cols)
}
return g
}
import java.util.ArrayList;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private int rows, cols;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
rows = heights.length;
cols = heights[0].length;
boolean[][] pacific = new boolean[rows][cols];
boolean[][] atlantic = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
dfs(heights, pacific, i, 0, Integer.MIN_VALUE);
dfs(heights, atlantic, i, cols - 1, Integer.MIN_VALUE);
}
for (int j = 0; j < cols; j++) {
dfs(heights, pacific, 0, j, Integer.MIN_VALUE);
dfs(heights, atlantic, rows - 1, j, Integer.MIN_VALUE);
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (pacific[i][j] && atlantic[i][j])
result.add(List.of(i, j));
return result;
}
private void dfs(int[][] heights, boolean[][] ocean, int r, int c, int prevHeight) {
if (r < 0 || c < 0 || r >= rows || c >= cols)
return;
if (ocean[r][c] || heights[r][c] < prevHeight)
return;
ocean[r][c] = true;
for (int[] d : DIRS)
dfs(heights, ocean, r + d[0], c + d[1], heights[r][c]);
}
}
const DIRS = [
[1, 0],
[0, 1],
[-1, 0],
[0, -1],
];
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function (heights) {
const rows = heights.length,
cols = heights[0].length;
const newGrid = () => Array.from({ length: rows }, () => Array(cols).fill(false));
const pacific = newGrid(),
atlantic = newGrid();
const dfs = (ocean, r, c, prevHeight) => {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
if (ocean[r][c] || heights[r][c] < prevHeight) return;
ocean[r][c] = true;
for (const [dr, dc] of DIRS) dfs(ocean, r + dr, c + dc, heights[r][c]);
};
for (let i = 0; i < rows; i++) {
dfs(pacific, i, 0, -Infinity);
dfs(atlantic, i, cols - 1, -Infinity);
}
for (let j = 0; j < cols; j++) {
dfs(pacific, 0, j, -Infinity);
dfs(atlantic, rows - 1, j, -Infinity);
}
const result = [];
for (let i = 0; i < rows; i++)
for (let j = 0; j < cols; j++) if (pacific[i][j] && atlantic[i][j]) result.push([i, j]);
return result;
};
from typing import List
DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows, cols = len(heights), len(heights[0])
pacific = [[False] * cols for _ in range(rows)]
atlantic = [[False] * cols for _ in range(rows)]
def dfs(ocean: List[List[bool]], r: int, c: int, prev_height: float) -> None:
if r < 0 or c < 0 or r >= rows or c >= cols:
return
if ocean[r][c] or heights[r][c] < prev_height:
return
ocean[r][c] = True
for dr, dc in DIRS:
dfs(ocean, r + dr, c + dc, heights[r][c])
for i in range(rows):
dfs(pacific, i, 0, float("-inf"))
dfs(atlantic, i, cols - 1, float("-inf"))
for j in range(cols):
dfs(pacific, 0, j, float("-inf"))
dfs(atlantic, rows - 1, j, float("-inf"))
return [
[i, j]
for i in range(rows)
for j in range(cols)
if pacific[i][j] and atlantic[i][j]
]
const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
impl Solution {
pub fn pacific_atlantic(heights: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let (rows, cols) = (heights.len(), heights[0].len());
let mut pacific = vec![vec![false; cols]; rows];
let mut atlantic = vec![vec![false; cols]; rows];
for i in 0..rows {
Self::dfs(&heights, &mut pacific, i, 0, i32::MIN);
Self::dfs(&heights, &mut atlantic, i, cols - 1, i32::MIN);
}
for j in 0..cols {
Self::dfs(&heights, &mut pacific, 0, j, i32::MIN);
Self::dfs(&heights, &mut atlantic, rows - 1, j, i32::MIN);
}
let mut result = Vec::new();
for i in 0..rows {
for j in 0..cols {
if pacific[i][j] && atlantic[i][j] {
result.push(vec![i as i32, j as i32]);
}
}
}
result
}
fn dfs(heights: &[Vec<i32>], ocean: &mut Vec<Vec<bool>>, r: usize, c: usize, prev_height: i32) {
if ocean[r][c] || heights[r][c] < prev_height {
return;
}
ocean[r][c] = true;
let (rows, cols) = (heights.len(), heights[0].len());
for (dr, dc) in DIRS {
// wrapping_add_signed turns -1 at 0 into usize::MAX, caught by the bounds check
let (nr, nc) = (r.wrapping_add_signed(dr), c.wrapping_add_signed(dc));
if nr < rows && nc < cols {
Self::dfs(heights, ocean, nr, nc, heights[r][c]);
}
}
}
}