Press "Enter" to skip to content

How to Find Duplicate Number From Continuous Array

Ajk 0

How to Find Duplicate Number From Continuous Array? I got asked this very question a long time ago at an on-site interview. It is supposed to be one of the easier questions, but I can see how certain nuances of it can become hard.

First off, as always let us start with some clarifications:

How to Find Duplicate Number From Continuous Array – Assumptions

  • What is meant by a continuous array? In this problem’s context a continuous array is one that contains all numbers from 1 to N.
  • Are we given the number of elements of the array? Since the problem mentions that we have a duplicate. then the array has N + 1 elements.
  • Is the array sorted? We have no information about this, so we assume that the array is unsorted.

Given that we have all assumptions resolved, we can try to think about a brute force solution. Should be pretty trivial:

How to Find Duplicate Number From Continuous Array – Brute Force Algorithm

  • For each number from 1 to N.
  • Go through the array and check if it contains more than 1 of this number.

Obviously, the above algorithm, would perform quite poorly as N would get larger. Indeed, its time complexity would be O(N2). So let us try to optimize and find a better solution.

The usual approach to trying to optimize, is to use a hash table, so why don’t we try to use such a data structure. The idea is to put all elements in a HashMap and check which one of them gets put twice. Since getting and setting keys on a hash table is practically O(1), we should be able to come up with an O(N) solution to our problem.

How to Find Duplicate Number From Continuous Array – HashMap Algorithm

  • For each element in the array.
  • If the element does not exist as a key in the HashMap. Add it as a key in a HashMap.
  • If the element exists as a key in the HashMap, then we found our value.

Take-home question: What are the pros and cons of using a HashMap vs a HashSet.

Looks like a pretty easy solution does it not? By introducing a HashMap, the time complexity was reduced to O(N) as expected. However our space complexity, went from O(1) in our brute-force solution, to O(N).

This looks good and probably is the best solution in a world where computers have multi GB of memory. But, in an interview setting that might not matter. Your interviewer might ask for a solution where the space complexity is constant (O(1)) and yet it performs better than our brute force solution.

Our other, go to solution should be sorting. In fact sorting the array would take O(N*log(N)) time and then checking the array for a duplicate would be a trivial O(N) operation. Space complexity would also probably be constant O(1), since sorting can mostly be done in place.

Our interviewer has a nitpick though. He wants us to implement such a solution (that would take O(N*log(N) time and O(1) space), without us actually modifying the input array. This is quite an interesting problem, that we could use some kind of binary search to solve. In fact as interesting as it is, I will leave this final version on how to find duplicate number from a continuous array on you!

Take-home question: Implement a solution that will take O(N*log(N)) time and O(1) space, without modifying the input array.

Hope you guys enjoyed it! And I’ll see you guys next time!

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