# 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"

## 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]