0045MediumArrayStringGreedySorting

Greatest Shipment Tag

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 packing station prints the part number of every item in a shipment on its own slip, then glues the slips into one row that reads as a single numeral: the shipment tag. The station picks the order of the slips, and each slip is used exactly once with its digits kept as printed.

Given the part numbers parts, return the greatest tag the station can glue, as a string. A tag is never printed with a leading zero, so when every part number is 0 the tag reads "0". The answer comes back as a string because a tag can run far past what a machine integer holds.

Examples

Example 1

Input: parts = [7, 70]
Output: "770"

Gluing 7 in front gives 770, while 70 in front gives 707, so 7 leads.

Example 2

Input: parts = [2, 25, 251]
Output: "252512"

The order 25, 251, 2 reads as 252512, which beats every other arrangement, including 251 first at 251252.

Example 3

Input: parts = [2, 10, 0]
Output: "2100"

2 leads, then 10, then 0; putting 0 anywhere earlier only shrinks the tag.

Constraints

1 <= parts.length <= 100
0 <= parts[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 greatest_tag(parts: list[int]) -> str:

Java

public String greatestTag(int[] parts)

The intended approach

Time O(n log n * L) where L bounds a part number's digit countSpace O(n * L) for the slips and the glued tag

Two slips belong in the order that makes their own two-slip reading larger, so slip `a` goes before slip `b` when the text `a + b` is greater than `b + a` as a string of the same length. That test is consistent enough to sort the whole row by, so sort the slips with it, glue them, and collapse an all-zero row down to a single `0`.

Pythonentry point: greatest_tag

def greatest_tag(parts):
    from functools import cmp_to_key

    slips = [str(p) for p in parts]

    def order(a, b):
        if a + b == b + a:
            return 0
        return -1 if a + b > b + a else 1

    slips.sort(key=cmp_to_key(order))
    tag = "".join(slips)
    return "0" if tag[0] == "0" else tag

The obvious version

No ordering rule at all: glue every permutation of the slips, keep whichever reading is numerically largest, and print that value back out, which also strips any leading zeros. O(n! * n * L).

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_greatest_tag(parts):
    from itertools import permutations

    slips = [str(p) for p in parts]
    best = None
    for arrangement in permutations(slips):
        candidate = "".join(arrangement)
        if best is None or int(candidate) > int(best):
            best = candidate
    return str(int(best))

How this problem was checked

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