Skip to content
Advertisement

Remove last occurrence of a specific integer from an array

For some reason, my solution is not complete. I got 80/100 from hidden spec tests.

  1. What’s wrong with my solution? There is probably a certain use case that I’m not thinking of.
  2. How would space/time complexity change using an ArrayList instead of an array?
  3. Is there a better way to tackle this problem?

My current solution handles:

  • an empty input array
  • negative/positive integer values in the input array
  • duplicates in the input array
  • sorted/unsorted input array

Instructions:

Write a Java method removeLastOccurrence(int x, int[] arr), which removes the last occurrence of a given integer element x from a given array of integer elements arr.

The method should return a new array containing all elements in the given array arr except for the last occurrence of element x. The remaining elements should appear in the same order in the input and the returned arrays.

The code on the right shows you a code framework in which the implementation of one static method is still missing. Provide this implementation and check that it is correct by either writing more tests yourself or using the provided tests and specification tests.

My code:

class RemoveLastOccurrenceArray {

    /**
     * Takes the array and the last occurring element x,
     * shifting the rest of the elements left. I.e.
     * [1, 4, 7, 9], with x=7 would result in:
     * [1, 4, 9].
     *
     * @param x   the entry to remove from the array
     * @param arr to remove an entry from
     * @return the updated array, without the last occurrence of x
     */
    public static int[] removeLastOccurrence(int x, int[] arr) {

        // if arr == null return null;
        if (arr == null || arr.length == 0) return arr;

        // return a new array which will be size arr.legnth-1
        int[] res = new int[arr.length - 1];

        // introduce an int tracker which keep tracks of the index of the last occurrence of x
        int last_index = -1;

        // traverse through the array to get the index of the last occurrence
        for (int i = 0; i < arr.length; i++) if (arr[i] == x) last_index = i;

        int i = 0, j = 0;

        // copying elements of array from the old one to the new one except last_index
        while (i < arr.length) {
            if (i == last_index) {
                if (i++ < res.length) {
                    res[j++] = arr[i++];
                }
            } else res[j++] = arr[i++];
        }

        // if we pass in x which is not in the array just return the original array
        if (last_index == -1) return arr;

        // are there duplicates in the array? - WORKS
        // does the array have negative numbers? - WORKS
        // Is the array sorted/unsorted - WORKS

        return res;
    }
}

Passing Unit Tests

import static org.junit.Assert.*;

import org.junit.*;

public class RemoveLastOccurrenceArrayTest {
    @Test
    public void testRemoveArray_Empty() {
        int[] array = new int[0];
        assertEquals(0, RemoveLastOccurrenceArray.removeLastOccurrence(5, array).length);
    }

    @Test
    public void testFirstSimple() {
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] result = {2, 3, 4, 5, 6, 7, 8, 9, 10};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(1, input));
    }

    @Test
    public void testLastSimple() {
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] result = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(10, input));
    }

    @Test
    public void testPositiveInMiddleDuplicate() {
        int[] input = {1, 2, 3, 3, 4, 5};
        int[] result = {1, 2, 3, 4, 5};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(3, input));
    }

    @Test
    public void testNegativeFirst() {
        int[] input = {-3, -1, 2, -3, 3, 4, 5, 0};
        int[] result = {-3, -1, 2, 3, 4, 5, 0};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(-3, input));
    }

    @Test
    public void testLasttoRemove() {
        int[] input = {1, 4, 7, 9};
        int[] result = {1, 4, 7};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(9, input));
    }
}

Advertisement

Answer

This is the answer thank you very much!

Also, if there is no x to find, yours crashes … mine doesn’t. Maybe that’s where the twenty marks went?

I was already checking for this but too late in my code. So I just had to move

if (last_index == -1) return arr; before the while loop, and I got 100/100 scores.

enter image description here


Would your prof prefer this? Just another way, and I don’t think any more efficient than your answer. But maybe they like to see the java classes used …

Does your prof not tell you where you lost marks? You can’t improve if they don’t tell you what they were expecting for full marks. But here was another way … again, no better in my opinion, and not worth twenty more marks. I’ll just post it, because it is ‘another way.’

    public int[] removeLastOccurrence2(int x, int[] arr) {

        // if arr == null return null;
        if (arr == null || arr.length == 0) return arr;

        // Fill an ArrayList with your initial array ...

        java.util.List list = new java.util.ArrayList(arr.length);

        for (int i=0; i<arr.length; i++) {
            list.add(arr[i]);
        }

        int[] res;

        // Now ... use ArrayList methods to do the work.

        // Also, if there is no x to find, yours crashes ... mine doesn't.
        // Maybe that's where the twenty marks went?

        if ( list.lastIndexOf(x) != -1 ) { // This screens for no x found at all ...

             list.remove( list.lastIndexOf(x) ); // Done!

             // Make a new array to return.
             res = new int[list.size()];
             for (int i=0; i<list.size(); i++) {
                 res[i] = (int) list.get(i);
             }

        } else {

            // No 'x' found, so just return the original array.
            res = arr;
        }        

       return res;
    }
User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement