Smallest number from a set of digits, with a lower bound: Frontier Interview's solution

Question: Smallest number from a set of digits, with a lower bound

Companies: Airbnb

Difficulty: Hard

Problem statement

Part 1. You are given a non-empty list digits of single-digit integers (each 0-9). Use every element exactly once and arrange them to form the smallest possible non-negative integer. Return it as a string.

The result must not have a leading zero. The one exception is the value zero itself, returned as "0".
If every digit is 0, return "0".

def smallest_number(digits: list[int]) -> str: ...

Part 2. You are also given a non-negative integer bound as a decimal string, which may be longer than 64 bits. Return the smallest number that follows the Part 1 rules (all digits used once, no leading zero) and is strictly greater than bound. Return "" if there is none.

def smallest_greater_than(digits: list[int], bound: str) -> str: ...

Constraints: 1 <= len(digits) <= 10^5, 1 <= len(bound) <= 10^5. Aim for time linear in the input size.

Example 1

smallest_number([4, 0, 2, 0])  -> "2004"
smallest_number([0, 0, 0])     -> "0"

Example 2

smallest_greater_than([4, 0, 2, 0], "2040")  -> "2400"
smallest_greater_than([4, 0, 2, 0], "4200")  -> ""
smallest_greater_than([4, 0, 2, 0], "999")   -> "2004"

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

The question comes in two parts. Part 1 is a warm-up. Part 2 adds a lower
bound, and most of the interview time goes there.

Part 1, brute force. Try every permutation, drop the ones with a
leading zero, and keep the minimum. That is O(n! · n). It is only useful
as a test oracle.

Part 1, greedy. All valid answers have the same length n (unless
every digit is zero). Among numbers of equal length, the smaller one has
the smaller first digit where they differ. So:

If every digit is 0, the answer is "0".
Otherwise put the smallest non-zero digit first. A zero can't go
first.
Write the remaining digits in ascending order. This puts all the
zeros straight after the leading digit, where they do the most good.

Use a count array of size 10 instead of sorting. The digits are 0-9, so
this is O(n) and the output is built straight from the counts.

Part 2: smallest arrangement strictly greater than bound. Compare
lengths first. Every valid answer has exactly n digits.

bound shorter than n: the Part 1 answer already wins.
bound longer than n: no answer, return "".
Same length: this is "next permutation" over a multiset, constrained by
the bound rather than by our own current arrangement.

For equal length, the answer agrees with bound on some prefix
bound[:i], then puts a digit d > bound[i] at position i, then
writes the smallest possible tail (ascending). To get the smallest
answer, make i as large as possible. A later divergence means a
longer shared prefix, so a smaller number. Then pick the smallest d
that works.

Copy bound digit by digit while the count array still has that
digit. Stop at the first digit we don't have. Call the copied length
copied.
Walk i from min(copied, n - 1) down to 0. At each step, give
bound[i] back to the counts if we copied it. Then look for the
smallest available digit greater than bound[i].
The first i that has such a digit gives the answer:
bound[:i] + d + ascending(rest).
If no i works, return "".

Invariants. On entering step i, the counts hold exactly the digits
not used by bound[:i]. The leading-zero rule takes care of itself. At
i = 0 we choose d > bound[0] >= 1. For i > 0 the first digit is
bound[0], which is non-zero after we strip the bound's leading zeros.

Code

from typing import List


def _counts(digits: List[int]) -> List[int]:
    cnt = [0] * 10
    for d in digits:
        if not 0 <= d <= 9:
            raise ValueError(f"not a digit: {d}")
        cnt[d] += 1
    return cnt


def _ascending(cnt: List[int]) -> str:
    return "".join(str(d) * cnt[d] for d in range(10))


def smallest_number(digits: List[int]) -> str:
    """Part 1: smallest value using every digit once, no leading zeros."""
    if not digits:
        raise ValueError("digits must be non-empty")
    cnt = _counts(digits)
    if cnt[0] == len(digits):          # only zeros: the value is 0
        return "0"
    lead = next(d for d in range(1, 10) if cnt[d])
    cnt[lead] -= 1
    return str(lead) + _ascending(cnt)  # zeros sit right after the lead


