FastPrep
Problem · Array

Max Subarray Filled With Zeros

Learn this problem
● HardGoogleOA
See Google hiring insights

Problem statement

Given an array of non-negative integers, you can perform two operations.

Operation 1: Choose an index i with A[i] > 0 and set A[i] = A[i] - 1.

Operation 2: Choose an index i and set A[i] = 0.

Return the maximum length of a contiguous subarray that can be filled with zeros by performing Operation 1 at most X times and Operation 2 at most Y times.

Function

maxSubarrayFilledWithZeros(A: int[], X: int, Y: int) → int

Examples

Example 1

A = [4, 3, 0, 1]X = 2Y = 1return = 3

Step 1: [4, 0, 0, 1] X=2, Y=0

Step 2: [4, 0, 0, 0] X=1, Y=0

Therefore, the output is 3.

Constraints

  • 1 <= A.length <= 2 * 10^5
  • 0 <= A[i], X <= 10^9
  • 0 <= Y <= A.length

More Google problems

drafts saved locally
public int maxSubarrayFilledWithZeros(int[] A, int X, int Y) {
  // write your code here
}
A[4, 3, 0, 1]
X2
Y1
expected3
checking account