484 - Find Permutation

Difficulty: Medium | Pattern: Greedy + Stack | Company tags: Google, Bloomberg

Problem Statement

A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:

• s[i] == 'I' if perm[i] < perm[i + 1], and
• s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct any lexicographically smallest permutation perm and return it.

Example 1:

Input: s = "I"
Output: [1,2]

Example 2:

Input: s = "DI"
Output: [2,1,3]

Algorithm Flow

Approach: Stack-based Reverse — O(n), O(n)

Key insight: Fill numbers 1 to n+1. For each character: push current number. When we see 'I' (or end), pop all stack elements to result — this reverses the consecutive D-sequence.

def findPermutation(s: str) -> list[int]:
    result = []
    stack = []
    
    for i, c in enumerate(s):
        stack.append(i + 1)
        if c == 'I':
            while stack:
                result.append(stack.pop())
    
    stack.append(len(s) + 1)
    while stack:
        result.append(stack.pop())
    
    return result

Dry Run

s = "DI"

i	c	stack	result
0	D	[1]	[]
1	I	[1,2]	→ pop all: [2,1]
end	—	[3]	→ pop: [2,1,3]

Result: [2,1,3] ✓

s = "DDDI":

• Push 1,2,3,4 on consecutive D's, then on I pop all: result=[4,3,2,1], push 5, pop: [4,3,2,1,5] ✓

Why Lexicographically Smallest?

Ascending runs come naturally (1,2,3,...). Descending runs are local reversals of the smallest available numbers, which keeps the arrangement lexicographically minimal.

Complexity

• Time: O(n)
• Space: O(n)

Key Terms

Term	Definition
Greedy construction	Building the answer incrementally by always making the locally smallest valid choice.
Stack reversal	Using a stack to reverse a contiguous run of numbers (here, a "D" run).
Lexicographic order	Dictionary-style ordering used to compare sequences element by element.
Run-length grouping	Treating consecutive identical characters ('D's) as one unit to process together.

FAQ

Q: Why does pushing onto a stack and popping on 'I' produce the lexicographically smallest result? A: Each maximal run of 'D's must be a descending sequence of consecutive integers; pushing them in increasing order and popping (LIFO) automatically reverses that run into descending order using the smallest available numbers, which keeps the overall permutation minimal.

Q: What happens if s is all 'I's? A: Every push is immediately followed by a pop of size 1, so the result is simply [1, 2, ..., n] — the identity permutation, which is correct since it's already fully ascending.

Q: What happens if s is all 'D's? A: Nothing pops until the final flush, so the entire stack of 1..n gets reversed at the end, producing [n, n-1, ..., 1].

Q: Can this be solved without a stack? A: Yes — since each 'D' run just needs reversing, you can find run boundaries with two pointers and reverse in-place in a preallocated array of 1..n, avoiding explicit stack usage but with equivalent O(n) complexity.

Q: Is there always exactly one valid answer, or could there be ties? A: For each input s there are potentially many valid permutations, but the problem asks specifically for the lexicographically smallest one, which this greedy/stack method guarantees uniquely.

Quick Revision

• Reconstruct permutation of 1..n from an 'I'/'D' pattern string, minimizing lexicographic order.
• Push consecutive numbers onto a stack; whenever an 'I' is seen (or the string ends), pop everything.
• Popping a stack reverses order — this creates the descending sub-runs needed for 'D' groups.
• Ascending regions naturally stay in order since stacks of size 1 pop trivially.
• After the loop, push n and flush the stack one final time.
• Time and space are both O(n).
• All-'I' input gives the identity permutation; all-'D' input gives the fully reversed permutation.
• Same "reverse-the-descending-run" idea appears in problems reconstructing sequences from relative order constraints.

Related Problems

• Next Permutation — related lexicographic-ordering reasoning over permutations.
• 406 - Queue Reconstruction by Height — different mechanism, but similar "insert to satisfy relative constraints" flavor.
• 135 - Candy — greedy problem also driven by adjacent up/down (increase/decrease) constraints, similar to the 'I'/'D' pattern here.