Interview Questions/Coding/Campus Grid Profit Gap

Campus Grid Profit Gap

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Campus Grid Profit Gap

A campus table stores numeric readings in a grid. A valid comparison chooses an earlier cell and a later cell such that the later cell is strictly below and strictly to the right of the earlier cell. The profit gap of such a comparison is laterValue minus earlierValue. Values may be negative, and the best valid gap can also be negative if every later value is smaller. Input Format: You are given a 2D integer array grid. Output Format: Return the maximum profit gap among all valid cell comparisons.

Examples

Example 1

Input:

grid = [[1, 2, -1], [4, 5, 6], [7, 8, 9]]

Output:

Explanation: Choose grid[2][2]=9 after grid[0][0]=1. The gap is 8, so the output is 8.

Approach hint

For every cell, know the smallest value seen in the upper-left rectangle.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp