Assay Ladder Retuning

Minimally increased array with each value at least a given gap above the prior

EasyGreedyArraysMonotone Construction

A genetics lab runs an ordered ladder of assays. The integer setting for assay i is initially levels[i]. Negative settings are allowed because settings are measured relative to a calibration baseline.

Before the run, the lab may increase any setting by an integer amount, but it may not decrease a setting or change the assay order. Each assay after the first must have a setting at least gap greater than the preceding assay.

Return the final settings that minimize the total increase across all assays. In other words, return an integer array adjusted of the same length such that:

  • adjusted[i] >= levels[i] for every index;
  • adjusted[i] >= adjusted[i - 1] + gap for every index after the first;
  • the sum of adjusted[i] - levels[i] is as small as possible.

The minimizing array is unique. If levels is empty, return an empty array.

Examples

Example 1

Input: levels = [2,1,8,4], gap = 3
Output: [2,5,8,11]

The first assay can keep its setting. The second must be raised to meet the required gap, the third already has enough separation, and the fourth must be raised above the third.

Example 2

Input: levels = [-4,-4,-4], gap = 2
Output: [-4,-2,0]

Equal negative starting settings still need separation. Keep the first setting and raise each subsequent setting only as much as necessary.

Example 3

Input: levels = [-5,0,7], gap = 4
Output: [-5,0,7]

The existing settings already meet every required gap, so no adjustment is needed.

Constraints

  • 0 <= levels.length <= 10000
  • -1000000 <= levels[i] <= 1000000
  • 1 <= gap <= 1000000
  • All settings and adjustments are integers.

The intended solution takes O(n) time and O(1) auxiliary space, excluding the returned array. Final settings can exceed the original input range; JavaScript Number represents every possible result exactly under these constraints.

Hints

Show hint 1

Increasing an earlier setting can only make the requirement for the next setting harder to satisfy.

Show hint 2

Once the preceding final setting is fixed, what is the smallest permitted setting for the current assay?

Follow-up questions

What an interviewer might ask once you have a working solution.

  • If every assay also has a maximum permitted setting, how would you detect whether any valid adjustment exists?
  • How would you emit the adjusted settings from a stream without storing the entire input or output?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem