I am looking for the simple apperence array problem. For example if we have:

int arr[10] = {7,3,3,3,100,1000, 4, 8, 9, 6}

We want to return the occurence of every element like

• 7 > 1
• 3 > 3
• 100 > 1
• 1000 > 1
• 4 > 1
• 8 > 1
• 9 > 1
• 6 > 1

I am looking for the naive algortihm by creating a new arr with length equals to the max then increment in the index of the new arr while traversing the original array.

I know it's very naive algorithm, but i am looking here for the space comlexity.

In this case what is the space complexity? For example if the max number in the original array is 1000 we will create in the memory another array with size = 1000 so it's not O(n).