Replace Each Element Of Array With Its Corresponding Rank

Easy
0/40
Average time to solve is 10m
profile
Contributed by
49 upvotes
Asked in companies
GrowwMAQ SoftwareUnthinkable Solutions

Problem statement

Given an array of integers 'ARR’ of size ‘N’. Replace each element of this array with its corresponding rank and return the array.


The rank of an element is an integer between 1 to ‘N’ inclusive that represents how large the element is in comparison to other elements of the array. The following rules can also define the rank of an element:


1. It is an integer starting from 1.

2. The larger the element, the larger the rank. If two elements are equal, their rank must be the same.

3. It should be as small as possible.
For Example:
'ARR' = [4, 7, 2, 90]

Here, 2 is the smallest element, followed by 4, 7, and 90. 

Hence rank of element 2 is 1, element 4 is 2, element 7 is 3, and element 90 is 4.

Hence we return [2, 3, 1, 4].
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains an integer ‘N’ representing the number of elements in ‘ARR’.

The second line contains  ‘N’ space-separated integers representing the elements present in ‘ARR’. 
Output Format :
Print space-separated elements of ‘ARR’ where the value at index ‘i’  is replaced by the rank of the element at index ‘i’ in ‘ARR’.
Note :
You do not need to print anything it has already been taken care of. Return the integer array ‘ARR’ after replacing every element with its rank.
Sample Input 1 :
2
4 -1
Sample Output 1 :
2 1 
Explanation Of Sample Input 1 :
Here, 4 is the largest element and -1 is the smallest element.

So, the rank of 4 is 2.

The rank of -1 is 1.

Thus after replacing elements with their rank we get [2, 1].
Sample Input 2 :
5
1 2 6 9 2 
Sample Output 2 :
1 2 3 4 2
Explanation Of Sample Input 2 :
Here, 1 is the smallest element, 2 is the second-smallest element and 6 is the third-smallest element and 9 is the largest element.

So, the rank of 1 should be 1.

The rank of 2 should be 2.

The rank of 6 should be 3.

The rank of 9 should be 4.

Thus after replacing elements with their rank we get [1, 2, 3, 4, 2]
Constraints :
1 <= N <= 10^4
-10^9  <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the 'ith' element of the array.

Time limit: 1 sec
Hint

Observe, the rank of an element in an array will be one more than the number of different elements in an array which is smaller than it.

Approaches (2)
Brute Force
  • First, make an array ‘temp’ of size ‘N’ and copy all the elements of ’ARR’ in it.
  • Run a loop where ‘i ranges from 0 to N-1 -:
              1. Declare a HashMap and initialise a variable ‘rank’= 1
              2. Iterate over array ‘temp’ and increment ‘rank’ by one whenever we find an element in ‘temp’ which is strictly less than ‘ARR[i]’ and not present in HashMap. After that insert the element in HashMap.
              3. Replace the value in ‘ARR[i]’ with ‘rank’.
  • Return the array ‘ARR’.
Time Complexity

O(N*N),  Where ’N’ is the size of array ‘ARR’.

 

Here, we will have two nested loops, and in the worst case the outer loop runs ‘N’ time, and the inner loop will also run ‘N’ time.

Space Complexity

O(N),  Where ’N’ is the size of array ‘ARR’.

 

Space required by the ‘temp’ array and HashMap will be of order ‘N’.

Code Solution
(100% EXP penalty)
Replace Each Element Of Array With Its Corresponding Rank
Full screen
Console