Minimum Number of Increments on Subarrays to Form a Target Array
Updated
Problem statement
You are given an integer array target. You also have an array initial of the same length. Every value of initial starts at 0.
In one operation, you pick any subarray of initial and add 1 to each value in it. A subarray is a group of values that sit next to each other.
Return the smallest number of operations that turns initial into target.
The tests make sure the answer fits in a 32-bit integer.
For example, let target = [2, 1, 2]. Add 1 to the whole array: [1, 1, 1]. Add 1 at index 0: [2, 1, 1]. Add 1 at index 2: [2, 1, 2]. The answer is 3.
Function
minNumberOperations(target: int[]) → int
Complete the function minNumberOperations in the editor.
minNumberOperations has the following parameter:
int target[n]: the array you must build
Returns
int: the smallest number of operations
Examples
Example 1
target = [1,2,3,2,1]return = 3Add 1 to indexes 0 to 4: [1, 1, 1, 1, 1]. Add 1 to indexes 1 to 3: [1, 2, 2, 2, 1]. Add 1 at index 2: [1, 2, 3, 2, 1]. This is the target after 3 operations. It cannot be done in fewer. The answer is 3.
Example 2
target = [3,1,1,2]return = 4Add 1 to the whole array: [1, 1, 1, 1]. Add 1 at index 3: [1, 1, 1, 2]. Add 1 at index 0 two times: [2, 1, 1, 2], then [3, 1, 1, 2]. That is 4 operations. The answer is 4.
Example 3
target = [3,1,5,4,2]return = 7Add 1 to the whole array: [1, 1, 1, 1, 1]. Add 1 at index 0 two times: [3, 1, 1, 1, 1]. Add 1 to indexes 2 to 4: [3, 1, 2, 2, 2]. Add 1 to indexes 2 to 3 two times: [3, 1, 4, 4, 2]. Add 1 at index 2: [3, 1, 5, 4, 2]. That is 1 + 2 + 1 + 2 + 1 = 7 operations. The answer is 7.
Constraints
1 <= target.length <= 10^51 <= target[i] <= 10^5
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Server InvestmentRippling · OARippling interview questions
- Book Reading EveningsGoogle · OAGoogle interview questions
- Maximum Apples That Fit in a BoxVirtu Financial · OAVirtu Financial interview questions
- Minimum Project Bid CostNVIDIA · OANVIDIA interview questions
- Minimum AmountBelvedere Trading · OA
- Maximum Income from Asset TradingJefferies · OA
- Maximum Three-Server Difficulty ScoreVisa · OAVisa interview questions
- Economical TripAccenture · OAAccenture interview questions
- Best Time to Buy and Sell StockFlexTrade · OAFlexTrade interview questions