0504EasyArrayHash Table

Scarce Colour Code

Tracked in this browser only

Trains the technique from

LeetCode 3471Find the Largest Almost Missing Integer

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 paint line stamps one colour code onto every crate that passes. The array codes lists those stamps in the order the crates went by, and the auditor inspects the line in blocks: a block is any run of k consecutive entries of codes, so there are codes.length - k + 1 blocks in total and blocks may overlap.

A colour code is called scarce when exactly one block contains it. A block contains a code if the code is stamped on at least one of that block's k crates; a block that carries the same code twice still counts as one block.

Return the largest scarce colour code. Every colour code is non-negative, so return -1 when no code is scarce.

Examples

Example 1

Input: codes = [5, 1, 1, 2], k = 2
Output: 5

The three blocks are the first two crates, the middle two crates and the last two crates. Code 5 turns up only in the first block and code 2 only in the last, while code 1 turns up in all three, so the largest scarce code is 5.

Example 2

Input: codes = [3, 9, 3], k = 2
Output: -1

The two blocks are the first two crates and the last two crates. Code 3 is carried by both blocks and so is code 9, so nothing is scarce.

Example 3

Input: codes = [12, 50, 4, 50], k = 4
Output: 50

The block width matches the number of crates, so there is a single block and it carries all three codes. Each of them is therefore scarce, and 50 is the largest.

Constraints

1 <= codes.length <= 50
0 <= codes[i] <= 50
1 <= k <= codes.length

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 largest_scarce_code(codes: list[int], k: int) -> int:

Java

public int largestScarceCode(int[] codes, int k)

The intended approach

Time O(n): one tally pass plus a constant amount of case work.Space O(n): the tally of code frequencies.

Tally how often each code appears, then split on `k`. With `k` equal to the whole length there is one block and it holds everything, so the largest code wins. With `k` equal to one, every position is its own block, so the codes that appear exactly once are the scarce ones. Otherwise only the first and last positions belong to a single block, so a code is scarce exactly when it sits at one of those two positions and its tally is one.

Pythonentry point: largest_scarce_code

def largest_scarce_code(codes, k):
    # A block is a run of k consecutive positions, so position i sits inside
    # min(i, n - k) - max(0, i - k + 1) + 1 blocks. When k == n there is a single
    # block, and when k == 1 each position has its own block; otherwise only the
    # two end positions sit in exactly one block, so a value is scarce only if it
    # occupies an end position and appears nowhere else.
    # O(n) time, O(n) space for the tally.
    n = len(codes)
    counts = {}
    for v in codes:
        counts[v] = counts.get(v, 0) + 1
    if k == n:
        return max(codes)
    if k == 1:
        singles = [v for v, c in counts.items() if c == 1]
        return max(singles) if singles else -1
    best = -1
    for v in (codes[0], codes[n - 1]):
        if counts[v] == 1 and v > best:
            best = v
    return best

The obvious version

Materialise every block, reduce it to the set of codes it carries, and add one to a per-code counter for each block. Keep the codes whose counter is one and report the largest. O(n * k).

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_largest_scarce_code(codes, k):
    n = len(codes)
    hits = {}
    for start in range(n - k + 1):
        for v in set(codes[start:start + k]):
            hits[v] = hits.get(v, 0) + 1
    scarce = [v for v, c in hits.items() if c == 1]
    return max(scarce) if scarce else -1

How this problem was checked

Reference solution executed against 14 test cases — 14 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