FastPrepMinimize Adjacent Squared-Difference Cost with One Insertion

Minimize Adjacent Squared-Difference Cost with One Insertion

Scale AI logoScale AI● MediumNEW GRADOA
Learn

Problem statement

The cost of an integer array is the sum of (values[i]-values[i-1])² over all adjacent pairs.

Insert exactly one integer at any position, including either end, and return the minimum possible cost. The inserted integer may be any signed 32-bit value.

Function

minimumSquaredDifferenceCost(values: int[]) → long

Examples

Example 1

values = [1,4,7,4]return = 23

Insert 5 between 4 and 7: 9+1+4+9=23.

Example 2

values = [1,5]return = 8

Insert 3 and split a gap of four into two gaps of two.

Example 3

values = []return = 0

After insertion, an originally empty array still has no adjacent pair.

Constraints

  • 0 <= values.length <= 100000.
  • -1000000000 <= values[i] <= 1000000000.
  • The answer fits in a signed 64-bit integer.

More Scale AI problems

See Scale AI hiring insights
public long minimumSquaredDifferenceCost(int[] values) {
    // write your code here
}
values[1,4,7,4]
expected23
Checking account…