Is Find Permutation easy or hard?

Find Permutation is considered a medium difficulty problem. The trick lies in recognizing that consecutive 'D' characters require reversing a segment of numbers, which can be handled cleanly with a stack or range reversal technique.

Find Permutation Python/Java solution

The typical implementation uses a stack. Iterate from 1 to n, push numbers, and flush the stack when an 'I' appears. The same logic translates directly to Python, Java, C++, and Go with identical O(n) time complexity.

How to solve Find Permutation in O(n)?

Traverse the pattern while pushing numbers sequentially onto a stack. When encountering an 'I' or reaching the end of the string, pop all elements from the stack into the result array. This ensures decreasing segments are reversed automatically and the permutation satisfies the pattern in linear time.

What is the best approach for Find Permutation?

The optimal approach uses a greedy stack strategy. Iterate through numbers 1..n, push them onto a stack, and whenever an 'I' appears (or the pattern ends), pop everything from the stack into the result. This reverses segments corresponding to 'D' runs and produces the lexicographically smallest valid permutation in O(n) time.

Is Find Permutation asked at Google/Amazon/Meta?

Find Permutation represents a classic greedy and stack pattern problem. Variants involving pattern-based permutations or monotonic stacks appear in interviews at companies like Amazon, Google, and Meta, especially when testing sequence construction and greedy reasoning.

What data structure is used in Find Permutation?

A stack is commonly used in the optimal solution. The stack temporarily stores numbers during consecutive 'D' patterns and releases them in reverse order to enforce the decreasing relationship required by the pattern.

What is the time complexity of Find Permutation?

The optimal greedy solution runs in O(n) time because each number from 1 to n is pushed and popped from the stack exactly once. Space complexity is O(n) due to the stack and the resulting permutation array.

Description Solution Video 12:52

484. Find Permutation

Medium67.0% acceptance1 companyPremium elsewhere, free here

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 the lexicographically smallest permutation perm and return it.

Example 1:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

Example 2:

Input: s = "DI"
Output: [2,1,3]
Explanation: Both [2,1,3] and [3,1,2] can be represented as "DI", but since we want to find the smallest lexicographical permutation, you should return [2,1,3]

Constraints: