Problem 265179 · medium · Phase 02 Linear Data Structures

Shortest Span of the Busiest Value

hash maps · first and last index · counting

Given nums, let the degree be the highest number of times any value appears. Return the length of the shortest contiguous subarray that contains all occurrences of some value with that degree (so the subarray itself has the same degree). Return 0 for an empty list.

Examples

Input:  nums = [1, 2, 2, 3, 1]
Output: 2
Explanation: the degree is 2 (values 1 and 2). [2, 2] has length 2; [1, 2, 2, 3, 1] would be 5.

Input:  nums = [1, 2, 2, 3, 1, 4, 2]
Output: 6

Constraints

  • 0 <= len(nums) <= 10**5
  • Target complexity: O(n) time.

Goals

  • Store several facts per key (first index, last index, count)
  • Combine them to answer a min-length question
Starting Python…