Towers

Moderate

0/80

Average time to solve is 15m

Contributed by

13 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’, where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output format:

For each test case, print a single line containing a single integer denoting the minimum possible number of towers.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 2000
1 <= ARR[ i ] <= 2000

Where ‘T’ is the total number of test cases, and 'N’ is the length of the array, and ‘ARR[ i ]’ is the array element at index ‘i’.

Time limit: 1 second.

Sample Input 1:

Sample Output 1:

1
3

Explanation of the Sample Input 1:

For the first test case:
The answer will be one because you can stack one over two over 3. Therefore only these can be inserted in the same tower.


For the second test case:
The answer will be three because the array is in ascending order, and since we can only stack smaller values, three towers will have to be made.

Sample Input 2:

2
5
7 9 8 7 6
6
5 4 5 4 6 5

Sample Output 2:

2
3

Hint 1

For a given cube, can you find the best existing base cube in logarithmic time complexity?

Approaches (1)

Approach 1

Using binary search.

The main idea is to use a array to maintain all the bases of different towers that we made. If for some cube, we find a cube greater than itself, we can place it and delete the cube we put it on from the set and insert the new base.

Maintain an array ‘BASE.’
For each cube in the array, find the upper bound value of the current cube.
If no greater value exists, then insert the value in the cube.
Else delete the upper bound value and insert the current cube’s value in the set.
After all the values have been processed, the size of the set in our answer.

Time Complexity

O(N * log(N)), where ‘N’ is the length of the given array.

Since we try to place ‘N’ cubes and each cube, we query once, and it takes log(N) for each query. Therefore the final time-complexity is O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the length of the given array.

Since we are using an array to keep track of the elements, therefore, net space complexity will be O(N).

(100% EXP penalty)

Towers

Console