Frontend School

Optimal Frame Selection Path

DSA
medium

Optimal Frame Selection Path

Medium
Dynamic Programming
2D DP
Grid

Overview

At Lenskart, we're constantly innovating to provide the best customer experience, both online and in-store. Our AI-powered styling assistant helps customers discover frames that best suit their preferences. This system often presents a curated selection of frames in a grid-like interface. To optimize the customer's journey through this selection, we need to identify the most engaging path, maximizing their overall satisfaction.

What you need to do / Task

You are tasked with implementing a function that calculates the maximum possible "customer satisfaction score" a customer can achieve by navigating through a grid of frames.

Given a 2D array (grid) representing frames, where frames[r][c] is the satisfaction score associated with the frame at row r and column c:

  1. A customer starts by selecting any frame in the first row (row 0).
  2. From a chosen frame at (r, c), the customer can only move to a frame in the next row (r+1) at one of the following relative column positions: c-1, c, or c+1 (if valid).
  3. The path ends when a frame in the last row (row R-1) is selected.
  4. Your function should return the maximum total satisfaction score achievable for any valid path from the first row to the last row.

Input & output

Input:

  • frames: A 2D array of integers, frames[r][c], representing the satisfaction score for the frame at row r and column c.

Output:

  • An integer representing the maximum total satisfaction score achievable.

Examples

1

Example 1

Input:

frames = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output:

18

Note:

The path frames[0][2](3) -> frames[1][2](6) -> frames[2][2](9) yields a total score of 3 + 6 + 9 = 18. This is the maximum possible path sum.

2

Example 2

Input:

frames = [[-10, -5, -1], [-20, -15, -12], [-30, -25, -22]]

Output:

-35

Note:

The path frames[0][2](-1) -> frames[1][2](-12) -> frames[2][2](-22) yields -1 + (-12) + (-22) = -35. This is the maximum possible score, as maximizing with negative numbers means choosing the path with the smallest absolute sum.

3

Example 3

Input:

frames = [[10], [5], [12]]

Output:

27

Note:

With a single column, there is only one possible path: frames[0][0](10) -> frames[1][0](5) -> frames[2][0](12). The total score is 10 + 5 + 12 = 27.

Constraints

Constraints & assumptions

  • 1 <= R (number of rows) <= 500
  • 1 <= C (number of columns) <= 500
  • -100 <= frames[r][c] <= 100 (Satisfaction scores can be negative, indicating a poor fit or undesirable frame.)
  • The grid will always be non-empty.
  • All rows will have the same number of columns.

What interviewers evaluate

  • Correctness: The solution correctly handles all valid inputs, including edge cases like single-column grids or grids with negative scores, and produces the accurate maximum path sum.
  • Efficiency: The solution has optimal time and space complexity for the given constraints, demonstrating an understanding of dynamic programming principles.
  • Code Quality: The code is well-structured, readable, and follows good programming practices (e.g., meaningful variable names, clear logic).
  • Problem-Solving Approach: The candidate clearly articulates the chosen approach, identifies subproblems, and explains the recurrence relation and base cases.

Loading editor...