Press "Enter" to skip to content

Posts tagged as “BFS”

花花酱 LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid

Given a m x ngrid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

  • 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
  • 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
  • 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
  • 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some invalid signs on the cells of the grid which points outside the grid.

You will initially start at the upper left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path doesn’t have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1

Example 4:

Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

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

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100

Solution 1: Lazy BFS (fake DP)

dp[i][j] := min steps to reach (i, j)

Time complexity: O((m+n)*m*n)
Space complexity: O(m*n)

C++

C++

Solution 2: 0-1 BFS

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

花花酱 LeetCode 1345. Jump Game IV

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

  • i + 1 where: i + 1 < arr.length.
  • i - 1 where: i - 1 >= 0.
  • j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

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

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

  • 1 <= arr.length <= 5 * 10^4
  • -10^8 <= arr[i] <= 10^8

Solution: HashTable + BFS

Use a hashtable to store the indices of each unique number.

each index i has neighbors (i-1, i + 1, hashtable[arr[i]])

Use BFS to find the shortest path in this unweighted graph.

Key optimization, clear hashtable[arr[i]] after the first use, since all nodes are already on queue, no longer needed.

Time complexity: O(n)
Space complexity: O(n)

C++

Related Problems

花花酱 LeetCode 1306. Jump Game III

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.

Constraints:

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] < arr.length
  • 0 <= start < arr.length

Solution: BFS / DFS

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1298. Maximum Candies You Can Get from Boxes

Given n boxes, each box is given in the format [status, candies, keys, containedBoxes] where:

  • status[i]: an integer which is 1 if box[i] is open and 0 if box[i] is closed.
  • candies[i]: an integer representing the number of candies in box[i].
  • keys[i]: an array contains the indices of the boxes you can open with the key in box[i].
  • containedBoxes[i]: an array contains the indices of the boxes found in box[i].

You will start with some boxes given in initialBoxes array. You can take all the candies in any open box and you can use the keys in it to open new boxes and you also can use the boxes you find in it.

Return the maximum number of candies you can get following the rules above.

Example 1:

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

Example 2:

Input: status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
Output: 6
Explanation: You have initially box 0. Opening it you can find boxes 1,2,3,4 and 5 and their keys. The total number of candies will be 6.

Example 3:

Input: status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
Output: 1

Example 4:

Input: status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
Output: 0

Example 5:

Input: status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
Output: 7

Constraints:

  • 1 <= status.length <= 1000
  • status.length == candies.length == keys.length == containedBoxes.length == n
  • status[i] is 0 or 1.
  • 1 <= candies[i] <= 1000
  • 0 <= keys[i].length <= status.length
  • 0 <= keys[i][j] < status.length
  • All values in keys[i] are unique.
  • 0 <= containedBoxes[i].length <= status.length
  • 0 <= containedBoxes[i][j] < status.length
  • All values in containedBoxes[i] are unique.
  • Each box is contained in one box at most.
  • 0 <= initialBoxes.length <= status.length
  • 0 <= initialBoxes[i] < status.length

Solution: BFS

Only push boxes that we can open into the queue.

When can we open the box?
1. When we find it and have the key in hand.
2. When we find the key and have the box in hand.

Time complexity: O(B + K)
Space complexity: O(B)

C++

花花酱 LeetCode 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

Binary matrix is a matrix with all cells equal to 0 or 1 only.

Zero matrix is a matrix with all cells equal to 0.

Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.

Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6

Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

Constraints:

  • m == mat.length
  • n == mat[0].length
  • 1 <= m <= 3
  • 1 <= n <= 3
  • mat[i][j] is 0 or 1.

Solution: BFS + bitmask

Time complexity: O(2^(m*n))
Space complexity: O(2^(m*n))

C++