Given an array arr[] of size N, where arr[i] denotes the number of elements on the left that are greater than the ith element in the original permutation. The task is to find the original permutation of [1, N] for which given inversion array arr[] holds valid.
Examples:
Input: arr[] = {0, 1, 1, 0, 3}
Output: 4 1 3 5 2
Explanation:
The original permutation is ans[] = {4, 1, 3, 5, 2}
ans[0] = 4.
ans[1] = 1. Since {4} exists on its left, which exceeds 1, arr[1] = 1 holds valid.
ans[2] = 3. Since {4} exists on its left, which exceeds 3, arr[2] = 1 holds valid.
ans[3] = 5. Since no elements on its left exceeds 5, arr[3] = 0 holds valid.
ans[4] = 2. Since {4, 3, 5} exists on its left, which exceeds 2, arr[4] = 3 holds valid.Input: arr[] = {0, 1, 2}
Output: 3 2 1
Naive Approach: The simplest approach is to generate all the permutations of N number and for each permutation, check if its elements satisfy the inversions given by the array arr[]. If such permutation is found, print it.
Time Complexity: O(N!)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use a Segment Tree. Follow the below steps to solve the problem:
- Build a segment tree of size N and initialize all leaf nodes with value 1.
- Traverse the given array from right to left. For example, if the current index is N – 1, i.e, none of the elements are visited. So, the arr[i] is the number of elements that should be greater than the element which has to be at this position. So, the answer for this element is the (N – arr[N – 1])th element in the segment tree corresponds to that element. After that, mark that element as 0 to avoid its counting again.
- Similarly, find (i + 1 – arr[i])th element in the segment tree, for each i from (N – 1) to 0.
- After finding the answer for arr[i], let it be temp, store it in some array ans[], and update the node having index temp with 0.
- Finally, print the answer array ans[] in reversed order as the original permutation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MAXX = 100; // Declaring segment tree int st[4 * MAXX]; // Function to initialize segment tree // with leaves filled with ones void build(int x, int lx, int rx) { // Base Case if (rx - lx == 1) { st[x] = 1; return; } // Split into two halves int m = (lx + rx) / 2; // Build the left subtree build(x * 2 + 1, lx, m); // Build the right subtree build(x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to make index x to 0 // and then update segment tree void update(int i, int x, int lx, int rx) { // Base Case if (rx - lx == 1) { st[x] = 0; return; } // Split into two halves int m = (lx + rx) / 2; // Update Query if (i < m) update(i, x * 2 + 1, lx, m); else update(i, x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to find the Kth element int getans(int x, int lx, int rx, int k, int n) { // Base Condition if (rx - lx == 1) { if (st[x] == k) return lx; return n; } // Split into two halves int m = (lx + rx) / 2; // Check if kth one is in left subtree // or right subtree of current node if (st[x * 2 + 1] >= k) return getans(x * 2 + 1, lx, m, k, n); else return getans(x * 2 + 2, m, rx, k - st[x * 2 + 1], n); } // Function to generate the original // permutation void getPermutation(int inv[], int n) { // Build segment tree build(0, 0, n); // Stores the original permutation vector<int> ans; for (int i = n - 1; i >= 0; i--) { // Find kth one int temp = getans(0, 0, n, st[0] - inv[i], n); // Answer for arr[i] ans.push_back(temp + 1); // Setting found value back to 0 update(max(0, temp), 0, 0, n); } // Print the permutation for (int i = n - 1; i >= 0; i--) cout << ans[i] << " "; return; } // Driver Code int main() { // Given array int inv[] = { 0, 1, 1, 0, 3 }; // Length of the given array int N = sizeof(inv) / sizeof(inv[0]); // Function Call getPermutation(inv, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static int MAXX = 100; // Declaring segment tree static int []st = new int[4 * MAXX]; // Function to initialize segment tree // with leaves filled with ones static void build(int x, int lx, int rx) { // Base Case if (rx - lx == 1) { st[x] = 1; return; } // Split into two halves int m = (lx + rx) / 2; // Build the left subtree build(x * 2 + 1, lx, m); // Build the right subtree build(x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to make index x to 0 // and then update segment tree static void update(int i, int x, int lx, int rx) { // Base Case if (rx - lx == 1) { st[x] = 0; return; } // Split into two halves int m = (lx + rx) / 2; // Update Query if (i < m) update(i, x * 2 + 1, lx, m); else update(i, x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to find the Kth element static int getans(int x, int lx, int rx, int k, int n) { // Base Condition if (rx - lx == 1) { if (st[x] == k) return lx; return n; } // Split into two halves int m = (lx + rx) / 2; // Check if kth one is in left subtree // or right subtree of current node if (st[x * 2 + 1] >= k) return getans(x * 2 + 1, lx, m, k, n); else return getans(x * 2 + 2, m, rx, k - st[x * 2 + 1], n); } // Function to generate the original // permutation static void getPermutation(int inv[], int n) { // Build segment tree build(0, 0, n); // Stores the original permutation Vector<Integer> ans = new Vector<Integer>(); for(int i = n - 1; i >= 0; i--) { // Find kth one int temp = getans(0, 0, n, st[0] - inv[i], n); // Answer for arr[i] ans.add(temp + 1); // Setting found value back to 0 update(Math.max(0, temp), 0, 0, n); } // Print the permutation for(int i = n - 1; i >= 0; i--) System.out.print(ans.get(i) + " "); return; } // Driver Code public static void main(String args[]) { // Given array int inv[] = { 0, 1, 1, 0, 3 }; // Length of the given array int N = inv.length; // Function Call getPermutation(inv, N); } } // This code is contributed by SURENDRA_GANGWAR |
Python3
# Python3 program for the above approach MAXX = 100 # Declaring segment tree st = [0] * (4 * MAXX) # Function to initialize segment tree # with leaves filled with ones def build(x, lx, rx): # Base Case if (rx - lx == 1): st[x] = 1 return # Split into two halves m = (lx + rx) // 2 # Build the left subtree build(x * 2 + 1, lx, m) # Build the right subtree build(x * 2 + 2, m, rx) # Combining both left and right # subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2] return # Function to make index x to 0 # and then update segment tree def update(i, x, lx, rx): # Base Case if (rx - lx == 1): st[x] = 0 return # Split into two halves m = (lx + rx) // 2 # Update Query if (i < m): update(i, x * 2 + 1, lx, m) else: update(i, x * 2 + 2, m, rx) # Combining both left and right # subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2] return # Function to find the Kth element def getans(x, lx, rx, k, n): # Base Condition if (rx - lx == 1): if (st[x] == k): return lx return n # Split into two halves m = (lx + rx) // 2 # Check if kth one is in left subtree # or right subtree of current node if (st[x * 2 + 1] >= k): return getans(x * 2 + 1, lx, m, k, n) else: return getans(x * 2 + 2, m, rx, k - st[x * 2 + 1], n) # Function to generate the original # permutation def getPermutation(inv, n): # Build segment tree build(0, 0, n) # Stores the original permutation ans = [] for i in range(n - 1, -1, -1): # Find kth one temp = getans(0, 0, n, st[0] - inv[i], n) # Answer for arr[i] ans.append(temp + 1) # Setting found value back to 0 update(max(0, temp), 0, 0, n) # Print the permutation for i in range(n - 1, -1, -1): print(ans[i], end = " ") return # Driver Code if __name__ == '__main__': # Given array inv = [ 0, 1, 1, 0, 3 ] # Length of the given array N = len(inv) # Function Call getPermutation(inv, N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static int MAXX = 100; // Declaring segment tree static int []st = new int[4 * MAXX]; // Function to initialize segment tree // with leaves filled with ones static void build(int x, int lx, int rx) { // Base Case if (rx - lx == 1) { st[x] = 1; return; } // Split into two halves int m = (lx + rx) / 2; // Build the left subtree build(x * 2 + 1, lx, m); // Build the right subtree build(x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to make index x to 0 // and then update segment tree static void update(int i, int x, int lx, int rx) { // Base Case if (rx - lx == 1) { st[x] = 0; return; } // Split into two halves int m = (lx + rx) / 2; // Update Query if (i < m) update(i, x * 2 + 1, lx, m); else update(i, x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to find the Kth element static int getans(int x, int lx, int rx, int k, int n) { // Base Condition if (rx - lx == 1) { if (st[x] == k) return lx; return n; } // Split into two halves int m = (lx + rx) / 2; // Check if kth one is in left subtree // or right subtree of current node if (st[x * 2 + 1] >= k) return getans(x * 2 + 1, lx, m, k, n); else return getans(x * 2 + 2, m, rx, k - st[x * 2 + 1], n); } // Function to generate the original // permutation static void getPermutation(int []inv, int n) { // Build segment tree build(0, 0, n); // Stores the original permutation List<int> ans = new List<int>(); for(int i = n - 1; i >= 0; i--) { // Find kth one int temp = getans(0, 0, n, st[0] - inv[i], n); // Answer for arr[i] ans.Add(temp + 1); // Setting found value back to 0 update(Math.Max(0, temp), 0, 0, n); } // Print the permutation for(int i = n - 1; i >= 0; i--) Console.Write(ans[i] + " "); return; } // Driver Code public static void Main(String []args) { // Given array int []inv = { 0, 1, 1, 0, 3 }; // Length of the given array int N = inv.Length; // Function Call getPermutation(inv, N); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach let MAXX = 100; // Declaring segment tree let st = new Array(4 * MAXX); // Function to initialize segment tree // with leaves filled with ones function build(x, lx, rx) { // Base Case if (rx - lx == 1) { st[x] = 1; return; } // Split into two halves let m = parseInt((lx + rx) / 2, 10); // Build the left subtree build(x * 2 + 1, lx, m); // Build the right subtree build(x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to make index x to 0 // and then update segment tree function update(i, x, lx, rx) { // Base Case if (rx - lx == 1) { st[x] = 0; return; } // Split into two halves let m = parseInt((lx + rx) / 2, 10); // Update Query if (i < m) update(i, x * 2 + 1, lx, m); else update(i, x * 2 + 2, m, rx); // Combining both left and right // subtree to parent node st[x] = st[x * 2 + 1] + st[x * 2 + 2]; return; } // Function to find the Kth element function getans(x, lx, rx, k, n) { // Base Condition if (rx - lx == 1) { if (st[x] == k) return lx; return n; } // Split into two halves let m = parseInt((lx + rx) / 2, 10); // Check if kth one is in left subtree // or right subtree of current node if (st[x * 2 + 1] >= k) return getans(x * 2 + 1, lx, m, k, n); else return getans(x * 2 + 2, m, rx, k - st[x * 2 + 1], n); } // Function to generate the original // permutation function getPermutation(inv, n) { // Build segment tree build(0, 0, n); // Stores the original permutation let ans = []; for(let i = n - 1; i >= 0; i--) { // Find kth one let temp = getans(0, 0, n, st[0] - inv[i], n); // Answer for arr[i] ans.push(temp + 1); // Setting found value back to 0 update(Math.max(0, temp), 0, 0, n); } // Print the permutation for(let i = n - 1; i >= 0; i--) document.write(ans[i] + " "); return; } // Driver code // Given array let inv = [ 0, 1, 1, 0, 3 ]; // Length of the given array let N = inv.length; // Function Call getPermutation(inv, N); // This code is contributed by suresh07 </script> |
Output:
4 1 3 5 2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Related Topic: Segment Tree
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
