Placeholder Image

Subtitles section Play video

  • All right, This is what I've been training for.

  • I'm not gonna let send pie down.

  • What do we have here?

  • Find duplicate number given an array numbs containing end plus one integers where each integer is between one and end inclusive proved that at least one duplicate number must exist.

  • Of course, because of the pigeonhole principle, Child's play assumed that there is only one duplicate number, but it could be repeated more than once.

  • Find a duplicate number.

  • I got it.

  • If the numbers are sorted than any duplicate numbers will be a Jason in this sordid array.

  • A simple sort and the linear scan would do as expected.

  • I knew it couldn't be that easy, but you think that would stop me then You underestimated me.

  • I have no choice but to use my secret weapon Hash Famous hash map.

  • One of the most powerful data structures for reducing your time complexity, taking advantage of its constant look of times.

  • However, using a Hashmat requires me to increase my power level.

  • So I need to wear these to suppress control my powers in case it gets out of control.

  • Also, my doctor told me to wear them to treat my carpal tunnel.

  • Wait, oh, expressions to show.

  • Too weak.

  • I'm running out of ideas.

  • I can't solve this.

  • Me and roll can even be real engineer homemaking against Google, it seems like you need some help.

  • This question is trivial.

  • Oh my God, he's so cool and jackets so big.

  • Solving this in linear time and constant space requires Floyd's Tortoise and Hare, a simple cycle detection algorithm where one point to traverse is twice as fast is another.

  • And once they meet, you can trace back to the point where the cycle began.

  • In our case, the values of the array is like a pointer pointing to Indices of the array, which is like notes in our case, because each number is from one to end, then each valley will have to point to a valid index.

  • And since there's a duplicate number, there will be a cycle.

  • Find that cycle and you will have your answer.

  • What are you waiting for?

  • Call yourself senior engineers on coding.

  • More also, my doctor said not to because of my carpal tunnel.

  • They're worse.

All right, This is what I've been training for.

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it