FastPrepMaximize Remaining Item Types After Clearing Consecutive Shelves

Maximize Remaining Item Types After Clearing Consecutive Shelves

Marshall Wace logoMarshall Wace● MediumNEW GRADOA

Problem statement

Array A describes a row of shelves: A[i] is the item type on shelf i.

Clear a block of exactly R adjacent shelves. You cannot reorder the shelves before choosing the block. Count the different item types left on the shelves outside that block.

Return the largest count you can get by choosing which block to clear. If every shelf is cleared, the count is 0.

Function

solution(A: int[], R: int) → int

Examples

Example 1

A = [2,1,2,3,2,2]R = 3return = 2

Clear shelves at indices 2, 3 and 4. The remaining labels are [2,1,2], which contain two types.

Example 2

A = [2,3,1,1,2]R = 2return = 3

Clearing the final two shelves leaves labels [2,3,1], retaining all three types.

Example 3

A = [20,10,10,10,30,20]R = 3return = 3

Clear the first three shelves. Labels [10,30,20] remain, with three distinct types.

Example 4

A = [1,100000,1]R = 3return = 0

Every shelf is cleared, so no item type remains.

Constraints

  • 1 <= A.length <= 100000.
  • 1 <= R <= A.length.
  • 1 <= A[i] <= 2147483647.

More Marshall Wace problems

See Marshall Wace hiring insights
Saved
public int solution(int[] A, int R) {
    // Write your solution here.
}
A[2,1,2,3,2,2]
R3
expected2
Checking account…