There are some important inefficient elements in the posted implementation.
Inserting into a sorted array
To insert Alice's next score into the array of sorted scores,
the posted appends Alice's score at the end and then sorts the array.
What's the typical time complexity of sorting an array?
\$O(n \log n)\$
Is it possible to do better?
When you have a list of sorted values, you can use binary search to find the position to insert a value so that the list stays sorted.
The general idea of binary search goes something like this: pick the middle position m
of the array. Is it bigger than the value? Then pick the middle position between 0 and m
. Or else if the value was smaller, then pick the middle between m
and the end of the array. Follow the same logic, in each step dividing the interval to check by 2, quickly converging on the target position.
What would be the time complexity to find that position using binary search?
\$O(\log n)\$
That's a lot faster than \$O(n \log n)\$.
By the way, since Alice's score only increases,
the range of values to search for the correct position shrinks,
so the fast solution just keeps getting faster for finding the higher scores.
By the way, once you found the right position, do you actually need to insert into the array?
No, in this particular challenge, you could just overwrite the position with the new value.
Why is that even a question, why not just insert the value and be done with it?
Inserting a value into an array typically requires copying the values that come after the insertion position, which is expensive. Depending on the programming language and how arrays work, a reallocation of the entire array (copying all elements) may also happen, which is even more expensive.
And keep in mind that we have to do this m
times, where m
is the number of scores of Alice.
What is the overall time complexity of the solution with sorting?
\$O(m n \log n)\$
What is the overall time complexity when we replace sorting with binary search? (Without shrinking the search range, to keep the theory simple.)
\$O(m \log n)\$
If we take into account the shrinking of the search range, then we can achieve a performance faster than \$O(m + n)\$.
Processing the two lists together
An alternative linear time solution is possible if we process the two lists together:
- Compute the ranks of the leaderboard (see the next section of my answer)
- Iterate over the scores of Alice, in increasing order
- From the end of the leaderboard, find the next score that is greater than or equal to Alice's current score
- If that score is equal to Alice's, then Alice's rank is the same as of that score
- Otherwise (the score is greater than Alice's), Alice's rank is 1 + the rank of that score
- Repeat for all scores of Alice. Note that when looking for the next leaderboard score, you can continue from the position of the last one found, do not restart from the end
This algorithm visits all elements of the two arrays once, performing a constant number of operations for each. What is the overall time complexity?
\$O(m + n)\$
This is not as good as using binary search that can skip many leaderboard scores at once, but probably fast enough for this exercise, and simpler to implement.
Computing the rank
The current implementation recomputes the ranks up until Alice's position for every single position.
That's unnecessary.
You could compute the ranks just once up front, and store in an array.
Then, once you know Alice's position, you could use the index of that position to find the rank directly.
Style
It's recommended to declare variables right before you need them.
For example i
and rank
are declared too early,
when they are only used after the sorting step.
The reason to delay declaration as much as possible is to reduce the possibility of mistakes: a variable is not defined yet, a use by mistake is likely going to crash badly and so you discover the problem early.
Otherwise it may get overlooked.
A common convention to improve readability is to add spaces around operators, after commas, before (
and after )
, for example:
function ladder(arr1, arr2) {
while (arr2.length) {
let i = 0