0

That's not a question, but rather an aggregation post.

So the problem is: how can I achieve O(1) space and O(n) time complexity operating some value-type item (usually integers or chars) list, if I am to find n-times-appearing elements, sort the list or find all unique values?

One little note. This applies only to value-type objects with fixed ranges of values (e.g. integers, chars and so on).

UPDATE

There were lots of questions about using such an approach to achieve O(1) space and O(n) time complexity when sorting or searching for elements that appear k-times, or even number of times, or unique elements or so. So, please read the question carefully, especially the first statement. It's a FAQ-style post, not a question.

Also, I know the answer, no need to post it again and again. If you feel you can add something valuable - feel free to edit the question and the longest answer in the topic (note it's my own answer), so it become a community wiki.

Related questions:

  1. Finding the first non-repeated character of a string in O(n) using a boolean array?
  2. Find a single integer that occurs with even frequency in a given array of ints when all others occur odd with frequency
  3. Find if 2 strings are anagram in O(1) space and O(n) time
  4. Finding duplicates in O(n) time and O(1) space
  5. Find duplicates in an array
  6. O(n) algorithm to find out the element appearing more than n/2 times
Community
  • 1
  • 1
J0HN
  • 26,063
  • 5
  • 54
  • 85
  • I don't think I understand this question at all. Maybe you should split it up after all. For example, how do you expect to use arrays in O(1) space? Also you can't really sort arrays in less than O(n log n) time (althouigh Radix sort sort of can). – Adrian Ratnapala Jan 20 '12 at 10:52
  • @AdrianRatnapala, see the answer below. – J0HN Jan 20 '12 at 10:53
  • @J0HN I'd appreciate if can you add an example so I can better understand the question ? – brainydexter Jan 20 '12 at 15:37
  • If you want your answer to be a community wiki, there is a checkbox you can check. Since its too late for that, you could flag it and ask a moderator to. Also, it sounds like you're trying to make a "canonical question"; please reword appropriately if so. http://meta.stackexchange.com/q/104877 and http://meta.stackexchange.com/q/63762 and http://meta.stackexchange.com/q/62695 – derobert Jan 20 '12 at 20:17
  • You say two times in your post that *"this is not a question"*. Don't be surprised when five people agree, and this gets closed as such. – Andrew Barber Jan 20 '12 at 23:28
  • Actually I'm not surprised at all. Missed that "community wiki" checkbox at all, my fault. @derobert, thanks for pointing me out to how this sort of thing s should be done. – J0HN Jan 22 '12 at 10:58

3 Answers3

2

If you use the slightly sneaky argument that the number of unique values of each item is fixed then you can have a hash-map for each unique value that is O(1) space.

Now the answer to your question is trivial. Just go through the list once and accumulate the number of occurrences in the hash-map. O(n) time.

Note, to answer the question as posed, there's no need for sorting.

Tim Gee
  • 1,062
  • 7
  • 9
1

The basic idea is that O(1) space complexity in fact means that memory consumption is independent of the size of the array.

So if elements of the array you are operating have limited range (e.g. -128..127) you are able allocate a hash-like array of length max_value-min_value+1 to keep track of the number of appearances of each value (let's call it count-array for now).

Using such an approach you scan the array only once (hence O(n) time complexity), accumulate the number of appearances of each individual value and in the end you can answer the questions:

  1. Are there elements with odd/even number of appearances? Only one appearance? Arbitrary number of appearances? (just scan the count-array)
  2. What are the unique values that appear in the initial array (pick all keys that have value > 1 in count-array)
  3. Sort an array (a bit more complicated, see examples below)

And finally, some code samples on Python

import random, sys
min_val = -5
max_val = 5
initial_array = [random.randint(min_val, max_val) for i in range (0,20)]
count_array = {i:0 for i in range(min_val,max_val+1)}

for elem in initial_array:
    count_array[elem]+=1

#print initial_array

#1. Find unique values
unique_values = [item for item, count in count_array.iteritems() if count>0]
#print unique_values

#2. Find n-time-appearing values
n=2
n_times_appear = [item for item, count in count_array.iteritems() if count==n]
#print n_times_appear

#3. Find odd times appearing numbers
odd_times_appear = [item for item, count in count_array.iteritems() if not count%2]
#print odd_times_appear

#4. Sort an array
#We don't actually sort an array - we just reconstruct it.
sorted_array = []
for item,count in sorted(count_array.iteritems()):
    for i in range(0,count):
        sorted_array.append(item)

#print sorted_array

Feel free to add other languages implementations as well as correct me if I'm wrong :)

J0HN
  • 26,063
  • 5
  • 54
  • 85
  • To stretch the point even further, you can do a binary radix sort to sort any fixed-width integer type in `O(n)`, then scan through the result to do any of the other things you list. It's a bit weaselly, though. – Steve Jessop Jan 20 '12 at 11:17
  • +1 for a comprehensive answer. My only criticism would be that to answer the question (find elements that occur k times), there's no need for sorting. – Tim Gee Jan 20 '12 at 13:16
-1

Because input size is bounded, You can simply run Counting Sort algorithm on your inputs then find your result. Counting sort takes O(n), and finding specific elements of array has specific occurrence time is O(n) in sorted arrays.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83