Find minimum total range-increment to sort
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an integer array `power[0..n-1]` representing computational power of `n` servers.
You may perform the following operation any number of times:
- Choose a **contiguous segment** `[l, r]` (0-indexed, `0 <= l <= r < n`)
- Choose an integer `x >= 0`
- Increase every element in that segment by `x` (i.e., for all `i in [l, r]`, set `power[i] += x`)
Your goal is to make the final array **non-decreasing** (i.e., `power[i] <= power[i+1]` for all valid `i`).
Let the “cost” be the **sum of all chosen `x` values** across all operations (segment length does not affect cost). Compute the **minimum possible cost**.
Example:
- `n = 5`, `power = [3, 4, 1, 6, 2]`
- One optimal sequence:
- add `3` to subarray `[2, 4]` → `[3, 4, 4, 9, 5]`
- add `4` to subarray `[4, 4]` → `[3, 4, 4, 9, 9]`
- Minimum cost = `3 + 4 = 7`
Complete the function:
- `findMinimumSum(power)` → returns an integer: the minimum achievable total cost.
Assumptions:
- `power[i]` are integers; only increases are allowed (`x >= 0`).
Quick Answer: This question evaluates algorithmic problem-solving skills in array manipulation and optimization, focusing on reasoning about range-increment operations, cost minimization, and preserving non-decreasing order.
Return the minimum total x-cost of range increments needed to make the array non-decreasing.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([3,4,1,6,2],)
Expected Output: 7
Explanation: Drops of 3 and 4 require total cost 7.
Input: ([1,2,3],)
Expected Output: 0
Explanation: Already non-decreasing costs zero.
Input: ([5,1,1],)
Expected Output: 4
Explanation: One suffix increment of 4 is enough.
Hints
- Each adjacent drop must be paid for at least once.
- A suffix increment realizes exactly the sum of positive drops.