Frontend School

Optimal Package Consolidation Path

DSA
hard

Optimal Package Consolidation Path

Hard
Dynamic Programming
2D DP
Grid
Optimization

Overview

Shiprocket operates large-scale sorting and consolidation facilities. Optimizing the flow of packages through these facilities is critical for efficiency and profitability. This problem simulates a scenario where a package consolidation robot needs to navigate a grid-based sorting area, picking up packages, while adhering to a strict total weight limit to prevent equipment overload or delays.

What you need to do / Task

Implement the function maxConsolidatedValue that determines the maximum total value of packages that can be collected along a valid path from the top-left cell (0, 0) to the bottom-right cell (R-1, C-1) of a given grid. You can only move right or down at each step.

Each cell (r, c) in the grid contains a package object with two properties: value (representing the profit or priority of the package) and weight (representing its physical weight or handling complexity). The total weight of all packages collected along any path must not exceed maxCapacity.

Input & output

Input:

  • grid: A 2D array (matrix) where grid[r][c] is an object { value: number, weight: number } representing the package at cell (r, c). R is the number of rows, C is the number of columns.
  • maxCapacity: A number representing the maximum total weight allowed for a path.

Output:

  • A number representing the maximum total value of packages collected along a valid path. If no path exists that reaches the bottom-right cell within the maxCapacity, return 0.

Clarifications

  • All value and weight properties of packages are positive integers.
  • The starting cell (0,0) and the ending cell (R-1, C-1) are always included in the path and their respective package values and weights contribute to the total.
  • If multiple paths yield the same maximum value, any one of them is valid.
  • If maxCapacity is too low such that even the first package at (0,0) exceeds it, then no path can start, and the result should be 0 (as per the rule for no valid path).

Examples

1

Example 1

Input:

grid = [[{ value: 10, weight: 1 }, { value: 5, weight: 1 }], [{ value: 20, weight: 1 }, { value: 10, weight: 1 }]], maxCapacity = 3

Output:

40

Note:

Grid: [10,1] [5,1] [20,1] [10,1]

Path 1: (0,0) -> (0,1) -> (1,1) Value: 10 + 5 + 10 = 25 Weight: 1 + 1 + 1 = 3. Valid (3 <= 3).

Path 2: (0,0) -> (1,0) -> (1,1) Value: 10 + 20 + 10 = 40 Weight: 1 + 1 + 1 = 3. Valid (3 <= 3).

Maximum value is 40.

2

Example 2

Input:

grid = [[{ value: 10, weight: 2 }, { value: 100, weight: 1 }], [{ value: 1, weight: 10 }, { value: 5, weight: 1 }]], maxCapacity = 4

Output:

115

Note:

Grid: [10,2] [100,1] [1,10] [5,1]

Path 1: (0,0) -> (0,1) -> (1,1) Value: 10 + 100 + 5 = 115 Weight: 2 + 1 + 1 = 4. Valid (4 <= 4).

Path 2: (0,0) -> (1,0) -> (1,1) Value: 10 + 1 + 5 = 16 Weight: 2 + 10 + 1 = 13. Invalid (13 > 4).

Maximum value is 115.

3

Example 3

Input:

grid = [[{ value: 10, weight: 5 }]], maxCapacity = 3

Output:

0

Note:

The grid is 1x1. The package at (0,0) has weight 5. The maxCapacity is 3. Since the initial package's weight already exceeds the capacity, no path is valid. Returns 0.

Constraints

Constraints & assumptions

  • 1 <= R, C <= 50 (number of rows and columns)
  • 1 <= grid[r][c].value <= 100
  • 1 <= grid[r][c].weight <= 20
  • 1 <= maxCapacity <= 1000
  • Time complexity: Should be efficient enough for the given constraints (e.g., O(R * C * maxCapacity)).
  • Space complexity: Should be efficient enough for the given constraints (e.g., O(R * C * maxCapacity)).

What interviewers evaluate

  • Correct application of 2D dynamic programming principles with an additional state dimension.
  • Accurate handling of base cases and state transitions.
  • Efficient management of the maxCapacity constraint, including proper initialization and invalid state handling.
  • Optimal time and space complexity for the given constraints.
  • Code clarity, structure, and readability.

Loading editor...