FastPrepFastPrep
Problem Brief

Get the Fewest Moves (~Operations~)~

NEW GRADOA
See Amazon online assessment and 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.

    1Example 1

    Input
    data = [3, 2, 0, 0, -1]
    Output
    5
    Explanation
    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].

    2Example 2

    Input
    data = [3, 2, 1]
    Output
    3
    Explanation
    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

    Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 10^5
  • -10^9 ≤ data[i] ≤ 10^9
    • public int minOperations(int[] data) {
  // write your code here
}
    Input

    data

    [3, 2, 0, 0, -1]

    Output

    5

    Sign in to submit your solution.