def smallest_greater_than(digits: List[int], bound: str) -> str:
    """Part 2: smallest valid number from digits strictly greater than bound.

    Returns "" when no arrangement beats the bound.
    """
    if not digits:
        raise ValueError("digits must be non-empty")
    bound = bound.lstrip("0") or "0"
    n = len(digits)
    cnt = _counts(digits)
    if cnt[0] == n:                     # only value is 0, never > bound
        return ""
    if len(bound) < n:                  # any n-digit number already wins
        return smallest_number(digits)
    if len(bound) > n:
        return ""

    # Walk the longest prefix of bound we can copy from our digits.
    copied = 0
    while copied < n and cnt[int(bound[copied])] > 0:
        cnt[int(bound[copied])] -= 1
        copied += 1
    # cnt now holds what is left after copying bound[:copied].
    # Try to diverge as late as possible: at position i place the smallest
    # available digit > bound[i], then fill the rest in ascending order.
    for i in range(min(copied, n - 1), -1, -1):
        if i < copied:
            cnt[int(bound[i])] += 1     # un-copy bound[i] to free it
        for d in range(int(bound[i]) + 1, 10):
            if cnt[d]:
                cnt[d] -= 1
                return bound[:i] + str(d) + _ascending(cnt)
    return ""

Complexity

smallest_number: O(n) time to count and build the string, O(1) extra
space besides the output (10 counters).
smallest_greater_than: the prefix copy is O(n). The backward walk
visits at most n positions and tries at most 9 digits at each, so
O(10n) = O(n). Building the answer is O(n). Space is O(1) extra besides
the output.
Brute force: O(n! · n), only as a test oracle for n <= 8.

Test cases

smallest_number([3, 0, 1, 0]) -> "1003" (zeros go right after the lead)
smallest_number([5, 2, 9]) -> "259"
smallest_number([0]) -> "0"
smallest_number([0, 0]) -> "0" (all zeros)
smallest_number([7]) -> "7"
smallest_greater_than([1, 2, 3], "132") -> "213"
smallest_greater_than([1, 2, 3], "321") -> "" (already the largest)
smallest_greater_than([1, 0, 0], "99") -> "100" (shorter bound)
smallest_greater_than([1, 0, 0], "100") -> "" (equal is not greater)
smallest_greater_than([2, 0, 1], "150") -> "201" (diverge at position 0)
smallest_greater_than([1, 2], "1234") -> "" (longer bound)
smallest_greater_than([0, 0], "0") -> "" (only value is 0)
Randomized: compare both functions against the permutation brute force
for n <= 6.

Follow-ups

Largest number instead. Sort the digits in descending order. The
only edge case is all zeros, which gives "0". For "largest less than
bound", mirror Part 2: diverge as late as possible with the largest
available digit smaller than bound[i], then a descending tail. Now
d = 0 at i = 0 is forbidden.
The answer must be divisible by 3 (or 9). Divisibility by 3 or 9
depends only on the digit sum, so it doesn't depend on the arrangement.
Check sum(digits) % 3 once. If you may drop digits to reach "largest
divisible by 3", remove the fewest and smallest digits with the right
remainder, as in LeetCode 1363.
Divisible by 2, 5 or 4. Now the last one or two digits matter. Try
each feasible ending (a small, fixed set). Build the smallest valid
prefix from what is left, and take the minimum. Watch for the case
where the ending uses the only non-zero digit.
Stream of queries with different bounds. Precompute the count
array once. Each query is still O(n), which is the size of its output.
If you only need to know whether an answer exists, compare against the
largest arrangement in O(n), or O(1) with that string cached.
Arbitrary non-negative integers, not single digits (LeetCode 179
style, smallest concatenation). Sort with the comparator a + b < b + a
on strings. Leading zeros now come from whole numbers like "0", so
move the smallest number that doesn't start with zero to the front, or
return "0" if every number is zero.

Interviewer expectations

Mid-level (L4)

Solves Part 1 quickly and catches the leading-zero and all-zeros cases
without hints.
Gets Part 2 with some guidance, usually through "longest matching
prefix, then bump one digit".
Writes a few edge-case asserts.

Senior (L5)

Uses counting instead of sorting and says why: the alphabet is fixed
at 10.
Does the length comparison first in Part 2 and explains why diverging
as late as possible gives the minimum.
Gets the code right on the first pass and checks it against a brute
force.

Staff (L6+)

States the invariant on the counts and shows the leading-zero rule
holds by construction rather than by special cases.
Handles the follow-ups (largest-below, divisibility, the comparator
version) by changing the same greedy, not by starting over.
Talks about input validation and API shape: a string versus an int
result, and "" versus None for "no answer".