Array Insertions And Shifting Algorithm

Introduction

The array insertion and shifting algorithm in Java is a fundamental technique used to insert an element into an array at a specific position while efficiently shifting the existing elements to accommodate the new addition.

This algorithm is essential for dynamically modifying the contents of an array and maintaining its integrity.

By leveraging this algorithm, developers can handle array insertions with ease, ensuring optimal performance and maintaining the order of elements.

In this article, we will explore the implementation of the array insertion and shifting algorithm in Java, providing a step-by-step guide and a code example that demonstrates how to seamlessly incorporate new elements into an array at desired positions.

Insertion algorithms

Inserting an element at the start/middle of an array falls under array weaknesses, which might impact the performance if we are dealing with a massive array of elements as we need to shift the rest of the elements, which takes O(N) time unless we add new values at the end of the array, taking O(1) time.  

Note: If we are to just update the value at any(start/middle/end) index in the array, it takes O(1) time.

For example, consider an array of Characters { A, B, D, E, F } with indexes ranging from 0 to 4, and the length of the array being 5.

What happens if we insert a character C at index 2? or what happens we insert the character C at the last index?

We are inserting an element and not updating the index. Hence we need to shift the rest of the elements to make space for char C to insert it right index. Let us see both algorithms in practice.

Insert item at the end

As explained in introduction to array data structure lesson, when we declare an array, we are just creating an array that contains all zeros.

// array of elements with capacity as 5
int[] values = new int[5];

All array values are defaulted to 0.

Let us use a variable currentLength to track the current items inserted in the array. Where currentLength points to the array's next index at any given time.

We use a simple snippet to insert elements into the array. We have inserted a value 200 at the end of the array(array length).

Sketch

The sketch looks like this:

Code

Enough talk. Here is a simple algorithm that creates an array with a size 5, and inserts 100, 101 values into the array. Finally, we insert an element at the array length.

import java.util.Arrays;

public class ArrayAppends {
  public static void main(String[] args) {
    int[] A = new int[5];
    int currentLength = 0;

    // Let us add 2 elements to the array
    for (int i = 0; i < 2; i++) {
      A[i] = i + 100;
      currentLength++; // when i=1, length is set to 2
    }

    System.out.println(Arrays.toString(A)); // [100, 101, 0, 0, 0]
    System.out.println("current array items length " + currentLength); // 2
    System.out.println("Array capacity " + A.length); // 5
    System.out.println(
        "Element insert at end "
            + Arrays.toString(insertAtEnd(A, currentLength))); // [100, 101, 200, 0, 0]
  }

  // Inserting element at the end
  public static int[] insertAtEnd(int[] A, int currentLength) {
    A[currentLength] = 200;
    return A;
  }
}

/* 
Outputs:
[100, 101, 0, 0, 0]
current array items length 2
Array capacity 5
Element insert at end [100, 101, 200, 0, 0]
*/

You have seen adding elements at the end of an array. Let us see how we refactor our previous algorithm to insert values at the start or the middle.

Complexity Analysis

1. Time complexity: O(1), as we insert the value at the end.
2. Space complexity: O(1), no extra space is occupied other than the input memory.

Insert at the Start/Middle of the array

Think of a scenario where our array is filled with values. And we want to insert an item(not update) at the start/middle of the array.

Example

For example, consider an array A[10] that has elements {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} stored in it and the array is full.

The array capacity/length and size, both equal to 10. (array capacity is calculated using A.length, but the items inserted in the array is how size is calculated).

At any given index less than the size of the array. If we want to insert data, we must first shift all the elements from that index to the right and then insert this new data.

Sketch

Code

import java.util.Arrays;

public class ArrayInsertsAtEnd {

  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int insertValue = 100;
    int insertAtIndex = 5;
    int i;

    System.out.println(Arrays.toString(values)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    for (i = values.length - 2; i >= insertAtIndex; i--) {
      values[i + 1] = values[i];
    }

    values[insertAtIndex] = insertValue;

    System.out.println(Arrays.toString(values)); // [1, 2, 3, 4, 5, 100, 6, 7, 8, 9]
  }
}

Complexity Analysis

1. Time complexity: O(N), as we shifted elements from the insert position to the right. Worst case, we insert an element at the zeorth index, and we shift all elements to right, this is the reason we consider the time as O(N).
2. Space complexity: O(1), no extra space is occupied other than the input memory.

Conclusion

We discussed array capacity vs length and learned about inserting an element into the array at the start, middle, and end. We also learned how to shift array elements to make space for the new item to be inserted.

I hope these learning and examples on shifting algorithms help you gain some ideas and tricks to solve coding questions at LeetCode, HackerRank, CodeChef, etc., to ace top tech companies like FAANG.