Today I will look at more binary search questions updating this blog as I go!
I got confused halfway through so watched this video:
How to look for duplicates - space constraint
It gave a great tip. To save on space you can make an element negative (or flip in another way) in an array to show that you have seen that index.
Question:
Find the duplicated Integers
The integers are in the range 1...n
The array has a length of n+1
- First spot is that n = length -1 and is the highest possible value
- When you optimise this one for space you need to look for which half of the possible range has more numbers in it.
- Always when ceiling and floor converge then it is probably time to do something
Question 2 of the day:
Sort scores
const unsortedScores = [37, 89, 41, 65, 91, 53];
const HIGHEST_POSSIBLE_SCORE = 100;
sortScores(unsortedScores, HIGHEST_POSSIBLE_SCORE);
// returns [91, 89, 65, 53, 41, 37]
How can we do this quicker than O(n lg(n))
- First tip was to make an array with all of indexes 0...HighestPossible
- Then we add to a sorted array when there is a value in there
It seems to be all about building a toolkit of algos to solve any problem
Top comments (0)