Find Permutation solution and explanation
Google
3 more videos on this problem
The problem
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'ifperm[i] < perm[i + 1], ands[i] == 'D'ifperm[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:
1 <= s.length <= 105s[i]is either'I'or'D'.
Approach overview
Problem Overview: You are given a string consisting of characters 'I' (increasing) and 'D' (decreasing). The goal is to construct the lexicographically smallest permutation of numbers 1..n that satisfies this pattern. If s[i] = 'I', then perm[i] < perm[i+1]; if 'D', then perm[i] > perm[i+1].
Approach 1: Brute Force Permutation Search (O(n! * n) time, O(n) space)
Generate all permutations of numbers 1..n and check which ones satisfy the pattern. For each permutation, iterate through the pattern and verify whether adjacent elements follow the required increasing or decreasing rule. The first valid permutation in lexicographical order is the answer. This approach works conceptually but becomes infeasible quickly because the number of permutations grows factorially.
Approach 2: Greedy with Segment Reversal (O(n) time, O(1) extra space)
Start by building a sequence [1,2,3,...,n]. Traverse the pattern and look for consecutive 'D' segments. Whenever a block of 'D' appears from index i to j, reverse the corresponding range in the permutation. Reversing transforms the increasing sequence into the required decreasing structure while keeping the permutation lexicographically minimal. This greedy idea works because the smallest numbers are placed as early as possible while only adjusting ranges that violate the pattern.
Approach 3: Stack-Based Greedy (O(n) time, O(n) space)
This is the most common interview solution. Iterate through indices from 1 to n and push each number onto a stack. Whenever you encounter an 'I' or reach the end of the pattern, pop all elements from the stack and append them to the result. The stack naturally reverses segments corresponding to 'D' runs, producing decreasing subsequences while preserving the smallest available numbers. The algorithm performs one pass through the pattern and uses stack push/pop operations, making it both simple and efficient.
The stack and reversal strategies rely on the same greedy insight: delay output while reading 'D', then release numbers in reverse order to enforce decreasing constraints. This pattern manipulation frequently appears in stack and greedy problems involving sequences.
Recommended for interviews: The stack-based greedy solution is what most interviewers expect. It runs in O(n) time with O(n) space and clearly demonstrates understanding of pattern processing. Mentioning the brute force approach shows baseline reasoning, but implementing the greedy stack solution proves you can optimize using insights about array ordering and pattern constraints.
Solution
class Solution:
def findPermutation(self, s: str) -> List[int]:
n = len(s)
ans = list(range(1, n + 2))
i = 0
while i < n:
j = i
while j < n and s[j] == 'D':
j += 1
ans[i : j + 1] = ans[i : j + 1][::-1]
i = max(i + 1, j)
return ansclass Solution {
public int[] findPermutation(String s) {
int n = s.length();
int[] ans = new int[n + 1];
for (int i = 0; i < n + 1; ++i) {
ans[i] = i + 1;
}
int i = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == 'D') {
++j;
}
reverse(ans, i, j);
i = Math.max(i + 1, j);
}
return ans;
}
private void reverse(int[] arr, int i, int j) {
for (; i < j; ++i, --j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}class Solution {
public:
vector<int> findPermutation(string s) {
int n = s.size();
vector<int> ans(n + 1);
iota(ans.begin(), ans.end(), 1);
int i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] == 'D') {
++j;
}
reverse(ans.begin() + i, ans.begin() + j + 1);
i = max(i + 1, j);
}
return ans;
}
};func findPermutation(s string) []int {
n := len(s)
ans := make([]int, n+1)
for i := range ans {
ans[i] = i + 1
}
i := 0
for i < n {
j := i
for ; j < n && s[j] == 'D'; j++ {
}
reverse(ans, i, j)
i = max(i+1, j)
}
return ans
}
func reverse(arr []int, i, j int) {
for ; i < j; i, j = i+1, j-1 {
arr[i], arr[j] = arr[j], arr[i]
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n! * n) | O(n) | Conceptual understanding or very small input sizes |
| Greedy with Segment Reversal | O(n) | O(1) | Efficient in-place solution when modifying an array directly |
| Stack-Based Greedy | O(n) | O(n) | Most intuitive approach for interviews and editorial explanations |
Frequently asked questions
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.