Replace Each Element Of The Array By Its Rank In The Array In Java

When working with data arrays in Java, you often encounter situations where the absolute values of elements are less important than their relative order or standing within the dataset. Ranking an array transforms its elements into a sequence representing their position if the array were sorted.

In this article, you will learn how to replace each element of an array with its 1-based rank, where identical elements receive the same rank.

Problem Statement

Consider a numerical array where each element needs to be replaced by its rank. The rank signifies the element's position if the array were sorted in ascending order. If multiple elements have the same value, they should all be assigned the same rank. This operation is crucial in statistical analysis, competitive programming, and data preprocessing tasks where the distribution and relative magnitude of values are key.

Example

Given an input array: [10, 40, 20, 40, 30]

The array elements, when replaced by their ranks, would be: [1, 4, 2, 4, 3]

Background & Knowledge Prerequisites

To understand the solutions presented in this article, a basic understanding of the following Java concepts is beneficial:

• Arrays: Creating, accessing, and iterating through array elements.
• Sorting: Using Arrays.sort() method.
• Hash Maps (HashMap): Storing key-value pairs for efficient lookups.
• Loops: for loops for iteration.

Relevant imports needed will primarily be java.util.Arrays and java.util.HashMap.

Use Cases or Case Studies

Replacing array elements with their ranks is useful in several scenarios:

• Statistical Analysis: Converting raw scores into ranks for non-parametric tests like Spearman's rank correlation.
• Competitive Programming: Solving problems that involve relative ordering or percentile calculations, often to optimize comparisons.
• Data Preprocessing: Normalizing data by transforming values into ranks before feeding them into machine learning models, which can reduce the impact of outliers.
• Leaderboards: Determining positions in a competition or game where identical scores receive the same rank.
• Database Indexing: Ranking can sometimes be used to create custom indexes based on value distribution rather than raw values.

Solution Approaches

Here, we will explore two distinct approaches to replace array elements by their ranks: one using sorting and a hash map for efficiency, and another brute-force method for conceptual clarity.

Approach 1: Using Sorting and a HashMap

This approach leverages sorting to determine the order of elements and a hash map to efficiently store and retrieve the assigned ranks for each unique value.

Summary: Create a sorted copy of the array, then iterate through the sorted array to assign unique ranks to unique values using a HashMap. Finally, iterate through the original array, replacing each element with its rank looked up from the HashMap.

// Replace Array Elements by Rank using Sorting and HashMap
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Define the input array
        int[] originalArray = {10, 40, 20, 40, 30};
        System.out.println("Original Array: " + Arrays.toString(originalArray));

        // Step 2: Create a copy of the original array to sort
        int[] sortedArray = Arrays.copyOf(originalArray, originalArray.length);

        // Step 3: Sort the copied array
        Arrays.sort(sortedArray);

        // Step 4: Create a HashMap to store value-rank mappings
        Map<Integer, Integer> rankMap = new HashMap<>();
        int rank = 1;

        // Step 5: Iterate through the sorted array to assign ranks
        // Assign ranks to unique elements. Duplicates will get the same rank.
        for (int element : sortedArray) {
            if (!rankMap.containsKey(element)) {
                rankMap.put(element, rank);
                rank++;
            }
        }

        // Step 6: Create a new array to store the ranked elements
        int[] rankedArray = new int[originalArray.length];

        // Step 7: Iterate through the original array and replace elements with their ranks
        for (int i = 0; i < originalArray.length; i++) {
            rankedArray[i] = rankMap.get(originalArray[i]);
        }

        // Step 8: Print the ranked array
        System.out.println("Ranked Array (Approach 1): " + Arrays.toString(rankedArray));
    }
}

Run

Sample Output:

Original Array: [10, 40, 20, 40, 30]
Ranked Array (Approach 1): [1, 4, 2, 4, 3]

Stepwise Explanation:

