Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

Just 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:

  1. the integers are in the range 1..n
  2. the array has a length of n+1

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:

  • The value is the integer from the array.
  • The "next" pointer points to the value-eth node in the list (numbered starting from 1). For example, if our value was 3, the "next" node would be the third node.

Here’s a full example:

An array [2, 3, 1, 3], so 2 is in the first position and points to 3 in the second position.

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.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

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.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

What's next?

Powered by qualified.io

. . .