FastPrep
Problem · Array

Get the Fewest Moves (~Operations~)~

● MediumAmazonNEW GRADOA
See Amazon hiring insights

Similar to LC 2772

You are given an integer list named data. The objective is to adjust all elements in this list so that each becomes zero. You can carry out the following move any number of times:

  • Pick a prefix portion of the list and either increase or decrease every element in that prefix by 1.

    • Your task is to figure out the fewest moves required to turn all the elements into zero.

    A prefix is a contiguous group of items that includes the first element in the cart. for example [1], [1,2], [1,2,3] are prefixes of [1,2,3,4,5].

    The function you implement should print a single number — the minimum number of steps needed.

    A prefix segment refers to a continuous collection of elements starting from the first item in the sequence. For instance, [1], [1, 2], [1, 2, 3], and so on are valid prefixes of the sequence [1, 2, 3, 4, 5].

    It is assured that turning all values in the list to zero is always achievable.

    Examples
    01 · Example 1
    data = [3, 2, 0, 0, -1]
return = 5
    Step 1: Select a prefix of length 1 and subtract 1 from it. After this step, the list updates to [2, 2, 0, 0, -1]. Step 2: Choose the first 2 elements and decrease them by 1. Now, the list becomes [1, 1, 0, 0, -1]. Step 3: Pick a prefix containing the first 4 elements and reduce each by 1. After performing this, the list changes to [0, 0, -1, -1, -1]. Step 4: Select the first 2 elements and decrease them by 1. The updated list is [-1, -1, -1, -1, -1]. Step 5: Finally, choose the entire list (prefix length 5) and add 1 to every element. The list becomes [0, 0, 0, 0, 0].
    02 · Example 2
    data = [3, 2, 1]
return = 3
    The most optimal sequence of steps is as follows: Step 1: Choose a prefix of size 2 and reduce each element by 1. After this operation, the list becomes [2, 1, 1]. Step 2: Choose a prefix of size 1 and reduce its value by 1. The list now looks like [1, 1, 1]. Step 3: Select a prefix covering 3 elements and decrease all by 1. After this, the list turns into [0, 0, 0]. The total number of operations required is 3. It is not possible to turn all elements into zero using fewer steps.
    Constraints
  • 1 ≤ n ≤ 10^5
  • -10^9 ≤ data[i] ≤ 10^9
    • More Amazon problems
    drafts saved locally
    public int minOperations(int[] data) {
  // write your code here
}
    data[3, 2, 0, 0, -1]
    expected5
    sign in to submit