leetcode solution of problem 1409

Posted on by Admin

Queries on a Permutation With Key

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

  • In the beginning, you have the permutation P=[1,2,3,...,m].
  • For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

For complete problem please visit the below mentioned link:- Leetcode problem statement

Approach:-

The Given array is :-

M = 4 , So , p = [1,2,3,4]

P is

For I = 0 , the value is 4 in the given array. And the position of 4 in the p array is, 3. As, it’s starting from zero index.

Now, move 4 in the front position . So the new array will look like p = [4,1,2,3]

Not I = 1 , the value is 1. The position of 1 in the array p array is 1. So move the 1 in front.

So the new array will be as p = [1,4,2,3]

Now for I=2, the value is 2. the position of 2 is, 2 in p array. Move 2 in front

P = [2,1,4,3]

Now I = 3, the value is 2.  the position of 2 in P is, 0. No need to move it so the final p is = [2,1,4,3]

And the returning array is answer = [3,1,2,0] which is marked in bold.    

Flow Diagram:-

Code:-

class Solution {
     public int[] processQueries(int[] queries, int m) {
      int noOfQueries=queries.length;
        int[] answer=new int[noOfQueries];
        LinkedList queriesList=new LinkedList<>();
        for(int index=1;index>=m;index++)
        {
            queriesList.add(index);
        }
        for(int index=0;index<noOfQueries;index++)
        {
            int value=queries[index];
            int reqIndex=queriesList.indexOf(value);
           
            queriesList.remove(reqIndex);
            queriesList.addFirst(value);
            answer[index]=reqIndex;
        }
        return answer;
    }
}

For other problems and solutions please visit:- Algorithm problems