2

I've been doing tons of programming challenges and have lately encountered this problem: how to delete a value from an array and then shrink the array? I know how to tackle the problem by using the Arraylist and its methods but I'd like to know how to do the problem from scratch by using the basic array with fixed size. I'd really appreaciate if smb explains the solution elaborately.

public static int[] shrinkArray(int key)
{
    int[] resultArray = new int[myArray.length];
    for(int i = 0; i < myArray.length; i++)
    {
        if(myArray[i] == key)
           break;
    }

 return resultArray;
}
6
  • 4
    You can look at the source code of the ArrayList class to have an idea. Commented Jun 15, 2015 at 21:58
  • You cannot resize a Java array; you can only change the reference to point to a differently sized array. Commented Jun 15, 2015 at 22:01
  • @AlexisC., I already solved the problem using Arraylist but I'd like to know how to solve the problem with a basic fixed-sized array :) Commented Jun 15, 2015 at 22:07
  • 2
    @John I never said that you should use an ArrayList, I suggested that you look at the source code of the class to see how the remove method is implemented. Commented Jun 15, 2015 at 22:09
  • Do you want to remove all occurences of key or only first one? Commented Jun 15, 2015 at 22:32

4 Answers 4

2

You almost have it.

public static int[] shrinkArray(int key)
{
    int[] resultArray = new int[myArray.length-1]; //One length less as we removed an item
    boolean found = false;
    for(int i = 0, j = 0; i < myArray.length; i++, j++)
    {
        if(!found && myArray[i] == key){ //if we find item first time
            i++;                        //skip it
            found = true;               //we found first occurrence
        }
        if(j < resultArray.length)
            resultArray[j] = myArray[i]; //copy array
    }
    if(found)
        return resultArray;
    return myArray;  //not found
}
Sign up to request clarification or add additional context in comments.

4 Comments

It is wrong in case of key not found or key found many times.
i and j in if (i == j) is out of scope. When myArray = [1, 2, 2, 2, 3] and key = 2 then resultArray = [1, 3, 0, 0].
int j = 0 -> j = 0. , j < resultArray.length -> && j < resultArray.length.
You are like my very own compiler ^_^ Thanks again. (I should really compile it myself, but at work my options are limited.)
1

Perhaps converting your array to an arraylist then using the remove() method of the arraylist class would work. Then you could take said arraylist and convert it back to an array. Both conversions could work with a for-loop.

Another option would be to take an array. Find the index of the value you want to remove. Then make a for loop starting at that index that shifts all of the values to the right of that index then puts those values one index to the left.

Comments

0

Here is re sizable array that will change capacity on remove and add operations (when capacity is reached). Did not test this much but looks okay.

public class ArrayBackedIndexedCollection {

    private int size;
    private int capacity;
    private Object[] elements;

    public ArrayBackedIndexedCollection(){      

        this.capacity = 1;
        this.elements = new Object[capacity];
    }

    public ArrayBackedIndexedCollection(int initalCapacity){

        /***************************************************
         if initial capacity is less then 1 -> throw
         exception
         **************************************************/
        this.capacity = initalCapacity;
        this.elements = new Object[initalCapacity];

    }


    public int size(){

        return size;
    }

    public void add(Object object){

        // if capacity is reached
        if ( size == capacity){


            Object[] tmp = new Object[capacity];
            // backup current array
            System.arraycopy(elements, 0, tmp, 0, elements.length);

           // re size to double capacity 
            elements = new Object [2*capacity];

           // copy backup into re sized elements array
            System.arraycopy(tmp, 0, elements, 0, tmp.length);

            capacity = 2 * capacity;

        }

        this.elements[size] = object;
        size++;
    }

    public Object get(int index){

        return this.elements[index];    
    }

    public void remove(int index){

        elements[index] = null;
        size --;

        System.arraycopy(elements, index, elements, index + 1, size() - index);

    }

    public void insert(Object value, int position){

        //...
    }

}

Comments

0

Once you have created an array object in java you cannot resize it. If you want an array of different size you will have to create a new array and then populate it from scratch.

As you can imagine this is very inefficient and performance heavy. You are better off using an ArrayList or LinkedList. As a general rule you should favour collections over arrays, but if you're just looking to solve the challenge here's how I'd do it:

public static int[] shrinkArray(int keyToRemove, int[] arrayToRemoveFrom){
    int[] resultArray = new int[arrayToRemoveFrom.length - 1];//new array is one smaller
    boolean itemRemoved = false;
    for(int i = 0, j = 0; i < resultArray.length; i++, j++){
        if(!itemRemoved && arrayToRemoveFrom[i] == keyToRemove){
            itemRemoved = true;//boolean so you only get in here once
            i--;//decrease i for result array so you done leave a blank space 
        }else{
            resultArray[i] = arrayToRemoveFrom[j];
        }
    }
    return resultArray;
}

5 Comments

Variable j is undefined and unchanged.
Should have been i - Thanks! :)
IndexOutOfBoundsException will be thrown.
Indeed, this does not work (exception as well as creating a blank spot in new array)
Sorry yeah you're right. I should test these things first! I've fixed it now. Thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.