Minimum Increments for Stepwise Towers
Reported by candidates from ZipRecruiter's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
ZipRecruiter reported this one in September 2024, and the data structure question is a trap: you don't need one. It looks like a tower problem that wants a heap or a DP table, but the whole thing collapses to arrays and a single pass. You get an array of heights, you can only add blocks, and the final shape must be a perfect staircase going up or down by exactly one. If you blank on the setup during the OA, StealthCoder can sit invisibly on your screen as a safety net. Here's the idea so you don't need it.
The problem
You are given an integer array towers, where towers[i] is the height of the ith tower. In one move, add exactly one block to any tower. Blocks cannot be removed. Make the entire sequence stepwise in either direction: increasing: every height is exactly one greater than the previous height; or decreasing: every height is exactly one less than the previous height. Return the minimum number of moves required. Function minimumStepwiseIncrements(towers: int[]) → long Examples Example 1 towers = [1,4,3,2] return = 4 Raise the first tower from 1 to 5. The result [5,4,3,2] is stepwise decreasing and costs four moves. Example 2 towers = [5,7,9,4,11] return = 9 The cheapest target is [7,8,9,10,11], requiring 2 + 1 + 0 + 6 + 0 = 9 added blocks. Constraints 1 <= towers.length <= 100000 0 <= towers[i] <= 1000000000 The answer fits in a signed 64-bit integer.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is that a staircase is fully determined by one number. Increasing means towers[i] must end at least at base + i, where base is the start value. Since you can only add, base + i >= towers[i] for every i, so base = max(towers[i] - i). Every tower then lands at base + i, and the cost is the sum of (base + i - towers[i]). Decreasing is the mirror: the target is base - i, with base = max(towers[i] + i). Compute both costs and return the smaller. Check example 2: towers[i]-i gives 5,6,7,1,7, so base is 7, and the targets are 7 through 11, costing 9. The pitfall is overflow. With 100000 towers and heights up to 1e9, the sum needs a 64-bit integer. Also don't forget the decreasing direction, since example 1 needs it. If you freeze live, StealthCoder is the hedge, but this is two passes and a max.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill Minimum Increments for Stepwise Towers cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass ZipRecruiter's OA.
ZipRecruiter reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Minimum Increments for Stepwise Towers FAQ
What's the trick in Minimum Increments for Stepwise Towers?+
Fix the staircase by its starting value. For the increasing case, the base must be at least towers[i] - i for every i, so take the max. Then each tower's cost is its target minus its current height. Do the mirror for decreasing and take the minimum.
Do I need dynamic programming or a heap?+
No. The answer comes from a single formula per direction. You compute one max, then one sum. That's O(n) time and O(1) extra space. If you reach for DP, you're overcomplicating it, because the target sequence is forced once the base is chosen.
How do I handle the decreasing direction?+
Target heights are base - i, and each must be at least towers[i], so base = max(towers[i] + i). Cost is the sum of (base - i - towers[i]). Run both directions, compare totals, and return the smaller. Example 1 only works because of this case.
What edge cases break solutions on this problem?+
Overflow is the big one. Use a 64-bit type for the sum, since n can reach 100000 and heights reach 1e9. A single tower costs zero. Towers already forming a staircase cost zero. Heights of 0 are fine because you only ever add blocks.
How do I prepare for this in 48 hours?+
Practice the pattern of reducing a constrained sequence to one free parameter. Write the increasing and decreasing versions by hand, then test on both examples. Rehearse the max-offset idea until it's automatic. Spend the rest of your time on array and prefix-style problems.