FastPrepEqualize Arrays with Prefix and Suffix Increments
Problem · Array

Equalize Arrays with Prefix and Suffix Increments

Learn this problem
● MediumMicrosoft logoMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

You are given two integer arrays, source and target, of equal length n.

In one operation, choose an index i and perform exactly one of these actions:

  • Add 1 to every element in the prefix source[0..i].
  • Add 1 to every element in the suffix source[i..n - 1].

Return the minimum number of operations required to make source equal to target. If the transformation is impossible, return -1.

The source's numeric bounds require 64-bit values, so this practice contract uses long arrays and returns a long.

Complete getMinOperations for the given source and target arrays.

Function

getMinOperations(source: long[], target: long[]) → long

Examples

Example 1

source = [1, 2, 2]target = [2, 2, 3]return = 2

Increment the prefix ending at index 0, producing [2, 2, 2]. Then increment the suffix starting at index 2, producing [2, 2, 3].

Example 2

source = [1, 1, 1]target = [3, 3, 3]return = 2

Increment the whole array twice. A whole-array increment may be represented as either a prefix ending at index n - 1 or a suffix starting at index 0.

Example 3

source = [0, 0, 0, 0, 0]target = [1, 0, 1, 0, 1]return = -1

The required increment profile has two separate downward drops, but only one unit is required at the first position. No combination of prefix and suffix increments can create that profile.

Constraints

  • 1 <= n <= 100000
  • source.length = target.length = n
  • -10^13 <= source[i], target[i] <= 10^13
  • The correct minimum, when it exists, fits in a signed 64-bit integer.

More Microsoft problems

drafts saved locally
public long getMinOperations(long[] source, long[] target) {
  // write your code here
}
source[1, 2, 2]
target[2, 2, 3]
expected2
checking account