1. Duplicate Array and Sort: A copy of the originalArray is made (sortedArray) to avoid modifying the original order. This copy is then sorted in ascending order.
2. Initialize HashMap: A HashMap called rankMap is created to store unique array values as keys and their corresponding ranks as values. A rank counter is initialized to 1.
3. Assign Ranks: The sortedArray is iterated. For each element:

• If the element is not already a key in rankMap, it means this is the first time we're encountering this unique value.
• The element is added to rankMap with the current rank value.
• The rank counter is then incremented. This ensures that subsequent *unique* values get the next higher rank. Duplicate values (which will appear consecutively in the sorted array) will not be added to the map again, thus maintaining their initially assigned rank.

1. Replace Elements: A new rankedArray is created. The originalArray is iterated, and for each element, its rank is retrieved from rankMap and placed into the rankedArray at the corresponding index.

Approach 2: Brute Force Counting

This approach involves iterating through the array multiple times to count smaller elements for each value, which directly determines its rank.

Summary: For each element in the original array, iterate through the entire array again to count how many elements are strictly smaller than it. Add one to this count to determine its 1-based rank.

// Replace Array Elements by Rank using Brute Force
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Define the input array
        int[] originalArray = {10, 40, 20, 40, 30};
        System.out.println("Original Array: " + Arrays.toString(originalArray));

        // Step 2: Create a new array to store the ranked elements
        int[] rankedArray = new int[originalArray.length];

        // Step 3: Iterate through each element of the original array
        for (int i = 0; i < originalArray.length; i++) {
            int currentElement = originalArray[i];
            int rank = 1; // Ranks are 1-based

            // Step 4: For each element, count how many elements are smaller than it
            for (int j = 0; j < originalArray.length; j++) {
                // If another element is strictly smaller than the current element,
                // it contributes to increasing the current element's rank.
                if (originalArray[j] < currentElement) {
                    rank++;
                }
            }
            // Step 5: Assign the calculated rank to the current element's position
            rankedArray[i] = rank;
        }

        // Step 6: Print the ranked array
        System.out.println("Ranked Array (Approach 2): " + Arrays.toString(rankedArray));
    }
}

Run

Sample Output:

Original Array: [10, 40, 20, 40, 30]
Ranked Array (Approach 2): [1, 4, 2, 4, 3]

Stepwise Explanation:

1. Initialize rankedArray: A new array rankedArray of the same size as originalArray is created to store the results.
2. Outer Loop: The code iterates through each element of the originalArray using an outer loop (i).
3. Inner Loop and Rank Calculation: For each currentElement at originalArray[i]:

• A rank variable is initialized to 1 (since ranks are 1-based).
• An inner loop (j) iterates through the *entire* originalArray again.
• Inside the inner loop, if an originalArray[j] is strictly less than currentElement, it means currentElement should have a higher rank, so rank is incremented.

1. Assign Rank: After checking all other elements, the final rank value for currentElement is assigned to rankedArray[i]. This process repeats for all elements in the originalArray.

Conclusion

Replacing array elements with their ranks is a common task in data manipulation. We explored two methods to achieve this: a more efficient approach utilizing sorting and a HashMap, and a straightforward brute-force method. The sorting and HashMap approach offers better performance for larger arrays due to its O(N log N) time complexity (dominated by sorting) compared to the brute-force O(N^2) complexity. Both methods correctly handle duplicate elements by assigning them the same rank.

Summary

• Problem: Replace array elements with their 1-based ranks, assigning identical ranks to duplicate values.
• Approach 1 (Sorting + HashMap):
• Creates a sorted copy.
• Uses a HashMap to map unique values to their ranks after sorting.
• Iterates through the original array to replace elements using the map.
• Efficient for larger datasets (O(N log N)).
• Approach 2 (Brute Force):
• For each element, counts how many other elements are strictly smaller than it.
• Adds 1 to the count to get the 1-based rank.
• Simple to understand but less efficient (O(N^2)).
• Benefits of Ranking: Useful in statistics, data preprocessing, and competitive programming for relative comparisons and normalization.