Remove a specific element from array

Let's write an algorithm to remove a specific element from the array.

Input

Array : {1, 20, 5, 78, 30}

Element : 78

Output

Array : {1, 20, 5, 30}

Input

Array : {1, 20, 5, 78, 30}

Element : 100

Output

Element Not Found

Algorithm

1. Find the given element in the given array and note the index.

2. If the element found,

Shift all the elements from index + 1 by 1 position to the left.

Reduce the array size by 1.

3. Otherwise, print "Element Not Found"

Visual Representation

Let's take an array of 5 elements.

1, 20, 5, 78, 30.

If we remove element 20 from the array, the execution will be,

1. We need to remove the element 20 (index 1) from the array.

2. Shift all the elements from index + 1 (index 2 to 4) by 1 position to the left.

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

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

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

3. Finally, the new array.

Implementation Algorithm

1. Set index value as -1 initially. i.e. index = -1

2. Get key value from the user which needs to be deleted.

3. Search and store the index of a given key

[index will be -1, if the given key is not present in the array]

4. if index not equal to -1

Shift all the elements from index + 1 by 1 position to the left.

5. else

print "Element Not Found"

Animated Tutorial

Implementation

Example

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

#include<stdio.h>

#define size 5

int main()
{
    int arr[size] = {1, 20, 5, 78, 30};
    int key, i, index = -1;

    printf("Enter element to delete\n");
    scanf("%d",&key);

    /*
     * iterate the array elements using loop
     * if any element matches the key, store the index
     */

    for(i = 0; i < size; i++)
    {
        if(arr[i] == key)
        {
            index = i;
            break;
        }
    }

    if(index != -1)
    {
        //shift all the element from index+1 by one position to the left
        for(i = index; i < size - 1; i++)
            arr[i] = arr[i+1];

        printf("New Array : ");
        for(i = 0; i < size - 1; i++)
            printf("%d ",arr[i]);
    }
    else
        printf("Element Not Found\n");

    return 0;
}

Time Complexity Analysis - Remove a specific element from an array

Worst Case - O(N)

If the element which needs to be deleted is present in arr[0], we need to shift all the elements from index 1 to size - 1 by position to the left.

So it will take N - 1 iteration. For example, if the array has 100 elements the for loop will work for 99 times.

Hence the time complexity will be O(N - 1). Polynomially, O(N). Where N is the number of elements in the array.

Best Case - O(1)

If the element present at the last index, then the below for loop will not work. (We won't shift any element.)

for(i = index; i < size - 1; i++)
    arr[i] = arr[i+1];

We just reduce the array size by 1.

It will take constant time. Hence the time complexity will be O(1).

Useful Resources

1. https://www.log2base2.com/C/array/arrays-in-c.html [Why do we need array?]
2. https://www.log2base2.com/C/array/declaration-and-initialization-of-array-in-c.html [Declaration and Initialization of array]