SDE - 1

You are given ‘N’ cubes in an array ‘ARR’ in a certain order, and your task is to build towers using them. Whenever two cubes are on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower or begin a new tower. What is the minimum possible number of towers?

For example:

Given ‘N’ = 3, ‘ARR’[] = 3, 2, 1.
The answer will be one because you can stack one over two over 3. Therefore only these can be inserted in the same tower.

You’re given an array ‘ARR’ of size N and an integer K. Your task is to determine the minimum number of elements that should be removed from the array such that the difference between the maximum and the minimum element in the remaining array is less than or equal to K.

Aragorn is a great ruler and desires to become the most powerful in the entire world. There are ‘N’ kingdoms, kingdoms are numbered from 0 to 'N' - 1 and form of a tree, you are also given the information about the edges of this tree depicting all the Kingdoms that are adjacent to each other.

The ruler with the most kingdoms is considered the most powerful. You desire to become the greatest ruler without having to fight with Aragorn. Kingdoms are conquered one at a time in turns in order to make the process smooth and less violent.

Aragorn initially rules only the ‘X^th’ kingdom and all other kingdoms are not ruled by anyone. In each turn, a ruler can conquer another kingdom that is adjacent to one of his current kingdoms and is ruled by none of the rulers, the opponent plays the next turn and the process is repeated. The game continues until both the players run out of moves. If a ruler has no available adjacent kingdom to conquer then he passes his turn. In the end, the ruler with more kingdoms under his control wins the game.

Aragorn gives you an advantage in the first turn, letting you choose a kingdom of your choice, but for all other moves, you can only conquer a kingdom adjacent to one of your current kingdoms. If Aragorn plays optimally, determine if it’s possible for you to win by becoming the most powerful or not, print “true” if you can become more powerful than Aragorn, else return “false”.

For Example :

If N = 7, X = 2 and Edges = { {0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {4, 6} }

Then the tree is: 

Here N = 7 depicts that there are seven kingdoms (numbered from 0 to 6). Edges depict that kingdom-0 and kingdom-1 are adjacent, kingdom-0 and kingdom-2 are adjacent, and so on. And Aragorn initially controls kingdom-2.
Then in this case, if you select kingdom-1 in your first then, then Aargon will select kingdom-0 in the next turn, as both rulers play optimally, therefore in the end Aargon will be ruling kingdom-0, kingdom-2 and kingdom-3 and the remaining four kingdoms will be ruled by you. Hence you will be able to win the game and therefore we will print “true”.

You are given an Integer array ‘ARR’ and an Integer ‘K’.

Your task is to find the ‘K’ most frequent elements in ‘ARR’. Return the elements in any order.

For Example:

You are given ‘ARR’ = {1, 2, 2, 3, 3} and ‘K’ = 2. 

The answer will {2, 3} as 2 and 3 are the elements occurring most times.