Greatest three-digit subsequence

Why exactly three digits. Picking fewer than three digits never helps. Take any shorter pick. Since N ≥ 3, there is an unused digit somewhere. If an unused digit sits after the pick's last digit, appending it gives 10·x + d ≥ x. Otherwise every unused digit sits before the pick, and prepending one adds d·10^k ≥ 0. Either way the three-digit pick is at least as large. So the question becomes: choose a subsequence of length 3 whose value is the largest. Leading zeros are allowed and simply make the number smaller (0,0,7 is 7).

Brute force. Try every triple i < j < k and keep the largest 100·a[i] + 10·a[j] + a[k]. That is O(N³), which is fine for N ≤ 50 and a good first answer to state out loud.

Greedy. Comparing two equal-length numbers is lexicographic, so make the first digit as large as possible, then the second, then the third. For output position p (0, 1, 2), the digit must come from the window [start, N - (3 - p)]. The window stops early so enough digits remain for the rest. Take the largest digit in that window and its leftmost occurrence. Taking the leftmost one leaves the most room for later picks. Then set start to the index after it.

Invariant. After picking p digits, the prefix is the largest possible prefix of length p among all valid triples. Among the picks that reach that prefix, the one we chose ends earliest, so it keeps every option open for the rest.

Generalized to k digits (monotonic stack). Scan left to right with a stack. Pop while the top is smaller than the current digit and enough digits remain to still fill k slots. Then push if the stack has fewer than k items. This is O(N) for any k and is the version to give when the interviewer generalizes.

from itertools import combinations


def greatest_triple_brute(digits: list[int]) -> int:
    """O(N^3) baseline: try every ordered triple."""
    return max(100 * a + 10 * b + c for a, b, c in combinations(digits, 3))


def greatest_triple(digits: list[int]) -> int:
    """Greedy window scan; O(3 * N)."""
    n = len(digits)
    if n < 3:
        raise ValueError("need at least three digits")
    result, start = 0, 0
    for remaining in (3, 2, 1):
        last = n - remaining  # last index we may use for this slot
        best_idx = start
        for i in range(start, last + 1):
            if digits[i] > digits[best_idx]:  # strict: keep leftmost max
                best_idx = i
                if digits[i] == 9:
                    break
        result = result * 10 + digits[best_idx]
        start = best_idx + 1
    return result


def greatest_k_digits(digits: list[int], k: int) -> list[int]:
    """Largest length-k subsequence, in order, via a monotonic stack. O(N)."""
    if not 0 <= k <= len(digits):
        raise ValueError("k out of range")
    stack: list[int] = []
    n = len(digits)
    for i, d in enumerate(digits):
        # Pop a smaller top only if we can still fill k slots afterwards.
        while stack and stack[-1] < d and len(stack) - 1 + (n - i) >= k:
            stack.pop()
        if len(stack) < k:
            stack.append(d)
    return stack


def as_int(ds: list[int]) -> int:
    value = 0
    for d in ds:
        value = value * 10 + d
    return value


if __name__ == "__main__":
    import random

    assert greatest_triple([3, 1, 4, 1, 5, 9, 2, 6]) == 926
    assert greatest_triple([1, 2, 3]) == 123
    assert greatest_triple([9, 0, 0]) == 900
    assert greatest_triple([0, 0, 7]) == 7
    assert greatest_triple([0, 0, 0, 0]) == 0
    assert greatest_triple([5, 5, 5, 5]) == 555
    assert greatest_triple([1, 9, 1, 9, 1]) == 991
    assert greatest_triple([8, 7, 9]) == 879
    for _ in range(2000):
        ds = [random.randint(0, 9) for _ in range(random.randint(3, 12))]
        expect = greatest_triple_brute(ds)
        assert greatest_triple(ds) == expect, ds
        assert as_int(greatest_k_digits(ds, 3)) == expect, ds
    assert greatest_k_digits([2, 7, 1, 8, 2, 8], 4) == [7, 8, 2, 8]
    print("ok")

• Brute force: O(N³) time, O(1) space.
• Greedy window scan: each of the three slots scans at most N digits, so O(3N) = O(N) time, O(1) space.
• Monotonic stack for general k: O(N) time (each digit is pushed and popped at most once), O(k) space.

• [3, 1, 4, 1, 5, 9, 2, 6] → 926 (9 first, then the largest of [2, 6] in order).
• [1, 2, 3] → 123 (N = 3, the only choice).
• [8, 7, 9] → 879 (the 9 is last, so it cannot lead).
• [9, 0, 0] → 900.
• [0, 0, 7] → 7 (leading zeros are allowed and drop out).
• [0, 0, 0, 0] → 0.
• [5, 5, 5, 5] → 555 (ties: take the leftmost).
• [1, 9, 1, 9, 1] → 991 (leftmost 9 first leaves the second 9 available).
• Random arrays of length 3–12: greedy and stack both match the brute force.

1. Pick exactly k digits instead of 3. Use the monotonic stack (greatest_k_digits). It runs in O(N) whatever k is. The window scan would be O(k·N), and a sparse table for range-max with leftmost tiebreak brings it to O(N log N + k).
2. Return the indices, or the result as a string. Keep indices on the stack instead of values. For large k, return a string because the number can overflow fixed-width integers in other languages.
3. The result must be divisible by 3 (or by another m). Greedy no longer works on its own. Use a DP over (position, digits chosen, value mod m), filled from the right, that records whether a valid completion exists. Then build the answer greedily, taking the largest digit whose completion is still feasible. That is O(N·k·m·10) time.
4. Digits arrive as a stream with unknown length. You cannot know the "last usable index" in advance. Keep the best triple so far with a small DP: best1, best2, best3 as the largest values of length 1, 2, 3 using the prefix. Update on each digit d with best3 = max(best3, 10·best2 + d), then best2, then best1, in that order. This uses O(1) memory per digit and is a nice alternative proof of the static answer.
5. Merge from two arrays (LeetCode 321 style). For each split i + j = k, take the best i from the first array and the best j from the second with the stack. Merge them by comparing remaining suffixes lexicographically, and keep the best result.

Mid-level (L4)

• States the brute force, then reaches the greedy with the "leave enough digits" window.
• Handles ties by taking the leftmost max and explains why.
• Tests edge cases: N = 3, all equal digits, leading zeros, max digit at the end.

Senior (L5)

• Argues why three digits always beat fewer, and why lexicographic order equals numeric order at fixed length.
• Generalizes to k with the monotonic stack and gets the pop condition right.
• Checks the greedy against the brute force on random inputs.

Staff (L6+)

• Recognizes when greedy breaks (a divisibility constraint) and moves to feasibility DP plus greedy reconstruction.
• Offers the streaming DP (best1/best2/best3) and links it to the static proof.
• Discusses the output format for large k (string, not int) and the API contract (invalid input, N < k).