Matrix Traversals

O(n)
n = size(grid)

Python - DFS | Java - DFS

	def dfs(grid: List[List[int]], i: int, j: int, visited: Set[List[int]]):
	if i < 0 or j < 0 or i >= len(grid) or \
	j >= len(grid[0]) or (i, j) in visited: return
	visited.add((i, j))
	dfs(grid, i + 1, j, visited)
	dfs(grid, i - 1, j, visited)
	dfs(grid, i, j + 1, visited)
	dfs(grid, i, j - 1, visited)

view raw 2D_DFS.py hosted with ❤ by GitHub

	void dfs(int[][] grid, int i, int j, boolean[][] visited) {
	if (i < 0 || j < 0 || i >= grid.length ||
	j >= grid[0].length || visited[i][j]) return;
	visited[i][j] = true;
	dfs(grid, i + 1, j, visited);
	dfs(grid, i - 1, j, visited);
	dfs(grid, i, j + 1, visited);
	dfs(grid, i, j - 1, visited);
	}

view raw 2D_DFS.java hosted with ❤ by GitHub

Python - BFS | Java - BFS

	dirs = [ [0,1], [0,-1], [1,0], [-1,0] ]
	def bfs(grid: List[List[int]], _i: int, _j: int):
	q = deque([[_i, _j]])
	visited = set([(_i, _j)])
	while q:
	cur = q.popleft()
	for dir in dirs:
	i = cur[0] + dir[0]
	j = cur[1] + dir[1]
	if i < 0 or j < 0 or i >= len(grid) or \
	j >= len(grid[0]) or (i, j) in visited: continue
	visited.add((i, j))
	q.append([i, j])

view raw 2D_BFS.py hosted with ❤ by GitHub

	int[][] dirs = { {0,1}, {0,-1}, {1,0}, {-1,0} };
	void bfs(char[][] grid, int _i, int _j) {
	Deque<int[]> q = new ArrayDeque<>();
	boolean[][] visited = new boolean[grid.length][grid[0].length];
	q.addLast(new int[] {_i, _j});
	visited[_i][_j] = true;
	while (!q.isEmpty()) {
	int[] cur = q.removeFirst();
	for (int[] dir : dirs) {
	int i = cur[0] + dir[0];
	int j = cur[1] + dir[1];
	if (i < 0 || j < 0 || i >= grid.length ||
	j >= grid[0].length || visited[i][j]) continue;
	visited[i][j] = true;
	q.addLast(new int[] {i, j});
	}
	}
	}

view raw 2D_BFS.java hosted with ❤ by GitHub