Nedbank Mock: Pixel Intensity (Q73)

[sudosf]

Problem

Given a 2D grid of pixel intensities, make each column strictly increasing top to bottom by only increasing values (cost = units increased). Find minimum total cost.

Source

Nedbank VAS HackerRank Assessment - Q73
Tags: Easy, 2D Arrays, Comparison

Constraints

• 1 <= n, m <= 10^5
• 1 <= pixelIntensity[i][j] <= 10^9
• n * m <= 10^6

Example

pixelIntensity = [[2,5],[7,4],[3,5]]
Output: 9
// Increase [2][0] by 5 (value 3 -> 8)
// Increase [1][1] by 2 (value 4 -> 6)
// Increase [2][1] by 2 (value 5 -> 7)

Approach Hints

• Process each column independently - rows and columns are not coupled
• Walk top to bottom: each cell must be strictly greater than the cell above it
• You cannot decrease, only increase - what's the minimum value each cell must become?

Notes

Language: Java
Return type is long - accumulate cost as long to avoid overflow.