← Amazon questions

Minimum number from pattern

Filed under Amazon · Also reported at Google

Free read 2 of 3

Understand constraints on pattern length and confirm that output is a string of digits representing the smallest valid number.

The question

Given a pattern containing only 'I' (increasing) and 'D' (decreasing), construct the smallest possible number using digits 1 through 9 without repeating any digit. The length of the pattern is between 1 and 8.

Constraints

  • The pattern consists only of characters 'I' and 'D'.
  • Length of pattern is between 1 and 8.
  • Digits 1 to 9 must be used without repetition.

Examples

Input
pattern = "IIDDD"
Output
126543
Why
At index 0: 1<2 (I), index 1: 2<6 (I), index 2: 6>5 (D), index 3: 5>4 (D), index 4: 4>3 (D). The number uses digits 1-6 uniquely.

Approach

  1. Understand constraints on pattern length and confirm that output is a string of digits representing the smallest valid number.

Solution

O(N) time, O(N) space

Python
def minNumber(pattern: str) -> str:
    res, stack = [], []
    for i in range(len(pattern) + 1):
        stack.append(str(i + 1))
        if i == len(pattern) or pattern[i] == 'I':
            while stack:
                res.append(stack.pop())
    return "".join(res)

Tips

  • What they are testing: Test edge cases like all 'I's (e.g. "III"), all 'D's (e.g. "DDD"), and alternating patterns.
  • Common mistake: Trying to build the number greedily from left to right without looking ahead, which fails to produce the smallest lexicographical representation.

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.