FastPrepMinimize Array Sum Difference
Problems/Minimize Array Sum Difference

Minimize Array Sum Difference

Amazon logoAmazon● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

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, where n is the length of arr
  • 0 <= 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

Interview reports that mention this question

  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)
  • Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)
See Amazon hiring insights
Saved
class Solution {
    public int[] minimizeArraySumDifference(int[] arr) {
      // write your code here
    }

}
Checking account…