Another Casual Coder

This is a problem that exemplifies how to use mathematics and a priority queue to get to a fast and efficient solution. Here it is: https://leetcode.com/problems/rank-teams-by-votes/


It is clear that this is a sorting problem. Eventually we should have a set of teams from A..Z with a "rank" associated to each team based on the votes. Then all we need to do is sort based on the rank.
In order to calculate this rank, though, we should think about the mathematics here. We want to ensure that a vote for the 1st position, for example, is infinitely higher than a vote for the 2nd position, and so on. Also, we want to make sure that if after all the votes there is still a tie, we untie based on the alphabetical position of the letters.
In order to do all that, we'll make use of big, big numbers (hence, make sure to use System.Numerics BigInteger). Let's assume that we have all the letters in the input, hence we have 26 letters. In order to account for the vote in the first position, the rank that we'll encode will be:

1001 ^ 26

And for the second position it will be 1001 ^ 25. We claim that this will ensure that 1 vote for first position is better than all other votes for second position. Suppose that "A" gets voted for first, hence:

A -> 1001 ^ 26

And "B" gets 1000 votes for second place, hence

B -> 1000 * (1001 ^ 25) which is less than 1001 * (1001 ^ 25) = 1001 ^ 26

Hence, A > B (since 1001 > 1000). We also add the initial values for the letters from 25..0 in order to account for the alphabetical order.

We use the rank as the priority in a priority queue (modified to take a BigInteger as a priority).

When we run this algorithm, it is clear that it runs in linear time with constant space (since we have max of 26 letters). Code is below, cheers, ACC.


public class Solution
{
public string RankTeams(string[] votes)
{
BigInteger[] rank = new BigInteger[26];

//Alphabetical tiebreak
for (int i = 0; i < 26; i++)
{
rank[i] = 25 - i;
}

//Calculation
for (int pos = 0; pos < votes[0].Length; pos++)
{
int exp = 26 - pos;
int seed = 1001;

for (int i = 0; i < votes.Length; i++)
{
int index = (int)(votes[i][pos] - 'A');
rank[index] += BigInteger.Pow(seed, exp);
}
}

//Sort using the pQueue
PriorityQueue pQueue = new PriorityQueue();
for (int i = 0; i < votes[0].Length; i++)
{
int index = (int)(votes[0][i] - 'A');
pQueue.Enqueue(index, rank[index]);
}

string retVal = "";
while (pQueue.Count > 0)
{
int index = (int)pQueue.Dequeue();
retVal += ((char)(index + 'A')).ToString();
}

return retVal;
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private BigInteger priority;
public HeapEntry(object item, BigInteger priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public BigInteger 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 long weight*/)
{
object result = heap[0].Item;
//weight = heap[0].Priority;
count--;
trickleDown(0, heap[count]);
return result;
}

public void Enqueue(object item, BigInteger 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);
}
}