FastPrep
Problem · Array

Find Maximum Zeroes

Learn this problem
● MediumAmazonINTERNOA
See Amazon hiring insights

Problem statement

In an Amazon analytics team, the Analysts collectively have a preference for the number zero and a disapproval towards negative numbers. Their objective is to determine the maximum number of zeroes achievable after performing a series of operations (possibly zero) on an array, all while avoiding negative values.

Formally, given an array arr of size n of positive integers, the Analysts can perform the following operation any number of times (possibly zero):

  • Choose a prefix of size s (1 ≤ s ≤ n) that doesn't contain any zero (there is no index i such that arr[i] = 0 and 1 ≤ i ≤ s).
  • Decrease all values of this prefix by one, i.e., set arr[i] = arr[i] - 1 for all 1 ≤ i ≤ s.

Find the maximum number of zeroes that the array arr can contain after performing any (possibly zero) number of operations on the array.

Note that a prefix of size s in an array arr is the first s elements in this array, for example, the prefix of size 3 of array [3, 1, 5, 5, 2] is [3, 1, 5].

Function

findMaximumZeroes(arr: int[]) → int

Complete the function findMaximumZeroes in the editor.

findMaximumZeroes has the following parameters:

  • int arr[n]: the elements of the array.

Returns

int: the maximum number of zeroes that the array arr can contain after performing any (possibly zero) number of operations on the array.

𓍢ִ໋🌷͙֒ ᰔᩚ A massive thank you to chizzy_elect༊·° ♡

Examples

Example 1

arr = [4, 3, 5, 5, 3]return = 3
Example 1 illustration
If we perform the following operations: No further operations can be done on the array, and the number of zeroes in arr is 3, which is the maximum possible.

Example 2

arr = [2, 5, 9, 3, 5]return = 1
Example 2 illustration
If we perform the following operations: No further operations can be done on the array, and the number of zeroes in arr is 1, which is the maximum possible.

Constraints

  • 1 ≤ n ≤ 2 * 105
  • 1 ≤ arr[i] ≤ 109

    • More Amazon problems

    drafts saved locally
    public int findMaximumZeroes(int[] arr) {
  // write your code here
}
    arr[4, 3, 5, 5, 3]
    expected3
    checking account