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 the 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 the 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 backwards. 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)
}
The 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 ways will work in C#.
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 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.
Cover Image Attribution: Gabriel Garcia Marengo
Top comments (0)