Number of Paths with Max Score
Hard
0 views
Topics:
ArraysDynamic Programming
You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.
You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.
Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.
In case there is no path, return [0, 0].
Example 1:
Input: board = ["E23","2X2","12S"] Output: [7,1]
Example 2:
Input: board = ["E12","1X1","21S"] Output: [4,2]
Example 3:
Input: board = ["E11","XXX","11S"] Output: [0,0]
Constraints:
2 <= board.length == board[i].length <= 100
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the dimensions of the board, and what is the maximum size of the board allowed?
- Can the board contain characters other than 'E', 'S', 'X', and digits from '0' to '9'?
- If no valid path from 'E' to 'S' exists, what should the function return? Specifically, should I return [0, 0] or is there another expected default value?
- Is it possible to have multiple paths that result in the same maximum score? If so, should I return the number of such paths?
- Can the starting point 'E' or the ending point 'S' be surrounded by 'X's, effectively making it impossible to start or end the path?
Brute Force Solution
Approach
We want to find the best path to the starting point on a game board and the maximum score we can achieve on that path. The brute force approach is like trying every possible way to move from the end to the start and figuring out the score for each of those paths.
Here's how the algorithm would work step-by-step:
- Start at the end point of the board.
- Consider all possible moves we can make from the current position (up or left, in this case).
- For each possible move, we go to the new position and then consider all possible moves we can make from *that* position.
- We keep doing this, exploring all possible paths, until we reach the starting point.
- Every time we find a path from the end to the start, we calculate the total score for that path.
- After exploring all possible paths, we compare all the scores we found.
- We then pick the path that gave us the highest score and how many paths actually acheived that score.
Code Implementation
def number_of_paths_with_max_score_brute_force(board):
rows = len(board)
cols = len(board[0])
max_score = 0
number_of_paths = 0
def is_valid(row_index, col_index):
return 0 <= row_index < rows and 0 <= col_index < cols and board[row_index][col_index] != 'X'
def find_paths(row_index, col_index, current_score, path_count):
nonlocal max_score, number_of_paths
# Base case: Reached the starting point
if row_index == 0 and col_index == 0:
if current_score > max_score:
max_score = current_score
number_of_paths = path_count
elif current_score == max_score:
number_of_paths += path_count
return
# Check for valid moves up and left
possible_moves = []
if is_valid(row_index - 1, col_index):
possible_moves.append((row_index - 1, col_index))
if is_valid(row_index, col_index - 1):
possible_moves.append((row_index, col_index - 1))
# No possible moves means a dead end
if not possible_moves:
return
# Calculate the current cell value to add to score
current_cell_value = 0
if board[row_index][col_index] != 'E':
current_cell_value = int(board[row_index][col_index])
# Explore all possible paths using recursion
for next_row_index, next_col_index in possible_moves:
find_paths(next_row_index, next_col_index, current_score + current_cell_value, path_count)
# Start from the end point
find_paths(rows - 1, cols - 1, 0, 1)
# Modulo operation to prevent overflow, required by the prompt
return [max_score, number_of_paths % (10**9 + 7)]
Big(O) Analysis
Time Complexity
O(3^n) – The brute force approach explores every possible path from the end to the start. At each step, we have at most two choices: move up or move left. In the worst case (a board without obstacles), we need to move n steps up and n steps left to reach the start from the end, where n is related to the board size. This leads to a branching factor of roughly 2 at each step, and a path length of up to 2n steps. Thus, the total number of possible paths we need to explore can grow on the order of 2^(2n) which can be simplified to 4^n, however with the possibility of not moving up or left at some paths, the complexity falls closer to an upper bound of O(3^n) in the worst case. Therefore the time complexity grows exponentially with the dimensions of the board.
Space Complexity
O(N) – The provided solution implicitly uses recursion to explore all possible paths. Each recursive call adds a new frame to the call stack. In the worst-case scenario, the maximum depth of the recursion can be proportional to the number of cells in the board (N), where N is the number of cells, leading to a call stack that uses O(N) space. No significant auxiliary data structures are created beyond the call stack, so the space complexity is dominated by the recursion depth. Therefore, the auxiliary space complexity is O(N).
Optimal Solution
Approach
We want to find the best possible score and the number of ways to achieve that score when moving from the end to the start of a board. We use a clever trick to remember the best score and number of paths to reach each spot, avoiding redundant calculations.
Here's how the algorithm would work step-by-step:
- Start at the very end of the board (the destination).
- Work your way backwards, moving from the end towards the beginning.
- For each spot on the board, figure out the maximum score you can achieve if you start from that spot and follow the best possible path to the end.
- Also, for each spot, keep track of how many different paths there are that lead to that maximum score.
- When calculating the score and paths for a spot, look at the spots you can move to from there (down and to the right).
- Use the pre-calculated scores and path counts from those reachable spots to determine the best score and path count for the current spot.
- If both moving down and moving right give the same maximum score, add the number of paths from both directions to get the total number of paths for the current spot.
- Ignore any spots that are obstacles ('X').
- Once you reach the starting spot, you'll have the maximum score achievable and the number of paths to achieve it.
Code Implementation
def number_of_paths_with_max_score(board):
board_size = len(board)
score_dp = [[0] * board_size for _ in range(board_size)]
paths_dp = [[0] * board_size for _ in range(board_size)]
paths_dp[board_size - 1][board_size - 1] = 1
for row_index in range(board_size - 1, -1, -1):
for column_index in range(board_size - 1, -1, -1):
if board[row_index][column_index] == 'X':
continue
if row_index == board_size - 1 and column_index == board_size - 1:
score_dp[row_index][column_index] = 0
continue
max_score = -1
number_of_paths = 0
#Check the 'down' direction
if row_index + 1 < board_size and board[row_index + 1][column_index] != 'X':
if score_dp[row_index + 1][column_index] > max_score:
max_score = score_dp[row_index + 1][column_index]
number_of_paths = paths_dp[row_index + 1][column_index]
elif score_dp[row_index + 1][column_index] == max_score:
number_of_paths = (number_of_paths + paths_dp[row_index + 1][column_index]) % 1000000007
#Check the 'right' direction
if column_index + 1 < board_size and board[row_index][column_index + 1] != 'X':
if score_dp[row_index][column_index + 1] > max_score:
max_score = score_dp[row_index][column_index + 1]
number_of_paths = paths_dp[row_index][column_index + 1]
elif score_dp[row_index][column_index + 1] == max_score:
number_of_paths = (number_of_paths + paths_dp[row_index][column_index + 1]) % 1000000007
#Check the 'diagonal' direction
if row_index + 1 < board_size and column_index + 1 < board_size and board[row_index + 1][column_index + 1] != 'X':
if score_dp[row_index + 1][column_index + 1] > max_score:
max_score = score_dp[row_index + 1][column_index + 1]
number_of_paths = paths_dp[row_index + 1][column_index + 1]
elif score_dp[row_index + 1][column_index + 1] == max_score:
number_of_paths = (number_of_paths + paths_dp[row_index + 1][column_index + 1]) % 1000000007
if max_score != -1:
#Add the current cell value to the path
if board[row_index][column_index] != 'S':
score_dp[row_index][column_index] = int(board[row_index][column_index]) + max_score
else:
score_dp[row_index][column_index] = max_score
#The number of paths equals to the value we have computed
paths_dp[row_index][column_index] = number_of_paths
# If no path exists return 0
if paths_dp[0][0] == 0:
return [0, 0]
# Return the score and the number of paths
else:
return [score_dp[0][0], paths_dp[0][0] % 1000000007]Big(O) Analysis
Time Complexity
O(n*n) – The algorithm iterates through each cell of the board once, starting from the end and moving towards the beginning. The board has dimensions n x n, where n is the length of each row and each column. For each cell, the algorithm performs a constant number of operations: checking the cells to the right and below, calculating the maximum score, and updating the path count. Therefore, the total time complexity is proportional to the number of cells in the board, which is n * n. This can be simplified to O(n*n).
Space Complexity
O(N) – The algorithm uses two 2D arrays, `dp_score` and `dp_paths`, to store the maximum score and the number of paths to reach each cell, respectively. Both arrays have the same dimensions as the input board, which is of size N, where N is the number of cells on the board. Thus, the auxiliary space used is proportional to the size of the board, leading to a space complexity of O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty board input | Return [0, 0] if the board is null or empty as there are no paths or scores. |
| Board with only one cell (start or end) | If the board has only one cell and it's 'E', the score is 0 and there's one path; otherwise, score and path are both 0. |
| Board with no path to the end ('E') | If there is no path from the start to 'E', the score and number of paths should both be zero. |
| Board containing obstacles ('X') that block all paths | If all possible paths are blocked by 'X', the result should be score 0 and 0 paths. |
| Large board size to check for time complexity issues. | Use dynamic programming to optimize the solution, achieving a time complexity of O(N*N) where N is the size of the board. |
| Board with large numerical values leading to integer overflow during score calculation. | Use modulo operator to avoid integer overflow during score calculation, taking the modulo by 10^9 + 7 as specified. |
| Multiple paths with the same maximum score | The solution should count and return the number of distinct paths leading to the maximum score. |
| Board only contains number characters and 'E' and 'X'. | The code should throw an exception when an invalid character occurs on the board. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
