Wednesday, September 29, 2021

How to remove a number from an Integer Array in Java? [Example Tutorial]

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 the 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 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? Example

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 the Java Collection framework, and the second solution will do it without using the collection framework, as per the algorithm described in the 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 that are not equal to the 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 the rest of the values, and you now have your code dependent on the 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 that 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 a technical whiteboard interview perspective where the 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 the Java Collection framework, the Interview will definitely ask you to solve this problem without using the 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 the 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 your 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.

Anyway, 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

Here is our complete Java program to remove an element from a given array in Java. The program demonstrates how to remove numbers from an int array in Java but the method can be used with any array, for example, array of primitive values or an array of objects like an array of strings. 
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 that 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 bugs or typos 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 array-like arrays with strings or an array with objects. You just need to create separate methods to accept different types of array-like methods to remove an element from a long array or float array or String array.


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 find duplicates from an unsorted array in Java? (solution)
  • How to find one missing number in a sorted array? (solution)
  • 10 Free Data Structure and Algorithms Courses for Programmers [courses]
  • How to find the missing number in an integer array of 1 to 100? [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)
  • 50+ Data Structure and Algorithms Coding Problems  (questions)
  • How do you reverse an array in place 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? (solution)
  • 10 Algorithms courses to Crack Coding Interviews [courses]

Thanks for reading this article so far. If you like this Java coding problem and solution, then please share it 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 these free Data Structure and Algorithms Courses from Udemy and other websites. 

5 comments:

  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
  2. Hi, if you hae int set {0,1,2,3,4,5,6,7,8,9} and you want to remove the second[2] number. then update the int set to {0,1,3,4,5,6,7,8,9} and then again remove the second[2] number(3) to get to the int set {0,1,4,5,6,7,8,9}. how do you do that?

    ReplyDelete
    Replies
    1. there is no direct way to remove elements from array than creating another array and copying the remaining elements, so you need to just copy elements which are not removed.

      Delete
  3. Hello sir why you used LinkedList to add the
    non matching elements in array

    ReplyDelete
    Replies
    1. Hello Raju, because adding and removing element from linked list is O(1) operation and they also don't need to allocate memory in advance like array which will required re-allocation if we have large array.

      Delete

Feel free to comment, ask questions if you have any doubt.