Member Avatar for myk45

Hello.

i was trying to solve this problem.

Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.

Well, what i did is, use an array called present, to flag the elements ie:

for (i = 0; i < N; i++) {
    if (!present[i]) {
       present[i] = 1;
    } else {
       /* duplicate */
}

Is there a better way of doing it?

  • 2 Contributors
  • 4 Replies
  • 115 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by myk45

Dani AI

Generated

Building on and : the present-array approach is fine when you can afford O(N) extra space. If the input values are guaranteed to be in 1..N and you can modify the array, two common O(N) time, O(1) extra-space techniques are usually better than auxiliary arrays.

The negation-mark method

  • Iterate the array and for each value x = abs(A[i]) inspect A[x-1]. If that slot is already negative then x is a duplicate; otherwise negate A[x-1] to mark it seen. This is O(N) time, O(1) extra space. Restore the array afterward by running a pass that takes absolute values. See a worked description here: Find duplicates in O(n) time and constant extra space.

Index-placement (swap) method

  • Repeatedly put each element v into position v-1 by swapping. If the target position already contains v, you found a duplicate. This also runs in O(N) time and uses no extra array, and it naturally lists all duplicates if you keep scanning. It requires that values are in 1..N and the array be mutable; guard against out-of-range entries.

If the array must remain read-only and you want O(1) extra space, and there is exactly one duplicate, Floyds cycle-finding (tortoise-and-hare) can locate a duplicate without modifying the data. That technique and its limits are described here: Floyds Tortoise and Hare (cycle detection).

Choice guidance: use negation or swapping when memory is tight and mutation is allowed; use a hash set for simplicity and O(N) expected time if extra memory is acceptable; use sorting if in-place modification is permitted and O(N log N) time is fine. Always validate input (no zeros or out-of-range values) before applying the in-place tricks, and remember to restore the array if the original order must be preserved.

Recommended Answers

All 4 Replies

Member Avatar for Adak

That's a great way to do it, (called "Counting Sort", sometimes), IF the range of the numbers, is not too large.

Run time is O(n), and you can't beat that, as long as the range is suitable.

Member Avatar for myk45

Thanks for the reply Adak. But what if the number is huge? What way can i solve that?

Member Avatar for Adak

It depends on the data. If there were a lot of values < say 1000, and lots of values > 1 Million, with nothing in between, then it might make sense to have two arrays for Counting sort to work through. One for low and one for higher values.

Another way to do it - very common, is to simply sort the values. Now all the duplicate values will be right next to each other, and easily removed.

There are a wide variety of tricks with other data structures that can do the same thing. I haven't used them, but hash tables are one such. If the number hashes out to the same value, it will get tested for equality.

The general purpose being to get rid of any duplicate values, as far "upstream" in your processing of the data, as possible.

I'm always reminded of an old R:Base Relational Database, that SO EASILY would duplicate every record in the table you were working in. That was one of the first BASIC programs I wrote for work - remove duplicate records from our table in R:Base. (quite an adventure on a 286 cpu) ;)

Member Avatar for myk45

Thanks. The second method of sorting which you suggested was good too.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.