Just [[currentUser.getNumFreeQuestionsLeft()]] No more free questions left!Upgrade Now
Find a duplicate, Space Edition™ BEAST MODE
In Find a duplicate, Space Edition™, we were given an array of integers where:
These properties mean the array 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 array 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 array 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.
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.