Remove elements from an array during enumeration

AKA: .enumerate().reversed() or .reversed().enumerate() confusion, why can’t I just filter and get the result efficiently?

Image for post
Image for post
A visual illustration where we remove the third element in this particular array. Nice.

Difficulty: Easy | Normal | Challenging

Prerequisites:

Terminology

The problem

The example here is you have an array of times (in milliseconds) and you want to return the number of elements that are within 1000 milliseconds of the last element. The array is in time order, and has at least one element.

Therefore:

[1,2,3,1000] = [1,2,3,1000]

[1000,1001,1004,2000] = 1

  1. The easy solution

Filtering has a time complexity of O(n), and gives us a short and easy to understand solution

var last = input.last!

input.filter{ $0 — input.last! <= 1000}

Great! We are done. One issue might be that you do not like higher order functions, so want another solution.

2. The correct (wrong) way depending on your needs

Just moving through the list and removing elements will mean you risk running out of elements, and causing a nasty crash.

To prevent this you can come up with a better solution — reverse the list.

The issue is that you need to enumerate the list (so you can remove the appropriate element) — but do you enumerate before you reverse or the opposite?

For the input array [1000,1001,1004,2000]

for value in input.reversed().enumerated() {

print (value.element, value.offset)}

This returns

2000 0

1004 1

1001 2

1000 3

So what is happening is we first reverse the list, and then enumerate the result. This is not what we want, as we want to traverse the list in reverse order and remove the element from the original location in the list.

The alternative to this is

for value in input.enumerated().reversed() {

print (value.element, value.offset)}

Which returns

2000 3

1004 2

1001 1

1000 0

As we enumerate the list first and then reverse the list. The enumeration relates to the original order of the list — and this is what we want!

We can remove the elements on our reversed list — and we will never get a crash!

for value in input.reversed().enumerated() {

if value.element — input.last! > 1000 {

input.remove(at: value.offset) } }

Issues? The programming logic is not that easy to follow, and mistakes do happen! Plus why use this over filter (well, because your logic may not be a good fit for higher-order functions is a good reason)

3.The Correct solution

You can use removeAll to solve this problem!

var last = input.last!

input.removeAll(where: { ($0 — last > 1000 ) } )

Unfortunately we need to move our definition of last outside the function, as our algorithm is in-place.

This is faster than filter, and removes items in-place.

4.The faster solution

If you want super speed™ you don’t need to settle for O(n) and traversing each and every element in your input list.

var last = input.last!

while input[0] < last — 1000 {

input.removeFirst()}

Will do the job fine — and is faster! as you only traverse through the first 1000 elements (or less!); awesome!

Conclusion

However, doing things right can still have benefits, and you should want to make things both faster and better in your professional life. After all, isn’t that why people become programmers?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store