Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

484. Find Permutation

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  vector<int> findPermutation(string s) {
    vector<int> ans;
    stack<int> stack;

    for (int i = 0; i < s.length(); ++i) {
      stack.push(i + 1);
      if (s[i] == 'I')
        while (!stack.empty())
          ans.push_back(stack.top()), stack.pop();
    }
    stack.push(s.length() + 1);

    while (!stack.empty())
      ans.push_back(stack.top()), stack.pop();

    return ans;
  }
};




			


class Solution {
  public int[] findPermutation(String s) {
    int[] ans = new int[s.length() + 1];
    int ansIndex = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < s.length(); ++i) {
      stack.push(i + 1);
      if (s.charAt(i) == 'I')
        while (!stack.isEmpty())
          ans[ansIndex++] = stack.pop();
    }
    stack.push(s.length() + 1);

    while (!stack.isEmpty())
      ans[ansIndex++] = stack.pop();

    return ans;
  }
}




			


class Solution:
  def findPermutation(self, s: str) -> List[int]:
    ans = []
    stack = []

    for i, c in enumerate(s):
      stack.append(i + 1)
      if c == 'I':
        while stack:  # Consume all decreasings
          ans.append(stack.pop())
    stack.append(len(s) + 1)

    while stack:
      ans.append(stack.pop())

    return ans