CODEWITHSUNDEEP
javaarraylisttime-complexity
sossu
sossu

Reputation: 23

How to remove elements from arraylist in linear time

Great suggestions but some of them were not allowed (as streams), was very restricted task. Leo's algorithm was the thing I was looking for.

I'm trying to compare a specific letter on arraylist elements and need to remove every bigger letter from the arraylist. This has to be done in linear time, so remove() is not an option. How do I do it?

int deleted = 0;
int n = 0;

while (n < A.size()) {
    if (A.get(n).compareTo(x) > 0) {
        //removing here
        removed = removed + 1;
    }
    n++;
}

return removed;

A is an arraylist with random alphabetical letters and x is also a random letter. I need to remove every element from A which is bigger than the given x letter. Remove() is not an option because I need to do this in linear time instead of n^2.

Upvotes: 2

Views: 1037

Answers (5)

Dici
Dici

Reputation: 25950

The least expensive solution is to traverse the list once while incrementing an index that represents the number of elements matching the criterion. Every time an element is found, it is set at this index and the index is incremented. In the end, you just have to delete everything at the right of this index. It's cheap to do so because deleting at the end of an array list is constant time.

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(Arrays.asList(1, 3, 6, 4, 7, 0, 2));
    filterLargerElementsInPlace(list, 4, Comparator.naturalOrder());
    System.out.println(list); // [1, 3, 0, 2]
}

public static <T> void filterLargerElementsInPlace(List<T> list, T max, Comparator<T> cmp) {
    int i = 0;
    for (T elem : list) {
        if (cmp.compare(elem, max) < 0) {
            // mutating the list as we traverse it, but it's safe as i is always less than the current index
            list.set(i++, elem);
        }
    }
    while (list.size() > i) list.remove(list.size() - 1);
}

Upvotes: 1

Leo Aso
Leo Aso

Reputation: 12463

If you want to remove elements in linear time from the list itself rather than creating a new list, then you can do it like this.

int i = 0;
int j = 0;

while (j < A.size()) {
    if (A.get(j).compareTo(x) > 0) {
        j++;
    } else if (i < j) {
        A.set(i++, A.get(j++));
    } else {
        i++;
        j++;
    }
}
int oldSize = A.size();
int newSize = oldSize - j + i;
A.subList(newSize, oldSize).clear();

This basically runs once through the list, shifting down elements to overwrite the elements that need to be filtered out. Then the list is trimmed down to size in the last three lines.

Upvotes: 0

Oleg Pavlyukov
Oleg Pavlyukov

Reputation: 161

Maybe that's you need? 

ArrayList<String> b = a.stream().filter(l -> l.compareTo(x) <= 0)
                                .collect(Collectors.toCollection(ArrayList::new));

Upvotes: 1

Fullstack Guy
Fullstack Guy

Reputation: 16908

We can use a SortedSet to get the set having elements less than the given string, this can be achieved by using the SortedSet.headSet(String key) method:

List<String> list = new ArrayList<>();
list.add("d");
list.add("l");
list.add("e");
list.add("z");
list.add("x");

SortedSet<String> set = new TreeSet<>(list);
String x = "f"; //string to compare
List<String> elementsLessThanX = new ArrayList<>(set.headSet("f")); 
System.out.println(elementsLessThanX);

Output:

[d, e]

This is definitely not constant time but it is better than O(n^2). This implementation would not modify the original list.

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

You can add elements in linear time to another list. For example:

ArrayList<Integer> result = new ArrayList<Integer>();
for(int n = 0; n < A.size(); n++) {
    if(A.get(n).compareTo(x) <= 0) {
        result.add(A.get(n));
    }
}
return result;

or with streams as @Dici says:

A.stream().filter(n -> n.compareTo(x) <= 0).collect(Collectors.toList());

You can later swap the lists, or clear the original list, and copy the values from result back in that list, which takes linear time as well.

Although using another data structure to store data might be beneficial as well.

Upvotes: 3

Related Questions