Frontend School

Maximize Team Mood Path

DSA
medium

Maximize Team Mood Path

Medium
Dynamic Programming
2D DP
Grid

Overview

At Atlassian, team morale is crucial for productivity and innovation. Imagine we have a project board represented as a grid, where each cell signifies a task and has an associated "mood score" reflecting its impact on the team's spirit. A project manager needs to navigate this board from the top-left to the bottom-right, moving only right or down. To strategically boost morale, the manager has a limited number of "mood boost" items, each capable of doubling the mood score of a single task cell. The goal is to find the path that maximizes the total accumulated mood score for the team.

What you need to do / Task

You are tasked with implementing a function that calculates the maximum possible total mood score a project manager can achieve.

  1. Implement the maxMoodPath function.
  2. Your solution should use dynamic programming.
  3. Handle all valid inputs as per the constraints.

Input & output

The function maxMoodPath takes two parameters:

  • moods: A 2D array (matrix) of integers representing the mood score of each cell. moods[r][c] is the score for the cell at row r and column c.
  • k: An integer representing the total number of mood boost items available.

The function should return a single integer:

  • The maximum total mood score achievable from (0, 0) to (m-1, n-1) using at most k mood boost items.

Clarifications

  • The starting cell (0, 0) and the ending cell (m-1, n-1) are part of the path, and their scores contribute to the total.
  • A mood boost item can be applied to any cell on the chosen path, including the start or end cell.
  • Each mood boost item can only be used once. If k items are available, you can use 0 to k items.
  • Mood scores can be positive, zero, or negative. The total path score can also be negative.
  • If no valid path exists (e.g., empty grid), the problem constraints ensure valid m, n >= 1.

Examples

1

Example 1

Input:

moods = [[1, 2], [3, 4]], k = 1

Output:

12

Note:

The optimal path is (0,0) -> (1,0) -> (1,1). Boosting moods[1][1] (score 4 -> 8) results in a total score of 1 (at (0,0)) + 3 (at (1,0)) + 8 (at (1,1)) = 12.

2

Example 2

Input:

moods = [[10, -5, 20], [1, 10, -10], [5, 2, 8]], k = 0

Output:

31

Note:

With no boosts, the optimal path is (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2). The total score is 10 + 1 + 10 + 2 + 8 = 31.

3

Example 3

Input:

moods = [[-1, -2], [-3, -4]], k = 1

Output:

-7

Note:

All mood scores are negative. Boosting any cell makes its score more negative (e.g., -1 becomes -2). The optimal path is (0,0) -> (0,1) -> (1,1) without using any boosts, resulting in -1 + (-2) + (-4) = -7.

Constraints

Constraints & assumptions

  • 1 <= m, n <= 50 (where m is the number of rows, n is the number of columns in moods)
  • -100 <= moods[r][c] <= 100
  • 0 <= k <= 10
  • You can only move right ((r, c) -> (r, c+1)) or down ((r, c) -> (r+1, c)).

What interviewers evaluate

  • Correctness: Does the solution produce the accurate maximum mood score for all valid inputs?
  • Algorithm Design: Is dynamic programming effectively applied to solve the problem with optimal time and space complexity?
  • Code Quality: Is the code clean, readable, well-structured, and appropriately commented?
  • Edge Case Handling: Does the solution correctly handle scenarios like k=0, 1xN or Mx1 grids, and negative mood scores?

Loading editor...