Say you have an array, a simple array with 16 integers.

const eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];

Your task is to remove all numbers that are greater than 99. Simple enough! You will iterate over the array and remove all the elements that are greater than 99.

Important

Although the following examples use JavaScript, the logic and the issue it posses are valid for any programming language. Near the end, I have added examples in Golang, C#, C++, Python and JavaScript.

Your code will probably look like this,

const eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];

for (let i = 0; i < eg.length; i++) {
  if (eg[i] > 99) {
    // Remove element
    eg.splice(i, 1);
  }
}

If you print the result eg, you will see that the result is not quite right.

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 233, 610];

This result cannot be correct. 233 and 610 are greater than 99 and still left in the array.

What went wrong?

Let’s add some log statements to the code. You can view and run the code at this link.

for (let i = 0; i < eg.length; i++) {
  console.log(i, eg[i], eg.length);
  if (eg[i] > 99) {
    // Remove element
    eg.splice(i, 1);
    console.log(`Element at ${i} removed. Length is  ${eg.length}`);
  }
}

The output is,

0 0 16
1 1 16
2 1 16
3 2 16
4 3 16
5 5 16
6 8 16
7 13 16
8 21 16
9 34 16
10 55 16
11 89 16
12 144 16
Element at 12 removed. Length is  15
13 377 15
Element at 13 removed. Length is  14
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 233, 610 ]

Notice that when the index i is 12, it reaches element 144. 144 is removed, which reduces array length to 15 from 16.

Then the index i is 14, and it reaches element 377. 377 is removed, which reduces array length from 15 to 14.

Then the index i reaches 15, but it fails the condition i < eg.length, which stops the result.

The loop ran only 14 times when it should have run 16 times. It happens because we modified the array length during the iteration.

Error

If you think forcing loop to run 16 times will fix the issue, then you are wrong again.

Have a look at following incorrect code.

const eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];

const len = eg.length;

for (let i = 0; i < len; i++) {
  console.log(i, eg[i], eg.length);
  if (eg[i] > 99) {
    // Remove element
    eg.splice(i, 1);
    console.log(`Element at ${i} removed. Length is  ${eg.length}`);
  }
}

If you try to run this code, you will get index out of bound runtime errors.

Now, how do we solve this issue? We have three ways to do it right way.

Solution 1 — Decrement index

One way to solve this problem is to decrement i whenever an element from the array is removed. This way index does not skip over the remaining elements of the array.

const eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];

for (let i = 0; i < eg.length; i++) {
  console.log(i, eg[i], eg.length);
  if (eg[i] > 99) {
    // Remove element
    eg.splice(i, 1);
    console.log(`Element at ${i} removed. Length is  ${eg.length}`);
    // Important
    i--;
  }
}

console.log(eg);

Its output is

0 0 16
1 1 16
2 1 16
3 2 16
4 3 16
5 5 16
6 8 16
7 13 16
8 21 16
9 34 16
10 55 16
11 89 16
12 144 16
Element at 12 removed. Length is  15
12 233 15
Element at 12 removed. Length is  14
12 377 14
Element at 12 removed. Length is  13
12 610 13
Element at 12 removed. Length is  12
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ]

You can view and run this code here.

Solution 2 — Iterate in Reverse

In this solution, you start from the last element of the array and continue backward. This way, even if array length is modified, the loop iterates over all the remaining elements.

const eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];

let i = eg.length;

while (i--) {
  console.log(i, eg[i], eg.length);
  if (eg[i] > 99) {
    // Remove element
    eg.splice(i, 1);
    console.log(`Element at ${i} removed. Length is ${eg.length}`);
  }
}

console.log(eg);

Its output is

15 610 16
Element at 15 removed. Length is 15
14 377 15
Element at 14 removed. Length is 14
13 233 14
Element at 13 removed. Length is 13
12 144 13
Element at 12 removed. Length is 12
11 89 12
10 55 12
9 34 12
8 21 12
7 13 12
6 8 12
5 5 12
4 3 12
3 2 12
2 1 12
1 1 12
0 0 12
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ]

You can view and run this code here.

You can, of course, use a for loop in place of while.

for (i = eg.length - 1; i >= 0; i--) {}

You can view code with a for loop here.

Is this problem specific to some languages?

No! Whichever programming language you pick, if you iterate and remove array elements incorrectly, you will face this issue.

Here is the same problem replicated in Golang. If you run it, the program fails during runtime.

package main

import "fmt"

func remove(slice []int, s int) []int {
    return append(slice[:s], slice[s+1:]...)
}

func main() {
    eg := []int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}
for i, el := range eg {
        if el > 99 {
            eg = remove(eg, i)
      fmt.Println(len(eg))
        }
    }


    fmt.Println(eg)
}

Output of the above program:

./main
15
14
panic: runtime error: slice bounds out of range

goroutine 1 [running]:
main.remove(...)
    /home/runner/main.go:6
main.main()
    /home/runner/main.go:14 +0x25b
exit status 2

But if we turn around the code and start iteration is reverse, then the code works fine.

package main

import "fmt"

func remove(slice []int, s int) []int {
    return append(slice[:s], slice[s+1:]...)
}

func main() {
    eg := []int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}
    l := len(eg) - 1
    for l >= 0 {
    if eg[l] > 99 {
            eg = remove(eg, l)
        }
    l = l - 1
    }

    fmt.Println(eg)
}

Best Solution

A succinct solution is to use functional programming.

Most modern programming languages are incorporating functional programming features. Thus, if a language supports new methods, you do not have to use the old fashioned loops to remove elements from an array.

JavaScript

In ECMA-262 5th edition, filter() method was added to the JavaScript.

We can rework the above example into a simple oneliner.

const eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];
result = eg.filter(x => x < 99);
// Output
console.log(result);

Python

Here is a working Python oneliner.

eg = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
result = [x for x in eg if x < 99]
print(result)

### C\

Either of the following way will work in C#.

Using Linq.

using System;
using System.Collections.Generic;
using System.Linq;

class MainClass {
  public static void Main (string[] args) {
    List<int> eg = new List<int>(){0, 1, 1, 2, 3, 5, 8, 13,
                        21, 34, 55, 89, 144, 233, 377, 610};
    var result = (from x in eg where x < 99 select x).ToList();
    result.ForEach(i => Console.WriteLine(i));
  }
}

Using predicate.

using System;
using System.Collections.Generic;

class MainClass {
  public static void Main (string[] args) {
    List<int> eg = new List<int>(){0, 1, 1, 2, 3, 5, 8, 13,
                        21, 34, 55, 89, 144, 233, 377, 610};
    eg.RemoveAll(i => i > 99);
    eg.ForEach(i => Console.WriteLine(i));
  }
}

C++

C++ has std::remove_if method.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> eg = {0,  1,  1,  2,  3,   5,   8,   13,
                         21, 34, 55, 89, 144, 233, 377, 610};
  eg.erase(std::remove_if(
              eg.begin(),
              eg.end(),
              [](int x) {
                  return x > 99;
              }),
           eg.end());

  // Print result
  std::for_each(eg.begin(),
                eg.end(),
                [](const int &e) {
                    std::cout << e << " ";
                });
}

You can run this code here.

Like this post? Share on: TwitterFacebookEmail

Comments

So what do you think? Did I miss something? Is any part unclear? Leave your comments below.
You need a free Github account to comment.


Keep Reading


Published

Category

Algorithm

Tags

Stay in Touch

Get New Posts In Your Inbox