How do you reorganize an array within O(n) runtime & O(1) space complexity?

Question

I'm a 'space-complexity' neophyte and was given a problem.

Suppose I have an array of arbitrary integers:
[1,0,4,2,1,0,5]

How would I reorder this array to have all the zeros at one end:
[1,4,2,1,5,0,0]

...and compute the count of non-zero integers (in this case: 5)?

... in O(n) runtime with O(1) space complexity?

I'm not good at this.
My background is more environmental engineering than computer science so I normally think in the abstract.

I thought I could do a sort, then count the non-zero integers.
Then I thought I could merely do a element-per-element copy as I re-arrange the array.
Then I thought something like a bubble sort, switching neighboring elements till I reached the end with the zeroes.
I thought I could save on the 'space-complexity' via shift array-members' addresses, being that the array point points to the array, with offsets to its members.

I either enhance the runtime at the expense of the space complexity or vice versa.

What's the solution?

Answer 1

Two-pointer approach will solve this task and keep within the time and memory constraints.

Start by placing one pointer at the end, another at the start of the array. Then decrement the end pointer until you see the first non-zero element.

Now the main loop:

• If the start pointer points to zero, swap it with the value pointed by the end pointer; then decrement the end pointer.
• Always increment the start pointer.
• Finish when start pointer becomes greater than or equal to the end pointer.

Finally, return the position of the start pointer - that's the number of nonzero elements.

Answer 2

This is the Swift code for the smart answer provided by @kfx

func putZeroesToLeft(inout nums: [Int]) {
    guard var firstNonZeroIndex: Int = (nums.enumerate().filter { $0.element != 0 }).first?.index else { return }

    for index in firstNonZeroIndex..<nums.count {
        if nums[index] == 0 {
            swap(&nums[firstNonZeroIndex], &nums[index])
            firstNonZeroIndex += 1
        }
    }
}

Time complexity

There are 2 simple (not nested) loops repeated max n times (where n is the length of input array). So time is O(n).

Space complexity

Beside the input array we only use the firstAvailableSlot int var. So the space is definitely a constant: O(1).

Answer 3

1. Start with iterating over the array (say, i) and maintaining count of zeros encountered (say zero_count) till now.
2. Do not increment the iterative counter when the current element is 0. Instead increment zero_count.
3. Copy the value in i + zero_count index to the current index i.
4. Terminate the loop when i + zero_count is greater than array length.
5. Set the remaining array elements to 0.

Pseudo code:

zero_count = 0;
i = 0;
while i + zero_count < arr.length 
  if (arr[i] == 0) {
    zero_count++;
    if (i + zero_count < arr.length)
      arr[i] = arr[i+zero_count]
  } else {
    i++;
  }

while i < arr.length
  arr[i] = 0;
  i++;

Additionally, this also preserves the order of non-zero elements in the array,

Answer 4

As indicated by the other answers, the idea is to have two pointers, p and q, one pointing at the end of the array (specifically at the first nonzero entry from behind) and the other pointing at the beginning of the array. Scan the array with q, each time you hit a 0, swap elements pointed to by p and q, increment p and decrement q (specifically, make it point to the next nonzero entry from behind); iterate as long as p < q.

In C++, you could do something like this:

void rearrange(std::vector<int>& v) {
    int p = 0, q = v.size()-1;
    // make q point to the right position
    while (q >= 0 && !v[q]) --q;
    while (p < q) {
        if (!v[p]) { // found a zero element
            std::swap(v[p], v[q]);
            while (q >= 0 && !v[q]) --q; // make q point to the right position
        }
        ++p;
    }
}

Answer 5

Start at the far end of the array and work backwards. First scan until you hit a nonzero (if any). Keep track of the location of this nonzero. Keep scanning. Whenever you encounter a zero -- swap. Otherwise increase the count of nonzeros.

A Python implementation:

def consolidateAndCount(nums):
    count = 0
    #first locate last nonzero
    i = len(nums)-1
    while nums[i] == 0:
        i -=1
        if i < 0:
            #no nonzeros encountered
            return 0
    count = 1 #since a nonzero was encountered
    for j in range(i-1,-1,-1):
        if nums[j] == 0:
            #move to end
            nums[j], nums[i] = nums[i],nums[j] #swap is constant space
            i -=1
        else:
            count += 1
    return count

For example:

>>> nums = [1,0,4,2,1,0,5]
>>> consolidateAndCount(nums)
5
>>> nums
[1, 5, 4, 2, 1, 0, 0]

Answer 6

The suggested answers with 2 pointers and swapping are changing the order of non-zero array elements which is in conflict with the example provided. (Although he doesn't name that restriction explicitly, so maybe it is irrelevant)

Instead, go through the list from left to right and keep track of the number of 0s encountered so far.

Set counter = 0 (zeros encountered so far).

In each step, do the following:

1. Check if the current element is 0 or not.
   1. If the current element is 0, increment the counter.
   2. Otherwise, move the current element by counter to the left.
2. Go to the next element.

When you reach the end of the list, overwrite the values from array[end-counter] to the end of the array with 0s. The number of non-zero integers is the size of the array minus the counted zeros.

This algorithm has O(n) time complexity as we go at most twice through the whole array (array of all 0s; we could modify the update scheme a little to only go through at most exactly once though). It only uses an additional variable for counting which satisfies the O(1) space constraint.

Answer 7

You can actually solve a more generic problem called the Dutch national flag problem, which is used to in Quicksort. It partitions an array into 3 parts according to a given mid value. First, place all numbers less than mid, then all numbers equal to mid and then all numbers greater than mid.

Then you can pick the mid value as infinity and treat 0 as infinity.

The pseudocode given by the above link:

procedure three-way-partition(A : array of values, mid : value):
    i ← 0
    j ← 0
    n ← size of A - 1

    while j ≤ n:
        if A[j] < mid:
            swap A[i] and A[j]
            i ← i + 1
            j ← j + 1
        else if A[j] > mid:
            swap A[j] and A[n]
            n ← n - 1
        else:
            j ← j + 1