How to Remove an Element from an Array in Java?

Hello guys, In the last article, you have learned how to reverse an array in place in Java and today I have come back with another array based coding interview question. It's also one of the frequently asked coding questions, not as popular as the previous one but still has been asked a lot of times on various Programming Job interviews, particularly to beginners. In this problem, you are asked to write a program to remove a given number from the given array. It may seem easy but the trick is that because an array is a fixed data structure and you cannot change the length of the array once created. So, you need to clarify with the Interviewer, what is the meaning of removing an element from the array here. Does he want to return an array without that element or just set that index to a null or empty string?

If he wants to return a new array without that element then the length of the array will be changed, which means you have to create and return a new array, which is not easy, particularly if you don't know how to copy elements from one array to another array. 

Anyway, before solving the problem let's see the problem statement first.

Problem: Given an array and a value, write a function to remove all instances of that value from the array in Java (in place) and return the new length, or simply print out the array before and after removing the number.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

For example, if the given array is {12, 122, 12, 13, 14, 23, 14}, and number to be removed is 12 then the result array should be {122, 13, 34, 23,14}, and the length of the new array is 5.

Btw, if you are not familiar with the array data structure itself then  I suggest you to first go through a comprehensive course on data structure like Data Structures and Algorithms: Deep Dive Using Java on Udemy to get an understanding of basic data structures like an array, linked list, binary tree, hash tables, and binary search tree. That will help you a lot in solving coding problems like this in real Programming Job interviews.




How to Remove a value from an array in Java

In this article, I am going to show you two ways to remove a number from an integer array in Java. Our first solution will use the LinkedList class of Java Collection framework and the second solution will do it without using the collection framework, as per the algorithm described incoming section.

2 ways to remove an element from array in Java



Solution 1- Using LinkedList or another Array

In this solution, we have used a LinkedList class to collect all non-matching elements. So, I scan through the original array and keep adding elements which are not equal to target value into LinkedList.

Once I have completed the scan, I have all the numbers without target value in LinkedList. Later I use the Apache Commons ArrayUtils class to convert this LinkedList into an array in Java.

There you go, you have removed the target number from the array without a fuss.

The only problem with this approach is that you need an extra LinkedList to hold rest of values and you now have your code dependent on Apache commons library, which is not that bad.

If LinkedList is not an option then you can also use another array and just follow the rest of the steps. I mean loop through the initial array and copy to a new array, which is one element smaller than the original array.

When you reach the target element just skip it and continue with the next element.  Now, you have another array which is without the target element, in other words, you have removed the element you wanted to.  Just return this array and you are done.

The time and space complexity of this solution is O(n) because you need to scan through the array and copy that into the linked list while removing and you need a linked list of the same size as the array, albeit one less node to hold the elements.

If you don't know how to calculate time and space complexity or understand the Big O notation of algorithms complexity then I suggest you go through a fundamental algorithm course like Algorithms and Data Structures - Part 1 and 2 on Pluralsight,  to learn these basics.

It's important to know the Big O notation while working through Algorithms and it's even more important from technical whiteboard interview perspective where Interviewer will force you to reduce time and space complexity and find a faster and better solution.

How to Remove a number from an Array in Java?



Solution 2 - Without the Java Collection Framework. 

Once you solve this problem easily using Java Collection framework, the Interview will definitely ask you to solve this problem without using Java Collection framework or using any in-built library functions.  In that case, you can use this approach, in fact,

The most straightforward way to remove a value from an array is to loop through the whole array, from the beginning to end. When the target value (number) is found, remove it and move all numbers behind it backward.

The overall time complexity of this algorithm is quadratic i.e. O(n^2) since we have to move O(n) numbers when a target number is removed, which is worse than the previous solution but this is more like an in-place algorithm as you don't need to create another array or list to copy elements.

As I have told you before, in this kind of coding problem there is always a time and space tradeoff. If you want to improve time by reducing time complexity, you need to use extra space and if you don't have the luxury of additional space then more likely time complexity will increase.

Anwya, if you are going for a coding interview, I suggest you refresh all these concepts before your interview and if you need a resource a course like Data Structures in Java: An Interview Refresher on Educative is perfect, which covers all most all the topics you need to prepare for coding interviews.

How to remove a number from Array in Java?





Java Program to Delete an Element from the Array


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import org.apache.commons.lang.ArrayUtils;
import org.apache.commons.lang.StringUtils;

/**
 * Sample Program to show how to remove elements from array in Java.
 * In this program, we have used two ways, first by using LinkedList
 
 * class of Java Collection framework and second without using 
 * Collection framework. 
 *
 * @author javinpaul
 */
public class RemoveNumberFromArray {

