Move elements N steps to the left (challenge)

Question

Lets say we have this array:

{"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};

Then I already made a method to push elements to the left and leaving all the nulls at the right:

void pushFromLeftToLeft() {

  int nullCount = 0;

  for (int i = 0; i < BUCKET_CAPACITY; i++) {
      if (data[i] == null) {
        nullCount++;
      }
      else if (nullCount != 0) {
        data[i-nullCount] = data[i];
      }
  }
  // set the last elements to null 
  for (int i = BUCKET_CAPACITY - nullCount; i < BUCKET_CAPACITY; i++) {
     data[i] = null;  
  }

}

This results in:

{"a", "b", "c", "d", "f", "g", "i", "j", "k", "l", null, null, null};

I know it could be done more simple with making an array of the same size and looping over the original and assign to the new one at the current index if not null. However I choose for a bit more complexity so it's more efficient for really large array.

While this works great I had another idea. I have been trying to solve the algorithm but it's killing me. The idea follows:

We start with this array again:

{"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};

I want to add "m" and "o" add the end of the array. To do that I want to shift the elements to the left again to make room but only as many as required to make room. So we can stop once we have 2 nulls at the end resulting in:

{"a", "b", "c", "d", null, "f", "g", "i", "j", "k", "l", null, null};

Here comes the challenge:

• work from right to left
• move elements directly to the right place, so instead of moving "l" one to the left and then one more time one to the left we move it 2 indexes in 1 step.
• don't use a new array, only a buffer that is as small as possible
• (in short be efficient)

So far I have failed multiple attempts. Below is my latest which probably won't help much. I hope someone can help with this interesting challenge.

String[] data = new String[] {"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};
int BUCKET_CAPACITY = data.length;

void pushFromRightToLeft(int offset) {

  int currentOffset = offset; // if we find a null this decreases

  Object[] buffer = new Object[offset];

  {
    int bufferIndex1 = (BUCKET_CAPACITY-1) % buffer.length;
    buffer[bufferIndex1] = data[BUCKET_CAPACITY-1];
  }


  for (int i = BUCKET_CAPACITY-1; i >= offset; i--) {

    int bufferIndex1 = i % buffer.length;
    int bufferIndex2 = (i+1) % buffer.length;

    if (buffer[bufferIndex1] == null) {
      //nullCount++;
      currentOffset--;
      // what to do, we don't want to move the null forward...
      // move last buffered item into this place
      data[i] = (String) buffer[bufferIndex2];
    } 
    else {

      buffer[bufferIndex2] = data[i-currentOffset]; 
      data[i-currentOffset] = (String) buffer[bufferIndex1]; 

      if (currentOffset == 0) {
        println("break on: "+i);
        break;
      }

    }

  } 

}

(For this case, pushFromRightToLeft(1); pushFromRightToLeft(2); and pushFromRightToLeft(3); should work.)

Answer 1

You can go right to left, count nulls and when the wanted number of nulls is reached, go right again, moving the elements in place:

public static void moveNulls(Object[] arr, int howMany) {
    int offset = arr.length;
    int nullCount = 0;
    while(nullCount < howMany) {
        if(arr[--offset] == null)
            nullCount++;
        if(offset == 0 && nullCount < howMany)
            throw new IllegalStateException("Not enough nulls");
    }
    int target = offset;
    while(offset < arr.length) {
        if(arr[offset] != null)
            arr[target++]=arr[offset++];
        else
            offset++;
    }
    Arrays.fill(arr, target, offset, null);
}

This algorithm does not require additional memory. Usage:

for(int i=0; i<5; i++) {
    String[] arr = {"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};
    moveNulls(arr, i);
    System.out.println(Arrays.toString(arr));
}

Output:

[a, b, c, d, null, f, g, null, i, j, k, null, l]
[a, b, c, d, null, f, g, null, i, j, k, l, null]
[a, b, c, d, null, f, g, i, j, k, l, null, null]
[a, b, c, d, f, g, i, j, k, l, null, null, null]
Exception in thread "main" java.lang.IllegalStateException: Not enough nulls