FastPrep
Problem · Sliding Window

Maximize Types After Freeing Shelves

● MediumMicrosoftFULLTIMEOA
See Microsoft hiring insights

A storeroom is used to organize items stored in it on N shelves. Shelves are numbered from 0 to N-1. The K-th shelf is dedicated to items of only one type, denoted by a positive integer A[K].

Recently it was decided that it is necessary to free R consecutive shelves. Shelves cannot be reordered. What is the maximum number of types of items that can still be stored in the storeroom after freeing R consecutive shelves?

Given:

  • an array A of N integers representing types of items stored on storeroom shelves.
  • an integer R representing the number of consecutive shelves to be freed.

    • Returns the maximum number of different types of items that can be stored in the storeroom after freeing R consecutive shelves.

    Examples
    01 · Example 1
    A = [2, 1, 2, 3, 2, 3, 2]
R = 3
return = 2
    It can be achieved by freeing shelves 2, 3, 4. The remaining shelves contain item types {2, 3}.
    02 · Example 2
    A = [2, 3, 1, 1, 2]
R = 2
return = 3
    All three types {2, 3, 1} can still be stored by freeing the last two shelves.
    03 · Example 3
    A = [20, 10, 10, 10, 30, 20]
R = 3
return = 3
    It can be achieved by freeing the first three shelves. The remaining item types are {10, 30, 20}.
    04 · Example 4
    A = [1, 100000, 1]
R = 3
return = 0
    All shelves need to be freed, leaving no items.
    Constraints
    • N is an integer within the range [1..100,000].
    • R is an integer within the range [1..N].
    • Each element of array A is an integer within the range [1..100,000].
    More Microsoft problems
    drafts saved locally
    public int maximizeTypesAfterFreeingShelves(int[] A, int R) {
  // write your code here
}
    A[2, 1, 2, 3, 2, 3, 2]
    R3
    expected2
    sign in to submit