all right this is what i've been
training for i'm not going to let senpai
down
what do we have here find duplicate
number
given an array nums containing n plus 1
integers where each integer is between 1
and n
inclusive prove that at least one
duplicate number must exist
of course because of the pigeonhole
principle
child's play assume that there is only
one duplicate number but it could be
repeated more than once
find the duplicate number
[Music]
i got it if the numbers are sorted then
any duplicate numbers will be adjacent
in the sorted array
a simple sort and a linear scan would do
[Music]
as expected i knew it couldn't be that
easy
but if you think that would stop me then
you underestimated me
i have no choice but to use my secret
weapon
[Music]
the famous hashmap one of the most
powerful data structures for reducing
your time complexity
taking advantage of its constant lookup
times however
using a hashmap requires me to increase
my power level
so i need to wear these to suppress and
control my powers in case it gets out of
control
also my doctor told me to wear them to
treat my carpal tunnel
honey wait
this question is too short
i'm too weak
[Music]
i'm running out of ideas i can't solve
this medium problem
how can i even be a real engineer how am
i gonna get into google
seems like you need some help
[Music]
this question is trivial oh my god he's
so cool
and his jacket is so big solving this in
linear time in constant space
requires floyd's tortoise and hair a
simple cycle detection algorithm
where one pointer traverses twice as
fast as 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 nodes in our case
because each number is from 1 to n then
each value 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 it
yourself senior engineers don't code
anymore
also my doctor said not to because of my
carpal tunnel
that works senpai why are you so smart
because of my gangsters