2

I'm trying to remove even-length words from a String ArrayList, and it's almost working, except that for some reason one even-numbered word is getting through.

My code:

public ArrayList<String> removeEvenLength(ArrayList<String> a) {
    for (int i = 0; i < a.size(); i++) {
      String wordEntry = a.get(i);
      if (wordEntry.length() % 2 == 0) {
        a.remove(i);
      }
    }
    return a;

I must be missing something, but I'm failing to determine what exactly. Pointers much appreciated.

Unmitigated
  • 76,500
  • 11
  • 62
  • 80

5 Answers5

4

The issue is that you are modifying the ArrayList while iterating over it, which changes its size. You need to decrease the index by one each time you remove an element since that index will now refer to the next element.

public static ArrayList < String > removeEvenLength(ArrayList < String > a) {
 for (int i = 0; i < a.size(); i++) {
  String wordEntry = a.get(i);
  if (wordEntry.length() % 2 == 0) {
   a.remove(i);
   i--;
  }
 }
 return a;
}

Looping backwards will also fix this problem, as elements will never be shifted to a position that you have yet to check.

public static ArrayList < String > removeEvenLength(ArrayList < String > a) {
 for (int i = a.size() - 1; i >= 0; i--) {
  String wordEntry = a.get(i);
  if (wordEntry.length() % 2 == 0) {
   a.remove(i);
  }
 }
 return a;
}

You can also use List#removeIf with Java 8 and up to accomplish this easier.

public static ArrayList < String > removeEvenLength(ArrayList < String > a) {
 a.removeIf(str -> str.length() % 2 == 0);//or str.length() & 1 == 0
 return a;
}

You can use Stream#filter to construct a new List with the odd-length Strings without modifying the old one.

public static ArrayList < String > removeEvenLength(ArrayList < String > a) {
 return a.stream().filter(str -> str.length() % 2 == 1).collect(Collectors.toCollection(ArrayList::new));
}
Unmitigated
  • 76,500
  • 11
  • 62
  • 80
  • 1
    Concerning the first of your solutions: I personally prefer iterating it from the last element to first `for (int i = (a.size() - 1); i >= 0; i--)` in those cases. That way When you remove an element it doesn't shift / change the indexes of the values that are yet to be iterated over. – OH GOD SPIDERS Jul 17 '20 at 16:12
  • @OHGODSPIDERS Good suggestion. – Unmitigated Jul 17 '20 at 16:14
2

Your method gets out of sync with the elements when removing from front to back. So remove them in reverse order.

ArrayList<String> words = new ArrayList<>(List.of("abc", "efgh", "o", "pq", "rs"));
words = removeEvenLength(words);
System.out.println(words);
        
public static ArrayList<String> removeEvenLength(ArrayList<String> a) {
   for (int i = a.size()-1; i >= 0; i--) {
      String wordEntry = a.get(i);
      if (wordEntry.length() % 2 == 0) {
        a.remove(i);
      }
   }
   return a;
}

And as stated you can also use removeIf()

Explanation.

As you move forward, removing elements, your index is still incrementing normally to get to the next element. But the list has changed by removing previous elements so the index may skip over elements that need to be checked.

Assume you want to remove even elements.

  • consider a = [5,20,40], index = 1
  • remove a[index++]; the list is now [5,40] and index = 2. 40 will not be checked because the list is now of size 2 and the iteration will cease.

By removing them in reverse, the decrease in the length of the list does not impact the index.

  • again consider a = [5,20,40], index = 2
  • remove a[index--]; the list is now [5,20] and index = 1. 20 will be checked and removed. Index will then be 0 and one element will remain.

This behavior can be mitigated by adjusting the index when removing items. However, by removing in reverse order, no such adjustment is required.

WJS
  • 36,363
  • 4
  • 24
  • 39
2

Your code is working fine but as you will delete any element from a particular index then the list index will change means the immediate element after the removed element will be updated to removed element.

You can modify your code to below code:

  public ArrayList<String> removeEvenLength(ArrayList<String> a) {
        for (int i = 0; i < a.size(); i++) {
            String wordEntry = a.get(i);
            if (wordEntry.length() % 2 == 0) {
                a.remove(i);
                i-=1;
            }
        }
        return a;
    }
2

The issue here is that when you do a.remove(i);, the ArrayList automatically updates its indices, so you end up skipping a value. Here's an example of how this could happen:

  • You get the 1st element (a.get(0);)
  • You find that it is an even length string (wordEntry.length() % 2 == 0)
  • You remove it (a.remove(i);)
  • Your for loop advances to the next value (now i = 1)
  • You get what is now the 2nd element (a.get(1);), but because you removed what was the 1st element, this is now what used to be the 3rd element.

In this scenario, you skipped over that 2nd element, which is why some strings are slipping through unnoticed. This is where I would suggest using the enhanced for loop, which simplifies things significantly so you don't need to worry about what index you are on. It would look something like this:

public ArrayList<String> removeEvenLength(ArrayList<String> a) {
    for (String wordEntry : a) {
        if (wordEntry.length() % 2 == 0) {
            a.remove(wordEntry);
        }
    }
    return a;
}

Alternatively, if you want to go for an even simpler one-liner, ArrayList offers some very convenient methods for manipulating ArrayLists. One such method, called removeIf(), pretty much does exactly what you want, but I think it's good to learn to properly use for loops before going on to use built-in methods like this. That said, if you wanted to go that route, here's how I would do it:

public ArrayList<String> removeEvenLength(ArrayList<String> a) {
    a.removeIf((wordEntry) -> wordEntry.length() % 2 == 0);
    return a;
}

Also, I just felt that I should note that there are other ways of finding even numbers. You can also use (wordEntry.length() & 1) == 0. There's no real difference as far as performance or anything, it's really just personal preference, but I just felt I should mention another way of doing it :)

Charlie Armstrong
  • 2,332
  • 3
  • 13
  • 25
1

Remove while iterating makes the problem. You can use removeIf for this

a.removeIf(wordEntry -> (wordEntry.length() % 2 == 0));

or use ListIterator to iterate the arraylist

ListIterator<String> iter = a.listIterator();
while(iter.hasNext()){
    if(iter.next().length() % 2 == 0){
        iter.remove();
    }
}
Eklavya
  • 17,618
  • 4
  • 28
  • 57