Array Insertions And Shifting Algorithm
In this lesson, you will learn about an array of insertion and shifting algorithms with illustrations and code examples.

Table of Contents
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
- Time complexity:
O(1)
, as we insert the value at the end. - 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
- 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 asO(N)
. - 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.
Gopi Gorantala Newsletter
Join the newsletter to receive the latest updates in your inbox.