Make a list's elements consecutive by an integer n

Question

Write a method makeConsecutiveByN that could be added to the ArrayIntList class that takes an integer n as a parameter, removes any list element that does not differ from the previous element by exactly n. For example, both 8 and 2 differ from 5 by exactly 3. Your method should return true if the list was changed and false if not. For example, suppose elementData stores the following element values: [1, 3, -6, 1]. We need to compare every set of pairs. If we remove an element we need to compare the next element in the list to the last non-removed element. If n were 2 and we made a call on the previous list we would compare 1 and 3, keep 3 and then compare 3 and -6. We would discard -6 and so then compare 3 and the last 1. Our call would return true. You may not use any other arrays, lists, or other data structures to help you solve this problem, though you can create as many simple variables as you like.

I'm looking for better/other ways to write this code. I noticed that I wasn't able to iterate from the right-to-left because this problem depends on the direction of traversal. With that in mind, are there other ways I can think about solving this problem? Also looking for general feedback to cleaning up my code for the future. It is also worth noting that this is code that would be added to a custom ArrayIntList class.

public boolean makeConsecutiveByN(int n) {
    boolean isChanged = false;
    for (int i = 0; i + 1 < size; i++) {
        if (Math.abs(elementData[i] - elementData[i + 1]) != n) {
            remove(i + 1);
            i--;
            isChanged = true;
        }
        
    }
    return isChanged;
}

Answer 1

remove() is most likely linear. If so, the entire method has a quadratic time complexity. However there is a linear algorithm, which does not rely on remove():

    int kept = 0;
    int unknown = 1;
    while (unknown < size) {
        if (Math.abs(data[kept] - data[unknown]) == n) {
            data[++kept] = data[unknown];
        }
        unknown++;
    }
    erase(kept + 1, size);  // or whatever method you have to delete the tail of the array
    return unknown - kept > 1;

A perk benefit of this approach is that you don't need to reassign isChanged every time an element is removed.

Answer 2

I have only a few minor points, which mostly come down to personal preference:

• I wouldn't use the private size field, because should the way size is determined change, you'll have to change this method too. Use the public size() method instead.

• I find the expression i + 1 < size not readable. I had to think for a moment what is happing here. I'd use i < size - 1.

• I'd add a comment to remind other authors, that remove() modifies the size, because that can be unexpected. Normally in a for loop I'd cache the size of an array to avoid repeatingly calling the size/length method (for (int i = 0, len = size(); i < len - 1; i++ )), but that would break the method in this case.

• A larger point would be that I may would replace the for loop with a while in order to avoid first increasing and then decreasing i. I reversed the if condition and use continue here to emphasize that in this "normal" case I continue on to the next pair of values.

---

public boolean makeConsecutiveByN(int n) {
    boolean isChanged = false;
    int i = 0;
    while ( i < size() - 1 ) {
        if (Math.abs(elementData[i] - elementData[i + 1]) == n) {
            i++;
            continue;
        }
        remove(i + 1);
        isChanged = true;
    }
    return isChanged;
}