## usaar33

BAN USERI suspect this is impossible under strict definitions of O(1) space. There exist no sorting algorithms with worst-case parameters of O(n) time and O(1) space. Any solution to this problem would allow you to do a linear time, constant space counting sort where the range_of_numbers <= length of array. If you could do that, you should publish a paper.

As noted in comments I've made on other answers (e.g. storing negative numbers or a number larger than len(N) in an element), all solutions thus far provided stretch the definition of O(1) space and in the general sense are O(N).

While very clever, this is an O(n) space algorithm. You are relying on the fact that every integer has a free sign bit. In the general case, this is not true - the algorithm fails for instance with an array of 255 unsigned bytes. While this solution is quite valid in the case of a signed integer array, I feel standard complexity analysis labels it O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.

- usaar33 July 31, 2013While very clever, this is an O(n) space algorithm. You are assuming you have additional free bits to add N in which may not be true. Standard complexity analysis would show this as O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.

- usaar33 July 31, 2013@varun, etc: While very clever, this is an O(n) space algorithm. You are relying on the fact that every integer has a free sign bit. In the general case, this is not true - the algorithm fails for instance with an array of 255 unsigned bytes. While this solution is quite valid in the case of a signed integer array, I feel standard complexity analysis labels it O(n); you need to "allocate" one bit per element as a flag for stating if the corresponding element is a count or input data.

- usaar33 July 31, 2013

Rep**thelmasaraht**, Applications Developer at Accolite softwareA child protection social worker is responsible for a variety of services designed to help families and children in a ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

@xuzheng:

- usaar33 July 31, 2013To show that your algorithm (as a general algorithm) is O(n) space, let's use a simple counter-example. Java's a little weird in that you don't have unsigned types, so let's use C.

void elements(unsigned char * A) {

...

//Issue #1

A[i] = -1;

//Issue #2

A[A[i] - 1]--;

Let's say A has 255 elements; the domain for input numbers is 1-255. The issue #X lines both are problematic. You are going to underflow, as a negative is outside the domain. The subtraction creates a large positive number indistinguishable from your original input data -- causing the algorithm to fail.

This isn't so obvious if you use Java, as all integers in Java are signed. In this particular language, you just happen to have that an extra bit of unused space in each element in the input array which you can use for your purposes. But this is not true in general (as in the C example given above).

You cannot rely on such the input array being inefficiently stored. If it is efficiently stored (e.g. as an unsigned type), you must allocate N new bits to store that "count or input" flag.. making it an O(N) space algorithm.