Duplicate index problem

Hi All,

I’m currently trying my hand at the PRACTICE interview questions on codesignal, but I’ve found myself unable to get my head around the final requirement, which is to do with computational complexity.

The problem can be summarised as follows:

  • For any array of length 1<= array.length >= 10^5, with values 1<= array[i] <= array.length
  • Find the lowest/smallest index of the second instance of a duplicate number

My solution is the following:

function firstDuplicate(a) {
    let indexes = []   
    
    a.forEach(element => {
        if (a.indexOf(element, a.indexOf(element) + 1) !== -1) {
            indexes.push(a.indexOf(element, a.indexOf(element) + 1));
        }
        
    })
    
    return indexes.length == 0 ? -1 : a[Math.min(...indexes)];
 
}

Now, this passes all the primary tests, but supposedly it is still too computationally inefficient. I’m really at a loss as to how to keep all of the above at O(1) processes, because cycling through the numbers or searching for a number is automatically at least a O(log n) process no?

Any advice, suggestions or recommendations are welcome!

Thank you,

Don

I don’t know how an O(1) solution would be possible - I assume it is not possible. A O(n) could be possible. What if you kept track of values as you encounter them? Then you’d know when you encounter something that is a duplicate, on the first pass.

How would that work? Do you mean:

  • creating a seperate copy of argument array
  • running a forEach
  • Storing the current element
  • Using shift() to remove said element
  • Using array.include(stored element) to check for duplicates?

I mean memoizing the data somehow, to keep track of the values you’ve encountered so far, something that is fast to access. You could do a hash table. You could do a simple array and toggle the index (that matches your number) to true. It could be an object where those are properties. It has to be something that can be accessed in O(1). I think some kind of hash solution would be best. You might even be able to do it in place. I don’t know, I’d have to think about it.

Do you have a link to the problem?

I’m sure there is an elegant solution out there. Maybe someone smarter than me will chime in with a better hint.

1 Like

Thanks for sharing your thoughts :slight_smile: It’s very hard to gauge what the requirements don’t the platform, so I’m not sure I’ve interpreted everything correctly; the link is below

https://app.codesignal.com/interview-practice/task/pMvymcahZ8dY4g75q/description

The problem is called the first duplicate problem, and this is one of the “hints” that was left for me:

You can choose to solve this problem without obeying the O(1) memory constraint. Once you have solved it, you will be able to look at other people’s solutions!

If you do want to solve it within the memory limit, the restrictions on the values a[i] are critical in this problem. Changing the array in place doesn’t require extra memory.

OK, so usually when people talk about complexity, they are talking about time complexity. That O(1) is talking about space complexity. There’s nothing wrong with that, I just misunderstood what was meant when you said O(1). So, if that is the space complexity, that means that you would want to do it in place. So, how do you encode into the original array if certain values have occurred already.

I seem to remember now doing one similar to this long ago. I think I remember how I solved this. Some clues:

  1. Note the instruction: “values 1<= array[i] <= array.length”.
  2. So, how does that affect the values? What could you say about the values? How could we use that to encode information in the already existing elements?

Yeah, this is kind of a tricky one. Coming up with a simple solution is fairly straightforward - but would use a lot of time or memory. And if I were in an interview and wasn’t 100% positive I could do better, I might do the “brute force” method quickly just so I have something. Then if I have time I would try for a “sexy” solution. But those often involve little tricks. This one does, if I remember correctly.

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.