Minimum Team Size From Every Start
Updated
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]Starting at index 0, the team [1,2,3] has length 3. Starting at index 1, the shortest valid team is [2,3,2,1], of length 4. Starting at index 2, [3,2,1] has length 3. Neither of the last two suffixes contains all three talents, so their answers are -1.
Example 2
talent = [2,2,1,2]talentsCount = 2return = [3,2,2,-1]The shortest valid teams starting at indices 0, 1, and 2 are [2,2,1], [2,1], and [1,2]. Their lengths are 3, 2, and 2. The final student has talent 2 only, so the last answer is -1.
Example 3
talent = [1,1,2]talentsCount = 3return = [-1,-1,-1]Talent 3 never appears. No starting index can form a valid team, so every answer is -1.
Constraints
1 <= talent.length <= 2000001 <= talentsCount <= 2000001 <= talent[i] <= talentsCount <= 200000
More Cognizant interview questions
Similar questions at other companies
- Count Subarrays With Product Equal to KSalesforce · OASalesforce interview questions
- Count Servers With No Requests in a Time WindowIBM · OAIBM interview questions
- Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
- Count Subarrays Matching a Comparison PatternCapital One · OACapital One interview questions
- Count Subarrays with at Least K Equal-Fruit PairsTikTok · OATikTok interview questions
- Consistent LogsRippling · OARippling interview questions
- Minimum of Fixed-Window MaximaJuspay · OA
- Sliding-Window Means with IEEE Special ValuesHeadlands Technologies · OAHeadlands Technologies interview questions
- Maximum Decrypted ScoreMicrosoft · OAMicrosoft interview questions
- Maximum of Subarray MinimumsJP Morgan Chase · OAJP Morgan Chase interview questions