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

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:

1. If every digit is 0, the answer is "0".
2. Otherwise put the smallest non-zero digit first. A zero can't go
   first.
3. 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.

1. 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.
2. 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].
3. The first i that has such a digit gives the answer:
   bound[:i] + d + ascending(rest).
4. 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.

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 ""

• 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.

• 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.

• 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.

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".