0518MediumArrayHash TableMath

Closest Mirror Tag

Tracked in this browser only

Trains the technique from

LeetCode 3761Minimum Absolute Distance Between Mirror Pairs

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 rail holds tags in a row, and codes[i] is the positive whole number printed on the tag at position i.

The mirror of a number is what you read when its decimal digits are read back to front, with any leading zeros the reversal produces thrown away. The mirror of 47 is 74, the mirror of 1200 is 21, and the mirror of 66 is 66.

Two positions i and j with i < j form a mirror pair when at least one of the two printed numbers is the mirror of the other, and the gap of that pair is j - i.

Return the smallest gap over all mirror pairs on the rail. Every gap is at least 1, so return -1 when the rail holds no mirror pair at all.

Examples

Example 1

Input: codes = [13, 5, 7, 31]
Output: 3

Position 0 prints 13 and position 3 prints 31, which is the mirror of 13, so that pair has gap 3 and no other pair on the rail forms a mirror pair.

Example 2

Input: codes = [120, 8, 21, 3, 21, 120]
Output: 1

Position 4 prints 21 and position 5 prints 120, whose mirror is 21, so that pair has gap 1.

Example 3

Input: codes = [10, 20, 30]
Output: -1

The mirrors of 10, 20 and 30 are 1, 2 and 3, none of which is printed on the rail, so no pair qualifies.

Constraints

1 <= codes.length <= 10^5
1 <= codes[i] <= 10^9

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

Java

public int closestMirrorTag(int[] codes)

The intended approach

Time O(n * d) for tags of at most d digits: one pass, one digit reversal each.Space O(n): the two dictionaries.

For a fixed right-hand position, the tightest gap comes from the latest position on its left that satisfies the rule, so one pass suffices if both directions of the rule can be looked up. Keep two dictionaries while walking the rail: the latest position printing each value, and the latest position whose value mirrors to each key. At position j, the first dictionary answers whether some earlier tag equals the mirror of the current tag, the second answers whether some earlier tag mirrors to the current tag, and the better of the two gaps updates the running best.

Pythonentry point: closest_mirror_tag

def closest_mirror_tag(codes):
    # Walk the shelf once, remembering for every value the latest position that
    # carried it and for every mirror the latest position whose value mirrors to it.
    # At position j both directions of the rule become a single lookup, and the
    # latest matching position gives the tightest gap ending at j.
    # O(n * d) time for tags of at most d digits, O(n) space.
    def mirror(value):
        flipped = 0
        while value > 0:
            flipped = flipped * 10 + value % 10
            value //= 10
        return flipped

    last_value = {}
    last_mirror = {}
    best = -1
    for j in range(len(codes)):
        value = codes[j]
        flipped = mirror(value)
        for i in (last_mirror.get(value), last_value.get(flipped)):
            if i is not None and (best == -1 or j - i < best):
                best = j - i
        last_value[value] = j
        last_mirror[flipped] = j
    return best

The obvious version

Test every pair of positions, reversing the decimal spelling of both printed numbers to check the rule in each direction, and keep the smallest gap found. O(n^2 * d).

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_closest_mirror_tag(codes):
    def flip(value):
        return int(str(value)[::-1])

    best = -1
    n = len(codes)
    for i in range(n):
        for j in range(i + 1, n):
            if flip(codes[i]) == codes[j] or flip(codes[j]) == codes[i]:
                if best == -1 or j - i < best:
                    best = j - i
    return best

How this problem was checked

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