Array Insertions and Shifting Algorithm

Array Insertions and Shifting Algorithm
Array Insertions and Shifting Algorithm

Array insertions, inserting an element in an array at the start or middle might impact the performance if we are dealing with a massive array of elements unless we add new values at the end of array.

If you are new to arrays, we recommend you read What is an Array? and come back here to learn more on array operations. Let us see how we insert an element in the array and shift the elements to the right.

In the following example sketch, we have an array of Character’s { A, B, D, E, F } with indexes ranging from 0 to 4, and the length of the array being 5.

Let us try to insert a Character C at index 2, before inserting we need to understand how to shift the elements from index 2 to the right so we make space for the Character C to fit in atindex 2.

Let us run through the below algorithms to understand both shifting and removing elements. This could help you with problem-solving and when you try to solve coding questions at LeetCode, HackerRank, HackerEarth, etc to ace top tech companies like FAANG.

Array Insertions

Inserting an element in an array at the start or middle might impact the performance if we are dealing with a massive array of elements.

1. Inserting At End

We know that the last index of the array whoaw length N is N-1.

Let us first create an array with size 5.

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

We then use a variable called length to track the current items inserted in it, where length points to the next index of the array at any given point of time.

Let us insert items into the array using a for-loop, and increment the length variable to insert values at a given index at any point of time inside loop. In below code we inserted values 10, 11 into the array.

Here is a simple algorithm that creates an array with size 5, and inserts 10, 11 values into the array.

import java.util.Arrays;

public class ArrayExample {
  public static void main(String[] args) {
    int[] values = new int[5];
    int length = 0;

    // Let us add 2 elements to the array
    for (int i = 0; i < 2; i++) {
      values[i] = i + 10;
      length++; // when i=1, length is set to 2
    }
    
    System.out.println(Arrays.toString(values)); // [10, 11, 0, 0, 0]
    System.out.println(length); // 2
  }
}

Run the above snippet and you will see that the first two values inserted into the array and the rest are defaulted to 0.

Now we can insert the value 100 by calling the length variable we created above.

values[length] = 100; // we are inserting 100 at index 2

Following is the simple algorithm that inserts new value at the 2nd index.

import java.util.Arrays;

public class ArrayExample {
  public static void main(String[] args) {
    int[] values = new int[5];
    int length = 0;

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

    values[length] = 100; // we are inserting 100

    System.out.println(Arrays.toString(values)); // [10, 11, 100, 0, 0]
    System.out.println(length); // 2
  }
}

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

2. Inserting at Start or Middle

Think of a scenario, where we have our array filled with values in it.

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

Consider the following example problem, we have to insert value 100 at index 5.

Input: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, insertValue = 100, insertAtIndex = 5
Output: [1, 2, 3, 4, 5, 100, 6, 7, 8, 9, 10]
import java.util.Arrays;

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

    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, 10]
  }
}

Try to understand the above algorithm, this might help you solve some of the problems in the real coding interview.