Shortest Talent-Covering Team Starting At Each Index
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
There are `n` students in a line. Each student has exactly one talent represented by an integer from `1` to `talentsCount`. A valid team is a contiguous subarray that contains every talent from `1` to `talentsCount` at least once. For every starting index, return the length of the shortest valid team that starts at that index, or `-1` if no such team exists.
Function signature:
```python
def shortest_complete_teams(talents_count: int, talent: list[int]) -> list[int]:
pass
```
Constraints:
- `1 <= talents_count <= n <= 100000`.
- Each `talent[i]` is between `1` and `talents_count`.
- The solution should be `O(n)` or close to it.
- Return one answer per starting index.
Examples:
```text
talents_count = 3, talent = [1, 2, 3, 2, 1]
Output: [3, 4, 3, -1, -1]
```
Quick Answer: Practice a sliding-window coding question where each start index needs the shortest contiguous team containing every talent type. This prompt targets hash map counts, two-pointer window management, and O(n) reasoning for large arrays.
For each starting index in an array of talents, return the length of the shortest contiguous subarray starting there that contains every talent from 1 to talents_count, or -1 if none exists.
Constraints
- 1 <= talents_count <= len(talent).
- Each talent value is in the range 1..talents_count.
Examples
Input: (3, [1,2,3,2,1])
Expected Output: [3,4,3,-1,-1]
Input: (1, [1,1,1])
Expected Output: [1,1,1]
Hints
- Use one right pointer shared across all left starts.
- Shrink from the left after recording the answer.