Count frequencies of all elements in array in O(1) extra space and O(n) time

Question

Problem Description: I found this problem in my Algorithms Assignment . It wants me to find the frequencies of all the elements of an array in O(n) time and O(1) space.

Array Can be anything like Ar[]={1,6,3,78,4,6,1}

After Thinking a little bit i came up with this approach:

1. Iterating the array and finding the max element.( O(n) time)
2. Creating a new array of the size= max element ( O(1) space)
3. Iterating over the original array and storing the frequencies at the indices of the new array (O(n) time).

I have a doubt regarding step 2. After finding the max element(say m) in Step 1 i am making a new array of size m. does thing array occupies O(1) space ? if not please explain

Answer 1

Yes you are right finding the maximum number and then creating a hash array of that length is not a solution of O(1) space complexity as O(1) space complexity refers to a constant space usage but if you are declaring the size of array based on your input values only then how can the space be a constant. Constant Space or O(1) complexity means an approach which does not take into account the input values instead is independent of the inputs. So therefore your this approach is not correct for the solution. Hope , I have made myself clear. But if you want the solution to your problem it can be found here Geeks for Geeks It gives a good explanation of your problem.

Answer 2

Without any assumptions about your input, there is no way to do this in O(n) time and O(1) space

• To have O(1) space means that you can fix the amount of space to be allocated before-hand. Meaning that it is constant (and thus non-dependent on your base array)
• If you can limit the input to a certain set, this becomes possible. Some examples are
  • When you're given a char array containing the ASCII charset, then you can fix your space to an array of 128 integers. You then iterate over your input and increment the numbers in arr[charCode(currentChar)]
  • An array of positive intergers. You can create an array of integers of size Integer.MAX_VALUE which is 2^32 - 1. Then apply the same logic as before.

Answer 3

I think doing this in O(1) space and O(n) time is going to be difficult unless you can make some assumptions, as some of the other answers have suggested. I don't think allocating an array of length MAXINT is really the right choice.

An answer in O(number of unique values) space and O(n) is far easier. Use a hash where the key is the value from the array and the hash-value is the count. You'll have one pass through your data, and then you have a hash with the complete counts.

HashMap<Integer,Integer> map.= new HashMap<Integer,Integer>();
for (int value: array) {
   Integer valueI = new Integer(value);
   if (!map.hasKey(valueI)) {
       Integer count = new Integer(1);
       map.put(valueI, count);
   }
   else {
       Integer oldCount = map.get(valueI);
       Integer newCount = new Integer(oldCount.intValue() + 1);
       map.put(valueI, count);
   }
}

Something like that. Your map's keys holds the unique values and the value of for each key maps that count.

I can't come up with anything you can do in O(1) space without making huge assumptions on the data, or allocating a really huge array. After all, you have to store the results somewhere.