Towers
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.

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

Question

Towers

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.

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.

Accepted Answer

I stored the difference in heights.
Sorted this array
And filled the difference such that max length is observed.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(nlogn)Explanation:

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)).

Python (3.5)

'''

    Time Complexity : O(N * Log(N)).

	Space Complexity : O(N)



	Where 'N' is the size of the array.

'''



def minTowers(arr, n):

    base = []

    

    for cube in arr:

        low = 0

        high = len(base) - 1

        pos = len(base)

        

        # Binary search the position.

        while low <= high:

            mid = (low + high) // 2

            if base[mid] > cube:

                pos = mid

                high = mid - 1

            else:

                low = mid + 1

         

        # Create a new tower.

        if pos == len(base):

            base.append(cube)

        # Put on top of another tower.

        else:

            base[pos] = cube

    

    return len(base)

Java (SE 1.8)

/*

	Time Complexity : O(N * Log(N)).

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



import java.util.ArrayList;



public class Solution {

	public static int minTowers(ArrayList arr, int n) {

		ArrayList base = new ArrayList<>();



		for (int i = 0; i < n; ++i) {

			int z = arr.get(i);



			int low = 0, high = base.size();

			while (low < high) {

				int mid = (low + high) / 2;



				if (base.get(mid) > z) {

					high = mid;

				} else {

					low = mid + 1;

				}

			}

			if (low == base.size()) {



				// Create new tower.

				base.add(z);

			} else {



				// Add to min towers.

				base.set(low, z);

			}

		}



		return base.size();

	}

}

C++ (g++ 5.4)

/*

	Time Complexity : O(N * Log(N)).

	Space Complexity : O(N)



	Where 'N' is the size of the array.

*/



int minTowers(vector &arr, int n)

{

	vector base;



	for (int i = 0; i < n; ++i)

	{

		int z = arr[i] ;



		int low = 0, high = base.size();

		while (low < high)

		{

			int mid = (low + high) / 2;

			if (base[mid] > z)

			{

				high = mid;

			}



			else {

				low = mid + 1;

			}

		}

		if (low == base.size())

		{

			// Create new tower.

			base.push_back(z);

		}

		else

		{

			// Add to min towers.

			base[low] = z;

		}

	}



	return base.size() ;

}

Accepted Answer

#arr = [4,5,1,2], n = len(arr)
ans = 0
for i in range(0,n):
    if arr[i] < arr[i+1] :

           i +=1

    if arr[i] > arr[i+1] or i == n-1 :

         ans +=1

         i +=1

return ans