SDE - 1

You are given a square matrix of non-negative integers of size 'N x N'. Your task is to rotate that array by 90 degrees in an anti-clockwise direction without using any extra space.

For example:

For given 2D array :

    [    [ 1,  2,  3 ],
         [ 4,  5,  6 ],
         [ 7,  8,  9 ]  ]

After 90 degree rotation in anti clockwise direction, it will become:

    [   [ 3,  6,  9 ],
        [ 2,  5,  8 ],
        [ 1,  4,  7 ]   ]

During Endgame Natasha(Black Widow) sacrificed her life for the soul stone.

Hulk wants to bring Natasha back. So, he came to Goku for help. Goku told him he will help Hulk if he can solve the task given by him. Hulk accepts the challenge of Goku.

Goku gave Hulk a list of ‘N’ numbers and a number ‘K’. The task is to rearrange the elements of the list such that all elements less than or equal to ‘K’ become adjacent to each other. Hulk can only swap any two elements of the array/list multiple times. Goku wants Hulk to do the task using the minimum number of swaps.

As Hulk is not good at maths so he called you to solve the task given by Goku to save Natasha.The fate of Natasha lies in your hand.

Design a Least Recently Used Cache using OOPS