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,


Remove an element from the array

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]


Topics You Might Like