Remove All Occurrences Of An Element From Array In c – Interview Question

Remove All Occurrences Of An Element From Array In c is a tutorial aimed at showing how to use two pointers in c programming.

Problem Statement

Given an array and a value, your task is to remove all the occurrence of the given value from the array and return the new length. You should solve the problem in-place.

You are not allocate extra space for another array, you are to do this by only by modifying the input array (i.e in place) with O(1) extra memory.

Example input 1

arr[] = {10,30,40,10,10}

value = 10

output: 2. This is because we are expected to remove every occurrence of 10 from the array; we will be left with only 30,40

Example input 2

arr[] = {4,9,6,9,8,9,9}

value = 9

output: 3. This is because we are expected to remove every occurrence of 9 from the array; we will be left with only 4,6,8

Hint

  • We can use two pointers to solve this problem; one pointer to iterate the array (call it i) and the other to point to the new array length (call it newLen), both pointers start from index 0;
  • Iterate the whole array one element at a time using pointer i and if each array index value is not equal to the given value, place that value in the newLen index and increment newLen index otherwise if the array index value is equal to the given value, just move pointer i to the next element and continue the process.

For our given input for example,

  • Get start value of pointer i index i.e 10
  • Compare the value of pointer i indext to the given value 10, value is same, move pointer i to next element and continue the process.
  • Get value of current pointer i index which now 30
  • Compare the value of current pointer i index with given value, value is not the same, retrieve the value of current pointer i index 30 and store it in the current pointer newLen index and increment newLen by 1; index 0 now holds the value 30 and pointer newLen now points to index 1
  • Continue the process until you have reached the last element of the array

The Confusion

So at the end of execution, the new array now looks like this

and you are wondering why array does not return just 30, 40 but rather 30, 40, 40, 10, 10. Well we are solving the problem in-place; we are not to allocate any new memory so we cannot create a new array to store only 30, 40.

But the hint in the given problem in leetcode suggest that it doesn’t matter what you leave beyond the new length and that the order of elements can be changed. Click on this link to see description of the problem statement in leetcode https://leetcode.com/problems/remove-element/

So since what we are asked to do in this particular problem statement is to return the new length of the array, we are just fine returning 2 and ignoring any other thing. Maybe if you have need to use this particular algorithm to return the new elements of the array 30, 40 instead; you find a way to delete all records from the newLegth Pointer and you will be left with elements minus the given value – in this case 30, 40 for input 1.

The Solution

This is code written in c but you can use same algorithm to write it in whatever language you choose to.

#include <stdio.h>

int removeElement(int *arr, int n, int val)
{
    int i, newlength = 0;
    
    for(i=0; i<n; i++)
        if(arr[i] != val)
            arr[newlength++] = arr[i];
            
    return newlength;
}

int main()
{
    int ary[6] = {10,30,40,10,10};
    int new_arry_length = removeElement(ary, 5, 10);
    printf("New lenght is: %d", new_arry_length);
}

OUTPUT

Also see more detailed output in leetcode though with a different input.

Time and Space Complexity Analysis

  • Time complexity is O(n); i.e the algorithm runs in linear time
  • Space complexity is O(1)

Conclusion

The two pointer technique algorithm used to remove all occurrences of an element from array using c programming is accepted by leetcode; please see status in attached image, and notice that the algorithm runs at 4ms second for the given input and is faster than 64% of other codes submitted in c for this particular problem statement and the memory usage is 5.9 MB which is 97.42% less than the memory other codes submitted for this problem used.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like