Insert an element at a particular index in an array

Insert a given element at a specific position in an array.



Input

int arr[5] = {10, 20, 30, 40, 50}

Element = 100 position = 2.

Output

{10, 20, 100, 30, 40, 50}

Input

int arr[5] = {10, 20, 30, 40, 50}

Element = 100 index = -1 or 10.

Output

"Invalid Position"



Algorithm

1. Get the element value which needs to be inserted.

2. Get the position value.

3. Check whether the position value is valid or not.

4. If it is valid,

     Shift all the elements from the last index to position index by 1 position to the right.

     insert the new element in arr[position]

5. Otherwise,

     Invalid Position



Visual Representation

Let's take an array of 5 integers.

1, 20, 5, 78, 30.

If we need to insert an element 100 at position 2, the execution will be,

Insert element in array

1. We need to insert element 100 at position 2.

2. Move all the elements from the last index(4) to the position(2) to one position right.

arr[4] (30) will be placed in arr[5].

arr[3] (78) will be placed in arr[4].

arr[2] (5) will be placed in arr[3].

3. Finally, the element 100 is placed at the position 2.


Animated Tutorial



Implementation

/*
 * Program  : Inserting an element in the array
 * Language : C
 */

#include<stdio.h>

#define size 5

int main()
{
    int arr[size] = {1, 20, 5, 78, 30};
    int element, pos, i;

    printf("Enter position and element\n");
    scanf("%d%d",&pos,&element);

    if(pos <= size && pos >= 0)
    {
        //shift all the elements from the last index to pos by 1 position to right
        for(i = size; i > pos; i--)
            arr[i] = arr[i-1];

        //insert element at the given position
        arr[pos] = element;

        /*
         * print the new array
         * the new array size will be size+1(actual size+new element)
         * so, use i <= size in for loop
         */
        for(i = 0; i <= size; i++)
            printf("%d ", arr[i]);
    }
    else
        printf("Invalid Position\n");

    return 0;
  }



Time Complexity Analysis - Insert an element at a particular index in an array

Worst Case - O(N)

If we want to insert an element to index 0, then we need to shift all the elements to right.

For example, if we have 5 elements in the array and need to insert an element in arr[0], we need to shift all those 5 elements one position to the right.

In general, if we have n elements we need to shift all n elements.

So, worst case time complexity will be O(n). where n = number of elements in the array.

Best Case - O(1)

If the position value equals to size, then the below for loop will not work as the pos == size.

for(i = size; i > pos; i--)
      arr[i] = arr[i-1];

We can directly place the element in arr[size].

So, best case time complexity will be O(1).

O(1) indicates that the insertion operation is not depended on the size of the array. Whatever the array size it will always take constant time.