Given an integer M which represents an array initially having numbers 1 to M. Also given is a Query array. For every query, search the number in the initial array and bring it to the front of the array. The task is to return the indexes of the searched element in the given array for every query.
Examples:
Input : Q[] = {3, 1, 2, 1}, M = 5
Output : [2, 1, 2, 1]
Explanations :
Since m = 5 the initial array is [1, 2, 3, 4, 5].
Query1: Search for 3 in the [1, 2, 3, 4, 5] and move it in the beginning. After moving, the array looks like [3, 1, 2, 4, 5]. 3 is at index 2.
Query2: Move 1 from [3, 1, 2, 4, 5] to the beginning of the array to make the array look like [1, 3, 2, 4, 5]. 1 is present at index 1.
Query3: Move 2 from [1, 3, 2, 4, 5] to the beginning of the array to make the array look like [2, 1, 3, 2, 4, 5]. 2 is present at index 2.
Query4: Move 1 from [2, 1, 3, 4, 5] to the beginning of the array to make the array look like [1, 2, 3, 4, 5]. 1 is present at index 1.Input : Q[] = {4, 1, 2, 2}, M = 4
Output : 3, 1, 2, 0
Naive approach: The naive approach is to use a hash table to search for the element and linearly do shifts by performing swaps. The time complexity will be quadratic in nature for this approach.
Below is the naive implementation of the above approach:
C++
// C++ program to search the element// in an array for every query and// move the searched element to// the front after every query#include <bits/stdc++.h>using namespace std;// Function to find the indicesvector<int> processQueries(int Q[], int m, int n){ int a[m + 1], pos[m + 1]; for (int i = 1; i <= m; i++) { a[i - 1] = i; pos[i] = i - 1; } vector<int> ans; // iterate in the query array for (int i = 0; i < n; i++) { int q = Q[i]; // store current element int p = pos[q]; ans.push_back(p); for (int i = p; i > 0; i--) { // swap positions of the element swap(a[i], a[i - 1]); pos[a[i]] = i; } pos[a[0]] = 0; } // return the result return ans;}// Driver codeint main(){ // initialise array int Q[] = { 3, 1, 2, 1 }; int n = sizeof(Q) / sizeof(Q[0]); int m = 5; vector<int> ans; // Function call ans = processQueries(Q, m, n); // Print answers to queries for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; return 0;} |
Java
// Java program to search the element// in an array for every query and// move the searched element to// the front after every queryimport java.util.*;class GFG{ // Function to find the indicesstatic Vector<Integer> processQueries(int Q[], int m, int n){ int []a = new int[m + 1]; int []pos = new int[m + 1]; for (int i = 1; i <= m; i++) { a[i - 1] = i; pos[i] = i - 1; } Vector<Integer> ans = new Vector<Integer>(); // iterate in the query array for (int i = 0; i < n; i++) { int q = Q[i]; // store current element int p = pos[q]; ans.add(p); for (int j = p; j > 0; j--) { // swap positions of the element a[j] = a[j] + a[j - 1]; a[j - 1] = a[j] - a[j - 1]; a[j] = a[j] - a[j - 1]; pos[a[j]] = j; } pos[a[0]] = 0; } // return the result return ans;} // Driver codepublic static void main(String[] args){ // initialise array int Q[] = { 3, 1, 2, 1 }; int n = Q.length; int m = 5; Vector<Integer> ans = new Vector<Integer>(); // Function call ans = processQueries(Q, m, n); // Print answers to queries for (int i = 0; i < ans.size(); i++) System.out.print(ans.get(i)+ " "); }}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to search the element # in an array for every query and # move the searched element to # the front after every query# Function to find the indices def processQueries(Q, m, n) : a = [0]*(m + 1); pos = [0]*(m + 1); for i in range(1, m + 1) : a[i - 1] = i; pos[i] = i - 1; ans = []; # iterate in the query array for i in range(n) : q = Q[i]; # store current element p = pos[q]; ans.append(p); for i in range(p,0,-1) : # swap positions of the element a[i], a[i - 1] = a[i - 1],a[i]; pos[a[i]] = i; pos[a[0]] = 0; # return the result return ans; # Driver code if __name__ == "__main__" : # initialise array Q = [ 3, 1, 2, 1 ]; n = len(Q); m = 5; ans = []; # Function call ans = processQueries(Q, m, n); # Print answers to queries for i in range(len(ans)) : print(ans[i],end=" "); # This code is contributed by Yash_R |
C#
// C# program to search the element// in an array for every query and// move the searched element to// the front after every queryusing System;using System.Collections.Generic;public class GFG{// Function to find the indicesstatic List<int> processQueries(int []Q, int m, int n){ int []a = new int[m + 1]; int []pos = new int[m + 1]; for(int i = 1; i <= m; i++) { a[i - 1] = i; pos[i] = i - 1; } List<int> ans = new List<int>(); // Iterate in the query array for(int i = 0; i < n; i++) { int q = Q[i]; // Store current element int p = pos[q]; ans.Add(p); for(int j = p; j > 0; j--) { // Swap positions of the element a[j] = a[j] + a[j - 1]; a[j - 1] = a[j] - a[j - 1]; a[j] = a[j] - a[j - 1]; pos[a[j]] = j; } pos[a[0]] = 0; } // Return the result return ans;}// Driver codepublic static void Main(String[] args){ // Initialise array int []Q = { 3, 1, 2, 1 }; int n = Q.Length; int m = 5; List<int> ans = new List<int>(); // Function call ans = processQueries(Q, m, n); // Print answers to queries for(int i = 0; i < ans.Count; i++) Console.Write(ans[i] + " ");}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// JavaScript program to search the element// in an array for every query and// move the searched element to// the front after every query// Function to find the indicesfunction processQueries(Q,m,n){ let a = new Array(m + 1); let pos = new Array(m + 1); for (let i = 1; i <= m; i++) { a[i - 1] = i; pos[i] = i - 1; } let ans = []; // iterate in the query array for (let i = 0; i < n; i++) { let q = Q[i]; // store current element let p = pos[q]; ans.push(p); for (let j = p; j > 0; j--) { // swap positions of the element a[j] = a[j] + a[j - 1]; a[j - 1] = a[j] - a[j - 1]; a[j] = a[j] - a[j - 1]; pos[a[j]] = j; } pos[a[0]] = 0; } // return the result return ans;}// Driver code// initialise arraylet Q=[3, 1, 2, 1];let n = Q.length;let m = 5;let ans=[];// Function callans = processQueries(Q, m, n);// Print answers to queriesfor (let i = 0; i < ans.length; i++) document.write(ans[i]+ " "); // This code is contributed by rag2127</script> |
Output:
2 1 2 1
Time complexity: O(n*p)
Auxiliary space: O(m)
Efficient Approach: An efficient method to solve the above problem is to use Fenwick Tree. Using the below 3 operations, the problem can be solved.
- Push element in the front
- Find the index of a number
- Update the indexes of the rest of the elements.
Keep the elements in a sorted manner using the set data structure, and then follow the below-mentioned points:
- Instead of pushing the element to the front i.e assigning an index 0 for every query.
- We assign -1 for the first query, -2 for the second query, -3 for the third, and so on till -m.
- Doing so, the range of index’s updates to [-m, m]
- Perform a right shift for all values [-m, m] by a value of m, so our new range is [0, 2m]
- Initialize a Fenwick tree of size 2m and set all the values from [1…m] i.e [m..2m]
- For every query, find its position by finding the number of set elements lesser than the given query, once done set its position to 0 in the Fenwick tree.
Below is the implementation of the above approach:
C++
// C++ program to search the element// in an array for every query and// move the searched element to// the front after every query#include <bits/stdc++.h>using namespace std;// Function to update the fenwick treevoid update(vector<int>& tree, int i, int val){ // update the next element while (i < tree.size()) { tree[i] += val; // move to the next i += (i & (-i)); }}// Function to get the// sum from the fenwick treeint getSum(vector<int>& tree, int i){ int s = 0; // keep adding till we have not // reached the root of the tree while (i > 0) { s += tree[i]; // move to the parent i -= (i & (-i)); } return s;}// function to process the queriesvector<int> processQueries(vector<int>& queries, int m){ vector<int> res, tree((2 * m) + 1, 0); // Hash-table unordered_map<int, int> hmap; // Iterate and increase the frequency // count in the fenwick tree for (int i = 1; i <= m; ++i) { hmap[i] = i + m; update(tree, i + m, 1); } // Traverse for all queries for (int querie : queries) { // Get the sum from the fenwick tree res.push_back(getSum(tree, hmap[querie]) - 1); // remove it from the fenwick tree update(tree, hmap[querie], -1); // Add it back at the first index update(tree, m, 1); hmap[querie] = m; m--; } // return the final result return res;}// Driver codeint main(){ // initialise the Queries vector<int> Queries = { 4, 1, 2, 2 }; // initialise M int m = 4; vector<int> ans; ans = processQueries(Queries, m); for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; return 0;} |
Java
// Java program to search the element// in an array for every query and// move the searched element to// the front after every queryimport java.util.*;class GFG{// Function to update the fenwick treestatic void update(int []tree, int i, int val){ // update the next element while (i < tree.length) { tree[i] += val; // move to the next i += (i & (-i)); }}// Function to get the// sum from the fenwick treestatic int getSum(int []tree, int i){ int s = 0; // keep adding till we have not // reached the root of the tree while (i > 0) { s += tree[i]; // move to the parent i -= (i & (-i)); } return s;}// function to process the queriesstatic Vector<Integer> processQueries(int []queries, int m){ Vector<Integer>res = new Vector<>(); int []tree = new int[(2 * m) + 1]; // Hash-table HashMap<Integer,Integer> hmap = new HashMap<>(); // Iterate and increase the frequency // count in the fenwick tree for (int i = 1; i <= m; ++i) { hmap.put(i, i+m); update(tree, i + m, 1); } // Traverse for all queries for (int querie : queries) { // Get the sum from the fenwick tree res.add(getSum(tree, hmap.get(querie) - 1)); // remove it from the fenwick tree update(tree, hmap.get(querie), -1); // Add it back at the first index update(tree, m, 1); hmap.put(querie, m); m--; } // return the final result return res;}// Driver codepublic static void main(String[] args){ // initialise the Queries int []Queries = { 4, 1, 2, 2 }; // initialise M int m = 4; Vector<Integer> ans; ans = processQueries(Queries, m); System.out.print(ans);}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to search the element# in an array for every query and# move the searched element to# the front after every query# Function to update the fenwick treedef update(tree, i, val): # Update the next element while (i < len(tree)): tree[i] += val # Move to the next i += (i & (-i))# Function to get the# sum from the fenwick treedef getSum(tree, i): s = 0 # Keep adding till we have not # reached the root of the tree while (i > 0): s += tree[i] # Move to the parent i -= (i & (-i)) return s# Function to process the queriesdef processQueries(queries, m): res = [] tree = [0] * (2 * m + 1) # Hash-table hmap = {} # Iterate and increase the frequency # count in the fenwick tree for i in range(1, m + 1): hmap[i] = i + m update(tree, i + m, 1) # Traverse for all queries for querie in queries: # Get the sum from the fenwick tree res.append(getSum(tree, hmap[querie]) - 1) # Remove it from the fenwick tree update(tree, hmap[querie], -1) # Add it back at the first index update(tree, m, 1) hmap[querie] = m m -= 1 # Return the final result return res# Driver codeif __name__ == "__main__": # Initialise the Queries Queries = [ 4, 1, 2, 2 ] # Initialise M m = 4 ans = processQueries(Queries, m) for i in range(len(ans)): print(ans[i], end = " ")# This code is contributed by chitranayal |
C#
// C# program to search the element// in an array for every query and// move the searched element to// the front after every queryusing System;using System.Collections.Generic;class GFG{// Function to update the fenwick treestatic void update(int []tree, int i, int val){ // update the next element while (i < tree.Length) { tree[i] += val; // move to the next i += (i & (-i)); }}// Function to get the// sum from the fenwick treestatic int getSum(int []tree, int i){ int s = 0; // keep adding till we have not // reached the root of the tree while (i > 0) { s += tree[i]; // move to the parent i -= (i & (-i)); } return s;}// function to process the queriesstatic List<int> processQueries(int []queries, int m){ List<int>res = new List<int>(); int []tree = new int[(2 * m) + 1]; // Hash-table Dictionary<int, int> hmap = new Dictionary<int, int>(); // Iterate and increase the frequency // count in the fenwick tree for (int i = 1; i <= m; ++i) { hmap.Add(i, i+m); update(tree, i + m, 1); } // Traverse for all queries foreach (int querie in queries) { // Get the sum from the fenwick tree res.Add(getSum(tree, hmap[querie] - 1)); // remove it from the fenwick tree update(tree, hmap[querie], -1); // Add it back at the first index update(tree, m, 1); if(hmap.ContainsKey(querie)) hmap[querie] = m; else hmap.Add(querie, m); m--; } // return the readonly result return res;}// Driver codepublic static void Main(String[] args){ // initialise the Queries int []Queries = {4, 1, 2, 2}; // initialise M int m = 4; List<int> ans; ans = processQueries(Queries, m); foreach (int i in ans) Console.Write(i + " ");}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to search the element// in an array for every query and// move the searched element to// the front after every query // Function to update the fenwick tree function update(tree,i,val) { // update the next element while (i < tree.length) { tree[i] += val; // move to the next i += (i & (-i)); } } // Function to get the// sum from the fenwick tree function getSum(tree,i) { let s = 0; // keep adding till we have not // reached the root of the tree while (i > 0) { s += tree[i]; // move to the parent i -= (i & (-i)); } return s; } // function to process the queries function processQueries(queries,m) { let res = []; let tree = new Array((2 * m) + 1); for(let i=0;i<tree.length;i++) { tree[i]=0; } // Hash-table let hmap = new Map(); // Iterate and increase the frequency // count in the fenwick tree for (let i = 1; i <= m; ++i) { hmap.set(i, i+m); update(tree, i + m, 1); } // Traverse for all queries for (let querie=0;querie< queries.length;querie++) { // Get the sum from the fenwick tree res.push(getSum(tree, hmap.get(queries[querie]) - 1)); // remove it from the fenwick tree update(tree, hmap.get(queries[querie]), -1); // Add it back at the first index update(tree, m, 1); hmap.set(queries[querie], m); m--; } // return the final result return res; } // Driver code let Queries=[4, 1, 2, 2]; // initialise M let m = 4; let ans; ans = processQueries(Queries, m); document.write(ans.join(" ")); // This code is contributed by avanitrachhadiya2155</script> |
Output:
3 1 2 0
Time complexity: O(nlogn)
Auxiliary space: O(n)
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!
