Array Rank Transform

XXX. Array Rank Transform

Array

Heap

Sorting

Problem Statement:

Given an array of integers arr, replace each element with its rank. The rank represents how large the element is, where rank 1 is the smallest element and two equal elements should have the same rank.

• Rank should start from 1
• Equal elements get same rank
• Original positions must be preserved

Algorithm:

1. **Initial Setup**:
   • Create pairs of (value, index)
   • Use heap to process in sorted order
   • Track rank and previous value
2. **Processing**:
   • Pop elements from heap in order
   • Increment rank for new values
   • Assign ranks to original positions

Complexity:

Time Complexity: O(n log n) for heap operations
Space Complexity: O(n) for auxiliary arrays

Implementation:

Java Solution:

public int[] arrayRankTransform(int[] arr) {
    // Create pairs of (value, index)
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    for (int i = 0; i < arr.length; i++) 
        pq.offer(new int[]{arr[i], i});

    int[] ranks = new int[arr.length];
    int rank = 0;
    Integer prev = null;

    while (!pq.isEmpty()) {
        int[] pair = pq.poll();
        if (prev == null || pair[0] != prev) 
            rank++;
        prev = pair[0];
        ranks[pair[1]] = rank;
    }

    return ranks;
}
                

Python Solution:

def arrayRankTransform(self, arr: List[int]) -> List[int]:
    # Create pairs of (value, index)
    arr = [(n, i) for i, n in enumerate(arr)]
    heapq.heapify(arr)

    ranks = [0 for x in range(len(arr))]
    rank = 0
    prev = None

    while arr:
        n, i = heapq.heappop(arr)
        if n != prev:
            rank += 1
        prev = n
        ranks[i] = rank

    return ranks
                

C++ Solution:

vector arrayRankTransform(vector& arr) {
    // Create pairs of (value, index)
    priority_queue, vector>, 
                  greater>> pq;
    for (int i = 0; i < arr.size(); i++)
        pq.push({arr[i], i});

    vector ranks(arr.size());
    int rank = 0;
    int prev = INT_MIN;
    bool first = true;

    while (!pq.empty()) {
        auto [val, idx] = pq.top();
        pq.pop();
        if (first || val != prev)
            rank++;
        prev = val;
        first = false;
        ranks[idx] = rank;
    }

    return ranks;
}
                

Explanation:

• **Heap Usage**:
  • Heap naturally orders elements
  • Maintains value-index pairs together
  • Processes elements in sorted order
• **Rank Assignment**:
  • Compare with previous value
  • Increment rank for new values only
  • Use index to place rank in correct position
• **Implementation Notes**:
  • Handle initial case separately
  • Track previous value for equality check
  • Use auxiliary array for final ranks