1002EasyArrayHash Table

The Shortest Stretch Holding the Commonest Reading

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A log holds the readings readings. Its busiest count is the number of times its most repeated reading appears.

Return the length of the shortest stretch of neighbouring entries whose own busiest count matches the whole log's.

Examples

Example 1

Input: readings = [4, 7, 7, 9, 4]
Output: 2

The busiest count is two, reached by both 4 and 7. The two 4s sit at the far ends and need the whole log, while the two 7s sit side by side, so the shorter stretch wins.

Example 2

Input: readings = [3, 3, 3, 1, 5]
Output: 3

Only 3 reaches the busiest count of three, and its appearances run from the start to the third entry.

Example 3

Input: readings = [8]
Output: 1

One entry, so the busiest count is one and a single entry already matches it.

Constraints

1 <= readings.length <= 50000
0 <= readings[i] <= 49999

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_shortest_sub_array(readings: list[int]) -> int:

Java

public int findShortestSubArray(int[] readings)

The intended approach

Time O(n) over the log's length.Space O(d) for the distinct readings.

A stretch can only reach the whole log's busiest count by holding every single appearance of some reading that appears that many times. Nothing else gets a tally that high, since a stretch cannot hold more of a reading than the log does. For one such reading, the shortest stretch holding all its appearances runs from the first to the last, so its length is the distance between those plus one. The answer is the smallest such length over the readings tied for the busiest count. One pass gathers everything needed: for each distinct reading, where it first appeared, where it last appeared, and how many times it turned up. Then one sweep of the distinct readings finds the busiest count, and another takes the smallest stretch among those tied for it.

Pythonentry point: find_shortest_sub_array

def find_shortest_sub_array(readings):
    first = {}
    last = {}
    tally = {}
    for at, value in enumerate(readings):
        if value not in first:
            first[value] = at
        last[value] = at
        tally[value] = tally.get(value, 0) + 1
    busiest = 0
    for value in tally:
        if tally[value] > busiest:
            busiest = tally[value]
    best = len(readings)
    for value in tally:
        if tally[value] == busiest:
            span = last[value] - first[value] + 1
            if span < best:
                best = span
    return best

The obvious version

Work out the whole log's busiest count, then try stretches by length, shortest first, tallying the readings inside each one and returning the length of the first stretch whose own busiest count matches. Costs every stretch times its length rather than a single pass with first and last appearances.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_shortest_sub_array(readings):
    n = len(readings)
    def busiest(part):
        tally = {}
        top = 0
        for value in part:
            tally[value] = tally.get(value, 0) + 1
            if tally[value] > top:
                top = tally[value]
        return top
    want = busiest(readings)
    for length in range(1, n + 1):
        for start in range(n - length + 1):
            if busiest(readings[start:start + length]) == want:
                return length
    return n

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in