Find minimum total range-increment to sort

Q: Find minimum total range-increment to sort

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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 ).

Find minimum total range-increment to sort

Overview

Comments (0)