Minimum number from pattern
Filed under Amazon · Also reported at Google
Free read 2 of 3Understand 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
Understand constraints on pattern length and confirm that output is a string of digits representing the smallest valid number.
Generate all permutations of digits 1-N+1 and check each against the pattern. Too slow for larger lengths.
Use a stack. Iterate from 0 to n, pushing digits 1, 2, ... into a stack. Whenever 'I' is encountered or we reach the end, pop all elements from the stack and append to the result.
Single character patterns like "I" or "D", and maximum length inputs.
Solution
O(N) time, O(N) space
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.