Just No more free questions left!
Upgrade NowFind a duplicate, Space Edition™ BEAST MODE
In Find a duplicate, Space Edition™, we were given a list of integers where:
These properties mean the list must have at least 1 duplicate. Our challenge was to find a duplicate number, while optimizing for space. We used a divide and conquer approach, iteratively cutting the list in half to find a duplicate integer in time and space (sort of a modified binary search).
But we can actually do better. We can find a duplicate integer in time while keeping our space cost at .
This is a tricky one to derive (unless you have a strong background in graph theory), so we'll get you started:
Imagine each item in the list as a node in a linked list. In any linked list, each node has a value and a "next" pointer. In this case:
Here’s a full example:
Notice we're using "positions" and not "indices." For this problem, we'll use the word "position" to mean something like "index," but different: indices start at 0, while positions start at 1. More rigorously: position = index + 1.
Using this, find a duplicate integer in time while keeping our space cost at .
Drawing pictures will help a lot with this one. Grab some paper and pencil (or a whiteboard, if you have one).
We don’t need any new data structures. Your final space cost must be .
We can do this without destroying the input.
We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.
We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.
time and space.
Our space cost is because all of our additional variables are integers, which each take constant space.
For our runtime, we iterate over the array a constant number of times, and each iteration takes time in its worst case. So we traverse the linked list more than once, but it's still a constant number of times—about 3.
We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.