5

I have an array containing names of items. I want to give the user the option to create items without specifying their name, so my program will have to supply a unique default name, like "Item 1".

The challenge is that the name has to be unique so i have to check all the array for that default name, and if there is an item with the same name i have to change the name to be "Item 2" and so on until i find an available name.

The obvious solution will be something like that:

String name = "Item ";
for (int i = 0; !isAvailable(name + i) ; i++);

My problem with that algorithm is that it runs at O(N^2).

I wonder if there is a known (or new) more efficient algorithm to solve this case.

In other words my question is this: Is there any algorithm that finds the first greater-than-zero number that dose NOT exist in a given array, and runs at less that N^2?

1
  • Does the name just have to be unique, or does it specifically have to be the first available string in the sequence "Item 1", "Item 2", etc? You can greatly decrease expected runtime by choosing a new name at random ("Item xF3g7a"). You also might improve on an array for the data structure: if the ordering isn't important don't use an array, and if it is important perhaps keep a secondary index of names as well as the array. Jan 14, 2011 at 21:51

7 Answers 7

4

You can certainly do it in O(N) time, N being the number of items in your array:

  • One of "Item 1", "Item 2", ... "Item N+1" must be free, so create an array of N+1 flags.
  • Traverse the items, and for each name if it is of form "Item k" with 0 < k <= N+1, set that flag.
  • Scan the flag array for the first clear flag.

Additional memory requirement is N+1 bits, which certainly beats any data structure that actually stores all N names.

16
  • I also considered this, but this assumes that the numbers in the items are small enough to be used as index in a vector. If there is an item called "Item 123456789132456789" then your array will be huge. On the other hand, if the value is that big you are probably not interested in it anyway.
    – Patrick
    Jan 14, 2011 at 21:57
  • @Patrick: the flag array will only be that huge if there are 123456789132456788 items in the item array. If there are only 4 items in the array, and one of them happens to be called "Item 123456789132456789", that doesn't matter because my flag array occupies only 5 bits. "Item 123456789132456789", is not a candidate for the least unused name any more than "Fred", so I need not record seeing either. A requirement for N+1 bits of memory is annoying, but in practice rarely difficult to satisfy since it's such a very small percentage of the space already occupied by the items themselves. Jan 14, 2011 at 22:01
  • @Steve I think you can do it with just N flags. If they are all set then N+1 must be available. Jan 14, 2011 at 22:07
  • @David: agreed. Mind you, if that makes the code any larger due to the additional special case, we might lose our hard-won bit straight away :-) Jan 14, 2011 at 22:10
  • So now we are going to impose a linear cost, growing as the number of items grows, on every item insertion? For the little benefit it gives you, this seems like a hell of a cost, especially if the list gets long. Jan 14, 2011 at 22:18
3

Yes, there is.

First sort the array. Then run through it and return the first element whose value is not equal to its index (plus 1). The sort is O(n log n), the final step is O(n), so the entire thing is O(n log n).

If you put all items into a hash table, you can do it in O(n) at the cost of some space and an additional O(1) step at creation of new items. Since each element needs to be visited, O(n) is clearly optimal.

I'd be interested to see if there's an O(n) way to do this, without using any "persistent" data structure like the hash table. (And assuming unbounded integers, otherwise a bucket sort could be used as an O(n) sorting algorithm).

4
  • And then I saw Steve's solution which is better! Jan 14, 2011 at 22:10
  • Thanks Thomas, Great answer! in fact, i thought of something very similar but i had a missing piece that you just put in place. Even though i'm writing my program for iPhone - so i'll probably use your algorithm because it uses less memory than Steve's algorithm, I'm accepting Steve's answer here because his solution is more efficient. Jan 14, 2011 at 22:19
  • "First sort the array" - for an optimization, you could first partition the array into names of form "Item k", and names of other forms. Then only sort the first part. This assuming that it's OK to destroy the original ordering of the items - sorting a copy of the array would take more memory than my answer. Jan 14, 2011 at 22:43
  • @Thomas: I think your hash table solution would be really good is the OP maintains the names of the items given out in a hash table from the very start, and not in an array. Then he would not be using any extra space Jan 10, 2012 at 19:53
1

Why not just keep track of the maximum number to date, and when you need a new one, increment it?

8
  • 1
    Then if you have Item1, Item2 and Item8 you will add Item9. But the user probably wants Item3 re-used. Jan 14, 2011 at 21:51
  • Could be, but "defragmenting" the items may not make sense and/or may not be required. If not, this is a O(1) algorithm in both runtime and space. Jan 14, 2011 at 22:11
  • Also, if "defragmenting" is required, it could be done lazily and only at the end of the item sequence. For example, once item[max-1] is no longer in use, you can reset max to max-1. Jan 14, 2011 at 22:15
  • @Emery but what if item[max-2] gets removed first, and then item[max-1]? Jan 14, 2011 at 22:22
  • @David - Exactly my line of reasoning Jan 14, 2011 at 22:26
1

Insert all of the existing names into a hash table. Repeat your loop, but make isAvailable check the hash table. Assuming a decent hash, it's O(nh) where h is the cost of evaluating the hash.

1

You could try to do the following:

first:

  • loop through the list, and get all numbered items, this is complexity N
  • for every numbered item, put the item in a tree (in C++: std::map), this is complexity log(N)

So now you have built up a map with the used numbers, with complexity "N x log(N)"

Next, iterate to the tree and as soon you see a 'hole', use the number. Worst case is complexity N.

So in total, the complexity is N x log(N) + N, or simplified: N log(N).

0

If there will be only one user accessing this array, why not use the number of nanoseconds? This, of course, assumes that the user is much slower than a computer, which seems to be a safe assumption.

That way, you have a O(1) cost for determining a unique name.

2
  • Wouldn't "item"+nanoseconds fulfill that requirement? Jan 14, 2011 at 23:23
  • it's unique, but it's not the first available name of the specified format. Jan 14, 2011 at 23:54
0

A logarithmic-time approach, assuming that you never leave "holes" by deleting items:

// Inverse binary search for the last one.
int upperBound = 1;
while(isInUse(upperBound)) upperBound *= 2;

// Standard binary search for the end once we have a ballpark.
int lowerBound = upperBound / 2;
while(lowerBound < upperBound - 1)
{
    int midpoint = (lowerBound + upperBound) / 2;
    if (isInUse(midpoint))
        lowerBound = midpoint;
    else
        upperBound = midpoint;
}
return upperBound;

If item numbers can be freed by deleting, nothing short of linear search will work unless you also keep a "free list" and pick from that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.