FastPrep
Problem · Sliding Window

Maximize Types After Freeing Shelves

Learn this problem
● MediumMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

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.

    Function

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

    Examples

    Example 1

    A = [2, 1, 2, 3, 2, 3, 2]R = 3return = 3
    It can be achieved by freeing shelves 2, 3, and 4. The remaining shelves contain item types {1, 2, 3}.

    Example 2

    A = [2, 3, 1, 1, 2]R = 2return = 3
    All three types {2, 3, 1} can still be stored by freeing the last two shelves.

    Example 3

    A = [20, 10, 10, 10, 30, 20]R = 3return = 3
    It can be achieved by freeing the first three shelves. The remaining item types are {10, 30, 20}.

    Example 4

    A = [1, 100000, 1]R = 3return = 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
    expected3
    checking account