Quick Overview

For a line of talents, each tagged with one subject, and a required count k of distinct subjects, return for every starting position the length of the shortest contiguous block from there covering at least k distinct subjects, or -1 if none exists. It tests efficient counting of distinct values across overlapping ranges and exact handling of impossible starts.

Shortest Contiguous Team From Each Start Covering K Distinct Subjects

Company: Walmart Labs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A teacher is taking a line of contestants, called talents, to a series of competitions. Each talent is strong in exactly one subject, given as an integer, and the talents keep a fixed left-to-right order. A competition needs a team that covers at least `k` different subjects, and a team must be a contiguous block of the line. For every starting position, find the length of the shortest block that starts there and covers at least `k` distinct subjects, or report that no block starting there can. The candidate did not remember whether a start with no valid block is reported as 0 or as -1; this version uses -1, as fixed in Rules below. ### Function Signature ```python def shortest_teams(talents: list[int], k: int) -> list[int]: ``` ### Rules - `talents[j]` is the subject of the talent at position `j` (0-indexed). Equal values are the same subject. - For a start `i`, the candidate blocks are `talents[i..j]` for every `j` with `i <= j < len(talents)`; a block always extends to the right of its start. - `answer[i]` is the smallest length `j - i + 1` for which `talents[i..j]` contains at least `k` distinct values. - If the block from `i` to the last position contains fewer than `k` distinct values, `answer[i]` is `-1`. - Return a list with the same length as `talents` whose element `i` is `answer[i]`. ### Constraints - `1 <= len(talents) <= 10^5` - `1 <= talents[j] <= 10^9` - `1 <= k <= 10^5`; `k` may exceed the number of distinct subjects in the whole list, in which case every element of the answer is `-1`. ### Examples **Example 1** ```text Input: talents = [1, 2, 3, 4, 3, 5], k = 3 Output: [3, 3, 4, 3, -1, -1] ``` Start 0 is covered by `[1, 2, 3]`, start 1 by `[2, 3, 4]` and start 3 by `[4, 3, 5]`, each of length 3. From start 2, `[3, 4, 3]` repeats subject 3 and holds only two distinct subjects, so the shortest block is `[3, 4, 3, 5]` of length 4. From start 4 the rest of the line is `[3, 5]` and from start 5 it is `[5]`; neither reaches three distinct subjects. **Example 2** ```text Input: talents = [2, 2, 1], k = 3 Output: [-1, -1, -1] ``` The whole list holds only two distinct subjects. **Example 3** ```text Input: talents = [4, 4, 4, 2, 4, 3], k = 3 Output: [6, 5, 4, 3, -1, -1] ``` The third distinct subject first appears at position 5, so the shortest blocks from starts 0, 1, 2 and 3 all end there, with lengths 6, 5, 4 and 3. From start 4 only subjects 4 and 3 remain, and from start 5 only subject 3.

Overview: For a line of talents, each tagged with one subject, and a required count k of distinct subjects, return for every starting position the length of the shortest contiguous block from there covering at least k distinct subjects, or -1 if none exists. It tests efficient counting of distinct values across overlapping ranges and exact handling of impossible starts.

Read the full Walmart Labs Software Engineer interview experience this question came from

A teacher is taking a line of contestants, called talents, to a series of competitions. Each talent is strong in exactly one subject, given as an integer, and the talents keep a fixed left-to-right order. A competition needs a team that covers at least `k` different subjects, and a team must be a contiguous block of the line. Given the list `talents` and the integer `k`, return a list `answer` with the same length as `talents`, where: - `talents[j]` is the subject of the talent at position `j` (0-indexed). Equal values are the same subject. - For a start `i`, the candidate blocks are `talents[i..j]` for every `j` with `i <= j < len(talents)`; a block always starts at `i` and extends to the right. - `answer[i]` is the smallest length `j - i + 1` for which `talents[i..j]` contains at least `k` distinct values. - If the block from `i` to the last position contains fewer than `k` distinct values, `answer[i]` is `-1`. If `k` exceeds the number of distinct subjects in the whole list, every element of the answer is `-1`. Every input value and every returned element fits in a signed 32-bit integer (none exceeds 2^31 - 1). **Example 1** Input: `talents = [1, 2, 3, 4, 3, 5], k = 3` Output: `[3, 3, 4, 3, -1, -1]` Starts 0, 1 and 3 are covered by `[1, 2, 3]`, `[2, 3, 4]` and `[4, 3, 5]`, each of length 3. From start 2, `[3, 4, 3]` repeats subject 3 and holds only two distinct subjects, so the shortest block is `[3, 4, 3, 5]` of length 4. From start 4 the rest of the line is `[3, 5]` and from start 5 it is `[5]`; neither reaches three distinct subjects. **Example 2** Input: `talents = [4, 4, 4, 2, 4, 3], k = 3` Output: `[6, 5, 4, 3, -1, -1]` The third distinct subject first appears at position 5, so the shortest blocks from starts 0, 1, 2 and 3 all end there, with lengths 6, 5, 4 and 3. From start 4 only subjects 4 and 3 remain, and from start 5 only subject 3. **Constraints** - `1 <= len(talents) <= 10^5` - `1 <= talents[j] <= 10^9` - `1 <= k <= 10^5`; `k` may exceed the number of distinct subjects in the whole list, in which case every element of the answer is `-1`.

Constraints

  • 1 <= len(talents) <= 10^5
  • 1 <= talents[j] <= 10^9
  • 1 <= k <= 10^5; k may exceed the number of distinct subjects in the whole list, in which case every element of the answer is -1.

Examples

Input: ([1, 2, 3, 4, 3, 5], 3)

Expected Output: [3, 3, 4, 3, -1, -1]

Explanation: Source Example 1: start 2 repeats subject 3 inside [3, 4, 3] and needs length 4; starts 4 and 5 are -1.

Input: ([2, 2, 1], 3)

Expected Output: [-1, -1, -1]

Explanation: Source Example 2: only two distinct subjects in the whole list, so k exceeds the total distinct count and every start is -1.

Hints

  1. Equal values are the same subject, so a block's coverage is its number of distinct values, not its length: a repeated subject adds length without adding coverage.
  2. Once the rest of the line from some start holds fewer than k distinct subjects, think about what that tells you about every later start.
  3. In Example 2 the shortest blocks for several starts all end at the same position. Think about how the best end for one start relates to the best end for the next start.

Loading coding console...

Show the approach

Approach

Sliding window with a frequency map. For a start i let end(i) be the smallest j such that talents[i..j] has at least k distinct values. Because talents[i+1..j] is contained in talents[i..j], it never has more distinct values, so end(i+1) >= end(i): the best end never moves left as the start moves right. Keep a window talents[left..right-1], a count per subject, and the number of subjects whose count is positive. For each left, advance right while the window has fewer than k distinct subjects and right < n. Invariant: right only advances while the window lacks k subjects, so the window without its last element always lacks k subjects; removing the leftmost element cannot add subjects, so the invariant survives each step of left. Hence, if the window reaches k distinct subjects, its last element is exactly end(left) and answer[left] = right - left. If right reaches n first, the whole suffix from left has fewer than k distinct subjects and answer[left] = -1 (and so does every later start). Before moving to the next start, decrement the count of talents[left] and drop the subject from the distinct total only when its count reaches zero, so a subject that still appears later in the window stays counted. Each index enters and leaves the window once. Edge cases: k = 1 answers 1 everywhere; k larger than the number of distinct subjects in the list answers -1 everywhere; a singleton list answers [1] or [-1].

Time complexity:
O(n)
Space complexity:
O(n)