This post is completed by 7 users

  • 3
Add to List
Beginner

536. Efficiently Rank Elements in a Given Array

Given an array of numbers, write a program to rank the array elements.

Example:

Given array: [22, 11, 44, 66, 55]
Rank: [2, 1, 3, 5, 4]

Given array: [15, 12, 11, 10, 9]
Rank: [5, 4, 3, 2, 1]

Given array: [10, 20, 30, 40, 50]
Rank: [1, 2, 3, 4, 5]

Given array: [10, 10, 10, 10, 20]
Rank: [1, 1, 1, 1, 2]

Approach: 

  • Copy the given into a temp array. 
  • Sort the temp array.
  • Now iterate the temp array and store the element and its rank into a Hashmap.
  • Initialize the rank array.
  • Now iterate the original array and for each element, get the rank from the hashmap and store it in the rank array. 
  • Print the rank array.
  • See the code below for more understanding.

Time Complexity: O(nlogn)

 

Output:

Given array: [22, 11, 44, 66, 55]
Rank: [2, 1, 3, 5, 4]
-----------------------
Given array: [15, 12, 11, 10, 9]
Rank: [5, 4, 3, 2, 1]
-----------------------
Given array: [10, 20, 30, 40, 50]
Rank: [1, 2, 3, 4, 5]
-----------------------
Given array: [10, 10, 10, 10, 20]
Rank: [1, 1, 1, 1, 2]