AMAZON Coding Question – Solved

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 sequenceData 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 sequenceData[i] = 0 and 1 ≤ i ≤ s). - Decrease all values of this prefix by one, i.e., set sequenceData[i] = sequenceData[i] - 1 for all 1 ≤ i ≤ s. Find the maximum number of zeroes that the array sequenceData can contain after performing any (possibly zero) number of operations on the array. Note that a prefix of size s in an array sequenceData 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]. Example: n = 5 sequenceData = [4, 3, 5, 5, 3] If we perform the following operations: - No further operations can be done on the array, and the number of zeroes in sequenceData is 3, which is the maximum possible. Function Description: Complete the function calculateMaxZeroes in the editor below. calculateMaxZeroes has the following parameters: int sequenceData[]: the elements of the array Returns: int: the maximum number of zeroes that the array sequenceData can contain after performing any (possibly zero) number of operations on the array. Constraints: 1 ≤ n ≤ 2 * 10^5 1 ≤ sequenceData[i] ≤ 10^9 Input Format for Custom Testing: The first line contains an integer, n, denoting the number of elements in sequenceData. Each of the next n lines contains an integer describing sequenceData[i]. Sample Case 0: Sample Input: 2 sequenceData[] size n = 5 sequenceData = [2, 5, 9, 3, 5] Sample Output: 1 Explanation: If we perform the following operations: - [2, 5, 9, 3, 5] → [1, 4, 8, 3, 5] - No further operations can be done on the array, and the number of zeroes in sequenceData is 1, which is the maximum possible. Prefix Size: 4 → New Array: [1, 4, 8, 3, 5] → [0, 3, 7, 2, 5]