How should I practice Minimize Array Sum Difference?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Minimize Array Sum Difference associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Minimize Array Sum Difference

Learn this problem

● MediumAmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

Given an integer array, define its cost as the sum of absolute differences between adjacent elements: for array a of length n, cost = |a[0]-a[1]| + |a[1]-a[2]| + ... + |a[n-2]-a[n-1]|.

For example, for [5, 4, 0, 3, 3, 1] the cost is |5-4| + |4-0| + |0-3| + |3-3| + |3-1| = 10.

Remove as many elements as possible from the array so that the cost of the remaining array (computed over its new adjacent pairs) stays exactly equal to the original cost. Return the resulting array with the minimum possible number of elements.

An element can be safely removed when it does not contribute to the total cost, i.e. when its neighbors form a monotonic run through it (the absolute differences telescope). For instance, removing intermediate points along an increasing or decreasing run does not change the total.

Function

minimizeArraySumDifference(arr: int[]) → int[]

Examples

Example 1

arr = [5, 4, 0, 3, 3, 1]return = [5, 0, 3, 1]

Original sum of absolute differences: |5-4|+|4-0|+|0-3|+|3-3|+|3-1| = 10.
After removing elements to minimize the array while keeping the sum the same:
Solution 1: [5, 4, 0, 3, 1] => Sum = 10
Solution 2: [5, 0, 3, 1] => Sum = 10
Solution 2 is the acceptable answer as it has the minimum number of elements.

Example 2

arr = [6, 4, 4, 3, 3, 2]return = [6, 4, 3, 2]

Original sum of absolute differences: |6-4| + |4-4| + |4-3| + |3-3| + |3-2| = 2 + 0 + 1 + 0 + 1 = 4. Removing the redundant duplicate elements that lie on monotonic (non-increasing) runs leaves [6, 4, 3, 2], whose cost is |6-4| + |4-3| + |3-2| = 2 + 1 + 1 = 4, equal to the original. This matches the answer shown in the source image.

Constraints

The input is an array of integers.
The cost is the sum of absolute differences of adjacent elements.
The returned array must have exactly the same cost as the input array.
Among all valid arrays that preserve the original cost, return one with the minimum number of elements.
The first and last elements of the original array are always kept.