Ranks of array elements with respect to lexicographic ordering

Question

I have an array A of length n containing strings of length 3. I want to build an array B where each string in A is replaced by its rank in A with respect to the lexicographic ordering. (Note that A can have duplicates, so B can also have duplicates.)

Assuming that the JavaScript A.sort() performs radix sort of A in time O(n), how can I build B in O(n) time from A?

Example: If A is

['abb', 'ada', 'bba', 'bba', 'dab', 'bad']

then B is

[1, 2, 4, 4, 5, 3]

(Note: You may assume that array assignments take constant time.)

• zw324: sort is implemented with radix sort in JavaScript? If so that's interesting, do you have some references?
• David Eisenstat: Can A have duplicates? If so, what should happen?
• James: Note that you cannot guarantee O(n) with Array#sort() in JS. We don't have control over what sorting algorithm a specific env uses either.
• David Eisenstat: Here's an O(sort(n))-time algorithm assuming that associative array ops are O(1)-time: copy A to an array A1. Sort A1. Scan A1 from beginning to end; whenever the element x in position j is not in the associative array Rank, insert Rank[x] = j. Make B by scanning through A doing lookups in Rank. I'd make this an answer if my Javascript weren't so rusty.
• David Eisenstat: @Randomblue With length-3 strings? Seems plausible to me as a practical assumption. I don't mean to start a holy war, but if you want more control, perhaps you should switch languages.

Answer 1

Here's the fastest thing I can think of...

function cheese(a){
 var b = [];
 var c = {};//hash references to make lookups really fast
 var d = [];//desired output
 for(var i = 0; i < a.length; i++)
 {
 if(!c[a[i]])
 b.push(a[i]);
 c[a[i]] = true;
 }
 b.sort();
 for(i = 0; i < b.length; i++)
 {
 c[b[i]] = i;
 }
 for(i = 0; i < a.length; i++)
 d.push(c[a[i]] + 1);
 return d;
}

• Reimius: Isn't your rewrite slower due to the use of forEach which would create a function scope for every iteration?

Answer 2

I'll try, but I don't feel very confident about:

• Sort algorithm consistency across browsers' implementations
• My solution could be simplified, and it's not extensively tested.

Anyway, it seems to give desired result so let's go:

Array.prototype.getLexicoGraphic = function() {
 var result = [], 
 sorted = this.slice(0).sort();
 for(var i = 0; i < sorted.length; i ++) {
 result[i] = sorted.indexOf(this[i]) - (i - sorted.indexOf(sorted[i])) + 1; 
 }
 return result;
}

• Randomblue: indexOf runs in O(n), so your algorithm runs in O(n^2).
• sixFingers: True. Answer's not easy :)
• sixFingers: Sorry for my ignorance on the topic, but I understand that n^x where x is the number of loops needed to return the final value. Is it correct?

Answer 3

var A = ['abb', 'ada', 'bba', 'bba', 'dab', 'bad'];
var B = [];
// Assuming slice(0) is O(n) 
var Ap = A.slice(0);
var H = [];
var N = A.length;
var i, index;
// O(n)
A.sort();
// O(n)
for (index = 1, i = 0; i < N; i++) {
 // Assuming that H[A[i]] is O(1)
 if (!H[A[i]]) { 
 H[A[i]] = index;
 index++;
 }
}
// O(n)
for (i = 0; i < N; i++) {
 B[i] = H[Ap[i]];
}
console.log(B);
// 4 * O(n) === O(n)

Answer 4

Construct secondary array, which will contain the value alongside with its original index - O(n).

[[0, 'abb'], [1, 'ada'], [2, 'bba'], [3, 'bba'], [4, 'dab'], [5, 'bad']] // Stored as 'foo' in the following examples

Sort the newly created array using comparator function - according to your assumption O(n) (but I doubt that).

foo.sort(function (a, b) { return a[1].localeCompare(b[1]); });

Iterate over the sorted array and create your rank array on the way - O(n).

var last = null, rank = 0, result = [], i;
for (i = 0; i < foo.length; i++) {
 result[foo[i][0]] = (last === null || last.localeCompare(foo[i][1]) != 0) ? ++rank : rank;
 last = foo[i][1];
}

Enjoy your result.

---

Update Another way how to do this is via associative array with indexes:

{ 'abb': [0], 'ada': [1], 'bba': [2, 3], 'dab': [4], 'bad': [5] }

Then you can create array of keys (hence unique values), sort it and construct your ranking based on that.

• Randomblue: Your first solution does not work. I get [1, 2, 3, 4, 4, 5] as result.
• Pavel Horal: I just used bad variable when constructing the result array. Now its fixed and working.

Answer 5

You can create an array of ordinals in O(n) time

var a = ...;
var ranks = [];
for (var i = 0; i < a.length; ++i) { ranks[i] = i; }

Then you can define a comparator that compares integers by comparing the indexed string

function cmp(i, j) {
 return a[i] < a[j] ? -1 : a[i] = a[j] ? 0 : 1;
}

Each comparison takes constant time since the strings are constant length.

Then perform your custom sort on ranks instead using cmp which you stipulated takes linear time. This will yield b.

If you need the sorted version of a, you can reconstruct it from a and ranks in linear time.

var aSorted = [];
for (var i = 0; i < a.length; ++i) {
 aSorted[i] = a[ranks[i]];
}