DEV Community

Paolo Ventura
Paolo Ventura

Posted on

100 algos in 100 days (Day 17)

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.


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];

sortScores(unsortedScores, HIGHEST_POSSIBLE_SCORE);
// returns [91, 89, 65, 53, 41, 37]
Enter fullscreen mode Exit fullscreen mode

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)