Apple Coding Interview Question: Modify an Array — Minimum Cost to Sort Ascending or Descending

Modify an Array

Given an array of integers, the cost to change an element is the absolute difference between its initial value and its new value. For example, if the element is initially 10, it can be changed to 7 or 13 for a cost of 3. Determine the minimum cost to sort the array either ascending or descending along its length.

Example

n = 6
arr = [0, 1, 2, 5, 6, 5, 7]

• Only arr[5] = 5 violates the order for an ascending sort.
• If the value 5 is increased to 6, the array will be sorted in ascending order: arr' = [0, 1, 2, 5, 6, 6, 7].
• The cost is |arr[5] - arr'[5]| = |5 - 6| = 1.

The key idea is to make the array monotonic, either nondecreasing or nonincreasing, while minimizing the total absolute change cost. A good solution usually evaluates both directions separately and returns the smaller cost. For each position, only values that break the target order need adjustment, so the problem is naturally suited to greedy reasoning combined with prefix/suffix optimization or dynamic programming. In the sample, only one element must be changed to restore ascending order, so the minimum cost is 1.