FastPrepMinimize Adjacent Squared-Difference Cost with One Insertion

Minimize Adjacent Squared-Difference Cost with One Insertion

McKinsey & Company logoMcKinsey & Company● MediumFULLTIMEOA

Problem statement

You are given an array arr of n positive integers, indexed from 0.

The cost of an array is the sum of squared differences between adjacent elements:

cost(arr) = sum((arr[i] - arr[i - 1])^2) for i from 1 through arr.length - 1.

Insert exactly one integer at any position in the array, including the beginning or the end, so that the resulting cost is minimized.

Return the minimum possible cost after this insertion.

Function

minimumSquaredDifferenceCost(arr: int[]) → long

Examples

Example 1

arr = [1,3,5,2,10]return = 49

The original cost is (1 - 3)^2 + (3 - 5)^2 + (5 - 2)^2 + (2 - 10)^2 = 81.

Two possible insertions are:

  1. Insert 4 between 3 and 5. The cost becomes (1 - 3)^2 + (3 - 4)^2 + (4 - 5)^2 + (5 - 2)^2 + (2 - 10)^2 = 79.
  2. Insert 6 between 2 and 10. The cost becomes (1 - 3)^2 + (3 - 5)^2 + (5 - 2)^2 + (2 - 6)^2 + (6 - 10)^2 = 49.

The minimum possible cost is 49.

Constraints

  • 2 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5

More McKinsey & Company problems

See McKinsey & Company hiring insights
Saved
public long minimumSquaredDifferenceCost(int[] arr) {
    // Write your code here
}
arr[1,3,5,2,10]
expected49
Checking account…