Find Permutation

Find Permutation

What is this problem about?

The Find Permutation interview question involves reconstructing a permutation of $1 \dots n$ based on a signature string of 'I' (Increase) and 'D' (Decrease). For example, if the string is "ID", you need a permutation of [1, 2, 3] such that the first move is an increase and the second is a decrease. You want to return the lexicographically smallest such permutation.

Why is this asked in interviews?

Google asks the Find Permutation coding problem to test a candidate's ability to use Stack or Greedy logic to handle relative order constraints. It evaluations if you can identify that a sequence of 'D's represents a reversed segment of numbers. It’s a great test of pattern recognition within Array interview patterns.

Algorithmic pattern used

This problem is best solved using a Stack or Reversing Subarrays.

1. Initialize: Start with an array [1, 2, ... n].
2. Greedy Strategy: Iterate through the signature string.
3. Handle Decreases: Whenever you see a sequence of 'D's (e.g., from index $i$ to $j$), it means the values at those positions should be in descending order. Since the smallest values are at the start, you can simply reverse the subarray corresponding to those 'D's.
4. Stack Approach: Push numbers $1, 2, \dots$ onto a stack. When you hit an 'I' (or the end), pop all numbers from the stack and add them to the result.

Example explanation

Signature: "ID" (Permutation of 1, 2, 3)

1. index 0: 'I'. Add 1 to result. Result: [1].
2. index 1: 'D'. End of string logic triggered.
3. Use numbers 2 and 3. Because of 'D', add them in reverse order: 3, 2. Result: [1, 3, 2]. Check: 1 to 3 (Increase), 3 to 2 (Decrease). Smallest possible.

Common mistakes candidates make

• Not Lexicographical: Finding any valid permutation instead of the smallest one.
• Off-by-one: Mistakes in identifying the range of numbers to reverse for a block of 'D's.
• Complex Search: Trying to use backtracking ($O(N!)$) for a problem that can be solved in $O(N)$.

Interview preparation tip

Sequences of "Decrease" requirements often imply a Reversal. If you need to stay as small as possible while going down, you should pick the smallest available set of numbers and flip them.