Tag Archives: breadth first search

C# || How To Find The Nearest Exit From Entrance In Maze Using C#

The following is a module with functions which demonstrates how to find the nearest exit from the entrance in a maze using C#.


1. Nearest Exit – Problem Statement

You are given an m x n matrix maze (0-indexed) with empty cells (represented as ‘.’) and walls (represented as ‘+’). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example 1:


Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:


Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:


Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.


2. Nearest Exit – Solution

The following is a solution which demonstrates how find the nearest exit from the entrance in a maze.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


1
2
-1

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

The following is a module with functions which demonstrates how to get two numbers in a binary search tree equal to target value using C#.


1. Find Target – Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Example 1


Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Example 2


Input: root = [5,3,6,2,4,null,7], k = 28
Output: false


2. Find Target – Solution

The following are two solutions which demonstrates how to get two numbers in a binary search tree equal to target value.

Both solutions use a set to keep track of the items already seen.

Each time a new node is encountered, we subtract the target value from the current node value. If the difference amount from subtracting the two numbers exists in the set, a 2 sum combination exists in the tree

1. Recursive

The following solution uses Depth First Search when looking for the target value.

2. Iterative

The following solution uses Breadth First Search when looking for the target value.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


true
false

C# || How To Find The Shortest Clear Path In A Binary Matrix Using C#

The following is a module with functions which demonstrates how to find the shortest clear path in a binary matrix using C#.


1. Shortest Path Binary Matrix – Problem Statement

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n – 1, n – 1)) such that:

  • All the visited cells of the path are 0.
  • All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:


Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:


Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:


Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1


2. Shortest Path Binary Matrix – Solution

The following is a solution which demonstrates how find the shortest clear path in a binary matrix.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


2
4
-1

C# || Jump Game III – How To Check If You Can Reach Target Value In Array Using C#

The following is a module with functions which demonstrates how to check if you can reach a target value in an array using C#.


1. Can Reach – Problem Statement

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i – arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:


Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:


Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

Example 3:


Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.


2. Can Reach – Solution

The following are two solutions which demonstrates how to check if you can reach a target value in an array.

The following solution uses Depth First Search when looking for the target value.

The following solution uses Breadth First Search when looking for the target value.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


true
true
false

C# || How To Find All Paths From Source To Target In Graph Using C#

The following is a module with functions which demonstrates how to find all paths from source to target in a graph using C#.


1. All Paths Source Target – Problem Statement

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n – 1, find all possible paths from node 0 to node n – 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Example 1


Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

Example 2


Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Example 3:


Input: graph = [[1],[]]
Output: [[0,1]]

Example 4:


Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]

Example 5:


Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]


2. All Paths Source Target – Solution

The following is a solution which demonstrates how to find all paths from source to target in a graph.

This solution uses Breadth First Search and backtracking when looking for paths.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


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

C# || How To Capture All Surrounded Regions ‘X’ & ‘O’ In Board Matrix Using C#

The following is a module with functions which demonstrates how to capture all surrounded regions ‘X’ and ‘O’ in a board matrix using C#.


1. Surrounded Regions – Problem Statement

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example 1:

Example 1


Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example 2:


Input: board = [["X"]]
Output: [["X"]]


2. Surrounded Regions – Solution

The following is a solution which demonstrates how to capture all surrounded regions ‘X’ and ‘O’ in a board matrix.

This solution uses Breadth First Search when looking for surrounded regions.

A ‘O’ is surrounded if there is no path from it to the outer border of the matrix (i.e: row: index 0, column: index 0, row: index matrix.length-1, column: index matrix[0].length-1) when moving in a North, South, East, or West direction.

Basically:


A 'O' will not be flipped to 'X' if:
It is on the border, OR
It is connected to any other 'O' that cannot be flipped

In this solution we get all ‘O’ cells around the borders and keep track of all ‘O’ cells connected to the ones around the outer border.

We mark the border ‘O’ cells, and all the connected ‘O’ cells to the ones around the outer border as invalid.

In the end, we mark all valid ‘O’ cells as ‘X’.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
[["X"]]