Last Updated: 3 Apr, 2021

Block Heights

Easy

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.

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

Solve now

Approaches

01 Approach

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

Solve now