FastPrep
Problem · Array

Minimum Team Size From Every Start

Learn this problem
● MediumMicrosoft logoMicrosoftNEW GRADOA
See Microsoft hiring insights

Problem statement

Students stand in a fixed order. The integer talent[i] is the talent of the student at index i, and every talent is between 1 and talentsCount.

A valid team is a contiguous group that contains at least one student with each talent from 1 through talentsCount.

For every starting index i, find the minimum length of a valid team whose first student is at index i. Return an array answer of the same length as talent, where answer[i] is that minimum length. If no valid team can start at i, set answer[i] to -1.

Function

minimumTeamSizes(talent: int[], talentsCount: int) → int[]

Examples

Example 1

talent = [1,2,3,2,1]talentsCount = 3return = [3,4,3,-1,-1]

The shortest complete windows beginning at the first three indices have lengths 3, 4, and 3. The suffixes beginning at the last two indices omit at least one talent, so their answers are -1.

Constraints

  • 1 <= talent.length <= 200000
  • 1 <= talentsCount <= 200000
  • 1 <= talent[i] <= talentsCount

More Microsoft problems

drafts saved locally
public int[] minimumTeamSizes(int[] talent, int talentsCount) {
  // Write your code here.
}
talent[1,2,3,2,1]
talentsCount3
expected[3,4,3,-1,-1]
checking account