Welcome to CodeRanch!

I can think of a way to do it in linear time (but not space)

1) Create a new ArrayList of the original size minus the number of elements to remove - this will ensure the new ArrayList doesn't grow as you add elements

2) Go through the original ArrayList adding the element at each index (unless it needs to be removed) to the new one

This doesn't use linear space though. The ArrayList class doesn't have a method that does what you are looking for. I recommend checking the performance of the code using normal ArrayList methods first to see if this is an actual performance problem.

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

Carl Dewitt wrote:I have an ArrayList of tens of thousands of elements, and want to remove the items at a given set of sorted indices like {1,5,29,318,499,583}. It seems like this operation could be performed in linear time and space by first finding a cumulative sum of the shifts needed to move everything to their right positions and then shifting every item. On the other hand, removing and shifting one by one would seem to require many more shifts. Is there a way to do this in Java's ArrayList?

I suspect you might be overthinking this. My O(n + r) solution would be:

1. Go through the list of indices and "null out" the element at that index.

2. Copy all non-null elements from your original list to the new one.

Or, if the

*original*List CAN contain nulls, then an alternative is to:

1. Sort the indices to be removed.

2. Copy the elements from your original list to the new one, missing out the indices in your "to be removed" array.

Slightly more complex than above, but basically the same idea.

The latter will be

`O(n + (r log r))`which, assuming r (the number of elements to remove) is relatively small, won't affect

`O(n)`very much. In the first case, assuming

`r < n`(ie, no duplicate indices), the overall time must be

`<= O(2n) == O(n)`. The copy can be done "in place" in both cases, so it would only require space relative to r if a sort is involved in the latter case.

If you want to get fancy, you could use a HashSet of "indexes to be removed", but you'll likely have a space overhead. I leave that to your ingenuity.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here