Block Heights

Easy
0/40
Average time to solve is 20m
profile
Contributed by
15 upvotes

Problem statement

There are ‘N’ empty places and you are given ‘N’ blocks. The task is to fill each place with a block of some height. After filling all the empty places all blocks should be arranged in increasing order of their height.

Given an array 'heights' which denotes the blocks arranged in some order. You have to find and return the number of blocks that are present in the wrong locations.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains N space-separated integers denoting the elements of the array “heights”.
Output Format : 
For each test case, print the number of blocks that are present in the wrong locations.

Print the output of each test case on a new line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= heights[i] <= 10^9

Where 'heights[i]' represents the height of the ith block.

Time Limit: 1 sec
Sample Input 1 :
2
4    
1 5 2 4
4
2 3 5 4
Sample Output 1 :
3
2
Explanation of Sample output 1:
For the first test case, Blocks with heights 2, 5, 4 are present in the wrong locations.

For the second test case, Blocks with heights 4, 5 are present in the wrong locations.

Sample Input 2:

2
2
1 2
5
5 1 3 2 4
Sample output 2:
0
4
Hint

Can you think of how to arrange the blocks in the correct order?

Approaches (1)
Sorting

The idea here is to create a copy of the array 'HEIGHTS', say 'HEIGHT_COPY', and then sort the 'HEIGHT_COPY' array. Now check if the element present at 'HEIGHTS'[i] is not equal to the 'HEIGHT_COPY'[i], then increment the 'ANS' count by 1.

 

The algorithm is as follows:

 

  • Declare a variable 'ANS' = 0, to store the number of blocks that are present in the wrong locations.
  • Declare an array 'HEIGHT_COPY' of size ‘N’.
  • Iterate from ‘i’ = 0 to ‘N’ - 1:
    • Set 'HEIGHT_COPY'[i] to 'HEIGHTS'[i].
  • Sort 'HEIGHT_COPY' array.
  • Iterate from ‘i’ = 0 to ‘N’ - 1 :
    • If 'HEIGHTS'[i] != 'HEIGHT_COPY'[i], then increment 'ANS' by 1.
  • Return the 'ANS'.
Time Complexity

O(N*logN), where N is the size of the array heights.

 

Since we are sorting the array heightCopy which takes the order of N*logN time. Hence the overall time complexity is O(N*logN).

Space Complexity

O(N), where N is the number of vertices.

 

Since we are using an auxiliary array heightCopy which is of order N. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Block Heights
Full screen
Console