Minimize Array Sum Difference
Updated
Problem statement
The cost of an array is the sum of the absolute differences between neighbors. For an array a of length n, the cost is |a[0] - a[1]| + |a[1] - a[2]| + ... + |a[n-2] - a[n-1]|. An array with one element has cost 0.
You are given an array arr. Remove as many elements as you can, so that the cost of what is left equals the cost of arr. The elements that are left keep their order, and the cost uses their new neighbors.
Return the elements that are left. The shortest such array always has the same values, so there is only one answer. If every element is the same, the cost is 0 and one element is left.
For example, let arr = [1, 3, 3, 2]. Its cost is 2 + 0 + 1 = 3. Removing one 3 gives [1, 3, 2], which also costs 2 + 1 = 3. Removing 1 or 2 instead, or any more elements, would lower the cost. The answer is [1, 3, 2].
Function
minimizeArraySumDifference(arr: int[]) → int[]
Complete the function minimizeArraySumDifference in the editor.
minimizeArraySumDifference has the following parameter:
int[] arr: the array
Returns
int[]: the shortest array of remaining elements with the same cost
Examples
Example 1
arr = [5, 4, 0, 3, 3, 1]return = [5, 0, 3, 1]The cost is |5 - 4| + |4 - 0| + |0 - 3| + |3 - 3| + |3 - 1| = 1 + 4 + 3 + 0 + 2 = 10. The values fall from 5 to 0, rise to 3, then fall to 1. The 4 sits inside the fall from 5 to 0, so it can go. One of the two 3s can also go, because their difference is 0. That leaves [5, 0, 3, 1], with cost 5 + 3 + 2 = 10. [5, 4, 0, 3, 1] also costs 10, but it is longer. No 3 or fewer elements keep the cost at 10. The answer is [5, 0, 3, 1].
Example 2
arr = [6, 4, 4, 3, 3, 2]return = [6, 2]The cost is |6 - 4| + |4 - 4| + |4 - 3| + |3 - 3| + |3 - 2| = 2 + 0 + 1 + 0 + 1 = 4. The values never go up, so every middle element can go. [6, 2] costs |6 - 2| = 4, the same as before. One element alone would cost 0. The answer is [6, 2].
Constraints
1 <= n <= 10^5, wherenis the length ofarr0 <= arr[i] <= 10^9
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
- Minimum Cost to Merge Values into OnePayPal · OAPayPal interview questions
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum ScoreNVIDIA · OANVIDIA interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions