Frontend School

Content Path Engagement Maximizer

DSA
medium

Content Path Engagement Maximizer

Medium
Dynamic Programming
2D DP
Grid

Overview

Adobe products often involve optimizing content delivery and user engagement across various platforms. Imagine a sophisticated content recommendation system that guides a user through a curated path of content modules arranged in a grid. Each module has an inherent engagement value, and some modules are strategically designated as "hot zones" (high-value multipliers) or "cold zones" (value reducers) to influence user flow. Your task is to implement an algorithm that finds the most engaging path through this grid.

What you need to do / Task

Implement the function maxEngagementScore that calculates the maximum possible total engagement score a user can achieve by navigating a grid of content modules.

  1. Starting Point: The user begins at the top-left cell (0, 0) of the grid.
  2. Movement Rules: From any cell (r, c), the user can only move right to (r, c+1) or down to (r+1, c).
  3. Score Accumulation: When the user enters a cell (r, c), its base engagementValue from grid[r][c] is added to their current total score.
  4. Zone Modifiers: Additionally, consider the zoneType for that cell from zoneTypes[r][c]:
    • If zoneType is "HOT", the engagementValue for grid[r][c] is tripled (before being added to the total score).
    • If zoneType is "COLD", the engagementValue for grid[r][c] is halved (using integer division, e.g., Math.floor(value / 2)) (before being added to the total score).
    • If zoneType is "NORMAL", the engagementValue is added as is.
  5. Goal: The objective is to reach the bottom-right cell (R-1, C-1) with the maximum possible total engagement score.

Input & output

Function Signature: function maxEngagementScore(grid: number[][], zoneTypes: string[][]): number

Input:

  • grid: A 2D array of integers, where grid[r][c] represents the base engagement value of the content module at row r and column c.
  • zoneTypes: A 2D array of strings, where zoneTypes[r][c] represents the type of zone ("NORMAL", "HOT", or "COLD") for the content module at row r and column c. This array will always have the same dimensions as grid.

Output:

  • A single integer representing the maximum total engagement score achievable by reaching the bottom-right cell (R-1, C-1).

Clarifications

  • The starting cell (0, 0)'s effective_value (after applying any zone modifier) is the initial score.
  • For "COLD" zones, ensure you use integer division (e.g., Math.floor(value / 2) in JavaScript/TypeScript).
  • All engagementValues in grid are non-negative.
  • It's guaranteed that grid and zoneTypes will be non-empty and have valid, rectangular dimensions (all rows have the same number of columns).

Examples

1

Example 1

Input:

grid = [[10, 20], [5, 15]], zoneTypes = [["NORMAL", "NORMAL"], ["NORMAL", "NORMAL"]]

Output:

45

Note:

Path (0,0)->(0,1)->(1,1): 10 (at 0,0) + 20 (at 0,1) + 15 (at 1,1) = 45. Path (0,0)->(1,0)->(1,1): 10 + 5 + 15 = 30. Max is 45.

2

Example 2

Input:

grid = [[10, 1], [1, 100]], zoneTypes = [["NORMAL", "COLD"], ["HOT", "NORMAL"]]

Output:

113

Note:

Effective values: (0,0)=10, (0,1)=floor(1/2)=0, (1,0)=1*3=3, (1,1)=100. Best path: (0,0) -> (1,0) -> (1,1) for 10 + 3 + 100 = 113.

3

Example 3

Input:

grid = [[10, 5, 2], [1, 100, 3], [4, 6, 20]], zoneTypes = [["NORMAL", "COLD", "NORMAL"], ["HOT", "NORMAL", "COLD"], ["NORMAL", "HOT", "NORMAL"]]

Output:

151

Note:

Effective values: (0,0)=10, (0,1)=2, (0,2)=2; (1,0)=3, (1,1)=100, (1,2)=1; (2,0)=4, (2,1)=18, (2,2)=20. The path (0,0)->(0,1)->(1,1)->(2,1)->(2,2) yields 10+2+100+18+20 = 150. The path (0,0)->(1,0)->(1,1)->(2,1)->(2,2) yields 10+3+100+18+20 = 151. Max is 151.

Constraints

Constraints & assumptions

  • 1 <= R, C <= 500, where R is the number of rows and C is the number of columns.
  • 0 <= grid[r][c] <= 1000 for all r, c.
  • zoneTypes[r][c] will always be one of "NORMAL", "HOT", or "COLD".

What interviewers evaluate

  • Correctness: The solution correctly calculates the maximum engagement score for all valid inputs.
  • Algorithm Efficiency: The chosen algorithm is optimal in terms of time and space complexity for the given constraints (e.g., O(RC) time, O(RC) or O(C) space).
  • Code Structure & Readability: The code is well-organized, easy to understand, and follows good programming practices.
  • Edge Case Handling: Correctly handles paths along the first row and first column, and single-cell grids.

Loading editor...