We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Paths with Max Score

Number: 1234

Difficulty: Hard

Paid? No

Companies: Amazon, Samsung

Problem Description

Given a square board where each cell contains either a digit ('1'-'9'), an obstacle ('X'), the start ('S' at the bottom-right), or the end ('E' at the top-left), find the maximum sum obtainable by moving from S to E. Allowed moves are upward, leftward, or diagonally up-left. Additionally, compute the number of distinct paths that yield this maximum sum, with the count returned modulo 10^9+7. If no valid path exists, return [0, 0].

Key Insights

  • Use dynamic programming (DP) traversing the board in reverse (from start 'S' backwards to end 'E').
  • Maintain a DP table where each cell holds a pair: (max score achievable from that cell to the end, count of paths that achieve that score).
  • Transitions consider three possible moves (up, left, diagonal up-left) and pick the best outcome.
  • Sum the numeric value of the current cell (if it is not 'S' or 'E') to contributions from the next moves.
  • Carefully handle obstacles ('X') by skipping them in the DP update.

Space and Time Complexity

Time Complexity: O(n^2), where n is the dimension of the square board, since each cell is processed once. Space Complexity: O(n^2) for storing the DP table.

Solution

We solve the problem using dynamic programming. A DP table dp[i][j] is used where each cell stores a tuple representing (maxScore, numPaths) from that position to the target 'E'. The board is processed in reverse order (starting from the bottom-right S) and for each cell we consider the moves allowed: up, left, and diagonal up-left. For each valid move, we update the current cell's dp value:

  • If the neighbor's max score is higher than what is currently known, update the current cell with that score plus the current cell’s digit (if applicable) and take the neighbor's path count.
  • If the neighbor’s max score equals the best known option, add its path count. Obstacles are skipped in the DP computation. Special consideration is given to the 'E' and 'S' cells where no numeric addition occurs. Finally, if the computed maximum score is negative (or no valid path is found), we return [0, 0].

Code Solutions

# Python solution with detailed comments

MOD = 10**9 + 7

def pathsWithMaxScore(board):
    n = len(board)
    # dp[i][j] = (maxScore, numPaths) from cell (i, j) to the end
    dp = [[(-1, 0) for _ in range(n)] for _ in range(n)]
    
    # Initialize start position 'S' at bottom-right.
    dp[n-1][n-1] = (0, 1)
    
    # Process board from bottom-right to top-left
    for i in range(n-1, -1, -1):
        for j in range(n-1, -1, -1):
            # Skip obstacles and the starting cell since they are already set.
            if board[i][j] == 'X' or (i == n-1 and j == n-1):
                continue
            
            bestScore = -1
            ways = 0
            # List of possible moves: downwards in our reversed computation corresponds to going up in actual movement.
            for di, dj in [(1, 0), (0, 1), (1, 1)]:
                ni, nj = i + di, j + dj
                if ni < n and nj < n:
                    score, count = dp[ni][nj]
                    if score == -1:  # unreachable cell.
                        continue
                    if score > bestScore:
                        bestScore = score
                        ways = count
                    elif score == bestScore:
                        ways = (ways + count) % MOD
            
            # If there is no valid move from the current cell, continue to next cell.
            if bestScore == -1:
                dp[i][j] = (-1, 0)
            else:
                # If current cell is the 'E', no digit is added.
                if board[i][j] in "SE":
                    dp[i][j] = (bestScore, ways)
                else:
                    # Otherwise, add the current digit value to bestScore.
                    dp[i][j] = (bestScore + int(board[i][j]), ways)
                    
    resultScore, resultPaths = dp[0][0]
    if resultScore == -1:
        return [0, 0]
    else:
        return [resultScore, resultPaths]

# Example usage:
#print(pathsWithMaxScore(["E23", "2X2", "12S"]))
← Back to All Questions