Another Casual Coder

This problem exemplifies the power of a Priority Queue, as well as the advantages of having one's own implementation which you can then tweak as needed. Here it is: https://leetcode.com/problems/rank-transform-of-an-array/

First approach was to bubble sort the vals and the indexes and then just do a linear processing.Timed out (len = 10^5, bubble sort is n^2, hence 10^10, intractable on the leetcode system). Another approach was to use a Priority Queue. I already had an implementation of it, but needed to make a minor adjustment. The idea is to use the array index as the key in the priority queue and use the array value as the priority. Usually a dequeue operation only returns the key, so the minor change is to make it return the priority (array value) too. The value is needed to compare with the previous and decide whether or not to increment the index in the final array. Hence the total complexity is nlogn (the priority queue creation) + n, hence O(nlogn). For 10^5 input len, it does the trick. Code is below, cheers, ACC.


public class Solution
{
public int[] ArrayRankTransform(int[] arr)
{
if (arr == null || arr.Length == 0) return arr;

PriorityQueue pq = new PriorityQueue();
for (int i = 0; i < arr.Length; i++) pq.Enqueue(i, arr[i]);

int[] retVal = new int[arr.Length];
long previous = Int64.MinValue;
int count = 0;
while (pq.Count > 0)
{
int current = 0;
int index = (int)pq.Dequeue(ref current);
if ((long)current != previous) count++;
retVal[index] = count;
previous = current;
}

return retVal;
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private int priority;
public HeapEntry(object item, int priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public int Priority
{
get
{
return priority;
}
}
}

private int count;
private int capacity;
private HeapEntry[] heap;

public int Count
{
get
{
return this.count;
}
}

public PriorityQueue()
{
capacity = 100000;
heap = new HeapEntry[capacity];
}

public object Dequeue(ref int priority)
{
object result = heap[0].Item;
priority = heap[0].Priority;
count--;
trickleDown(0, heap[count]);
return result;
}

public void Enqueue(object item, int priority)
{
count++;
bubbleUp(count - 1, new HeapEntry(item, priority));
}

private void bubbleUp(int index, HeapEntry he)
{
int parent = (index - 1) / 2;
// note: (index > 0) means there is a parent
while ((index > 0) && (heap[parent].Priority > he.Priority))
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}

private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
if (((child + 1) < count) &&
(heap[child].Priority > heap[child + 1].Priority))
{
child++;
}
heap[index] = heap[child];
index = child;
child = (index * 2) + 1;
}
bubbleUp(index, he);
}
}