Array Insertions And Shifting Algorithms

Introduction

Before reading this article about insertions and deletions, I recommend reading the "Introduction ToArray Data Structure".

You can skip reading the article below if you already know an array's strengths and weaknesses.

Introduction To Array Data Structure

In this article, we will dive deep into arrays introduction, array initialization, strengths, and weakness with complexity analysis. You will also see sketches, and snippets explaining in detail.

ggorantalaGopi Gorantala

Either way, I recommend brushing up on your basics; if you have one, it might fill some learning gaps!

Array Capacity and Length

Before working on inserting elements into the array. You need to understand what is arrays capacity vs arrays length.

If someone asks you how long an array is,

There could be two possible answers when discussing how long an array is.

1. How many items can an array hold, and
2. How many items currently an array has?

The first point is about capacity, and the second is about length.

Let us create an array A[10] whose capacity is10, but no items are added. Technically we can say the length is 0.

Capacity:

The capacity of an array in Java can be checked by looking at the value of its length attribute. This is done using the code A.lengthwhere A the Array's name is.

public class ArrayCapacityLength {
    public static void main(String[] args) {
        int[] A = new int[10];

        System.out.println("Array Capacity " + A.length); // 10
    }
}

Length

This is the number of items currently in the A[] array.

import java.util.Arrays;

public class ArrayCapacityLength {
    public static void main(String[] args) {
        int[] A = new int[10];

        int currentItemsLength = 0;
        for (int i = 0; i < 4; i++) {
            currentItemsLength += 1;
            A[i] = i + 10;
        }

        System.out.println(Arrays.toString(A)); // [10, 11, 12, 13, 0, 0, 0, 0, 0, 0]
        System.out.println("Array length is " + currentItemsLength); // 4
        System.out.println("Array Capacity is " + A.length); // 10
    }
}

Running the above snippet gives

Array length is 4
Array Capacity is 10

Array Insertions

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 an index in the array, it takes O(1) time.

You see how we insert an element in the array and shift the elements to the right.

In the following sample sketch, we have 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?

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.

The following explains how we insert values in an array. Let us dive deep into insertion algorithms.

Insert the element at the end of the array

Consider an array A[] that has 5 elements. To access the last element of the array, we use A[4].

With this knowledge, if N is the array length, then (N-1) is how we access the last element.

Example

Consider an array whose length is 5. The array looks like this -

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

Run the above snippet, and you will see all array values are defaulted to 0.

We use a variable currentLength to track the current items inserted in it. 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:

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

import java.util.Arrays;

public class ArrayIntroduction {
    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)); // [10, 11, 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;
    }
}

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).

Insert at the Start/Middle of the array

Think of a scenario where our array is filled with values.

Example

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

The array capacity and length are both equal to 10.

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.

import java.util.Arrays;

public class ArrayInsertAtMiddle {

    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.
2. Space complexity: O(1).

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 get some ideas and tricks to solve coding questions at LeetCode, HackerRank, CodeChef, etc., to ace top tech companies like FAANG.