    public static void main(String args[]) {

        System.out.println("Test #1 : General case to remove number  22");
        int[] input = {42, 322, 22, 11, 22, 33, 16};
        System.out.println("input : " + Arrays.toString(input) + ", remove 22");
        int[] output = remove(input, 22); // removes number 22 from array
        System.out.println("output : " + Arrays.toString(output));

        System.out.println("Test #2 : Remove number from empty array");
        int[] empty = {}; //empty array
        output = remove(empty, 23);
        System.out.println("input : " + Arrays.toString(empty) + ", remove 23");
        System.out.println("output : " + Arrays.toString(output));

        System.out.println("Test #3 : Remove number from array, without target number");
        int[] withoutTarget = {1, 2, 3, 4, 5, 6}; //empty array
        output = remove(withoutTarget, 12);
        System.out.println("input : " + Arrays.toString(withoutTarget) + ", remove 12");
        System.out.println("output : " + Arrays.toString(output));

        System.out.println("Test #4 : Delete element from array with only target numbers");
        int[] allWithTarget = {1, 1, 1, 1, 1, 1, 1};
        output = remove(allWithTarget, 1);
        System.out.println("input : " + Arrays.toString(allWithTarget) + ", remove 1");
        System.out.println("output : " + Arrays.toString(output));
    }


    /*
     * Removing a number from integer array with the help of LinkedList class
     */
    public static int[] removeNumber(int[] input, int number) {
        List<Integer> result = new LinkedList<Integer>();
        for (int item : input) {
            if (item != number) {
                result.add(item);
            }
        }
        return ArrayUtils.toPrimitive(result.toArray(new Integer[]{}));
    }


    /*
     * Removing element from array without using Collection class
     */
    public static int[] remove(int[] numbers, int target) {
        int count = 0;
        
        // loop over array to count number of target values.
        // this required to calculate length of new array
        for (int number: numbers) {
            if (number == target) {
                count++;
            }
        }

        // if original array doesn't contain number to removed
        // return same array
        if (count == 0) {
            return numbers;
        }

        int[] result = new int[numbers.length - count];
        int index = 0;
        for (int value : numbers) {
            if (value != target) {
                result[index] = value;
                index++;
            }
        }
        numbers = null; // make original array eligible for GC 
                return result;
    }
}

Output:
Test #1 : General case to remove number  22
input : [42, 322, 22, 11, 22, 33, 16], remove 22
output : [42, 322, 11, 33, 16]

Test #2 :  Remove number from empty array
input : [], remove 23
output : []

Test #3 : Remove number from array, without target number
input : [1, 2, 3, 4, 5, 6], remove 12
output : [1, 2, 3, 4, 5, 6]

Test #4 : Delete element from array with only target numbers
input : [1, 1, 1, 1, 1, 1, 1], remove 1
output : []


From the output, it's clear that our solution is working as expected. When we tested with an array where we have multiple target numbers it worked fine. We have also tested our solution with an empty array, an array which doesn't contain the value to be removed and an array containing the only value to be removed.

It worked fine in all these scenarios. You can also create JUnit tests to capture each of these conditions and let me know if you still found any bug or typo in the code. Another interesting problem or variant which is based on this concept is about removing duplicates from an array. If you understand this algorithm you can easily solve that problem as well.


That's all about how to remove numbers from an array in Java. You have now learned two ways to delete an element from an array in Java. Though we have seen the example of removing the number from a numeric array, the algorithm is generic and will work with all types of the array-like array with strings or array with objects. You just need to create separate methods to accept different types of array-like method to remove an element from a long array or float array or String array.


Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java: An Interview Refresher
Cracking the Coding Interview - 189 Questions with Solutions


Other Array related coding Interview Questions for practice:
  • 10 Algorithms Books Every Programmer should read [books]
  • How to find all pairs in an array whose sum is equal to k (solution)
  • How to rotate a given array in Java? (solution)
  • How to check if an array contains a particular value? (solution)
  • How to find the largest and smallest number in an array without sorting? (solution)
  • How to find duplicates from an unsorted array in Java? (solution)
  • How to find one missing number in a sorted array? (solution)
  • How to remove duplicates from an array in Java? (solution)
  • How to find the missing number from a given array in Java? (solution)
  • 30+ Array-based Coding Problems from Interviews (questions)
  • 10 Free Data Structure and Algorithms Courses for Programmers [courses]
  • Write a program to find the missing number in integer array of 1 to 100? [solution]
  • 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
  • How do you reverse an array in place in Java? [solution]
  • 10 Algorithms courses to Crack Coding Interviews [courses]

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy.

1 comment:

  1. Hi Javin,
    I guess It can be solved O(n).
    Please check below solution.

    -----------CODE----------------
    public class DeleteAnyElementFromArray {

    public static void main(String[] args) {
    // TODO Auto-generated method stub
    Integer[] ar = {12,3,5,1,12,6,9,12,15,-8,-1,12,-6,-3,5,7};
    int len = ar.length;
    System.out.println(len);
    int keyToDel =12;
    int j =0; //keeping J to count the freq of the item to be deleted
    int i=0;
    for(;i<len;i++){//O(n)
    if(ar[i] != keyToDel){
    ar[i-j] = ar[i];//I'm keeping the running index in check by reducing
    } //the increment index by the freq of the item to be deleted
    else
    j++; //increment when the element is "item to be deleted"
    }
    for(int k = i-j+1;k<i;k++){//O(n)
    ar[k] =null; //this loop shall perform worst when all the elements are same and they all have to be deleted
    }
    for (int k =0 ;k<i-j;k++){ //printing till the
    System.out.print(ar[k]+",");
    }
    }

    }

    ReplyDelete