Iterating on an array: should you loop with .map, .forEach or for?
Tags: javascript, optimization, beginners
Published: 2023-01-31 23:17:18

> ***TL;DR? Check at least the sections "Time for the comparisons!" and "But wait! There's more" ;)***

## Table of Contents

[1. The Problem](#the-problem)
[2. How Do We Tackle That?](#how-do-we-tackle-that)
[3. My First Thoughts](#my-first-thoughts)
[4. Improve on The First Try](#improve-on-the-first-try)
[5. Comparison Between .forEach(), .map() and for](#comparison-between-foreach-map-and-for)
[6. Time For The Comparisons!](#time-for-the-comparisons)
[7. But Wait! There's More](#but-wait-theres-more)
[8. Conclusion](#conclusion)

---

I was recently asked to answer a coding exercise before a job interview. Out of the 3 questions, one felt particularly easy as I coded the answer in 5 minutes, but then... Then a problem occurred.

## The Problem

My code passed 13 out of 15 tests. For the last two, it would not give an output in due time. It was not optimized enough (*it wasn't optimized at all, if you ask me*). Unfortunately, I only had 1 min left, and I couldn't find a proper solution in time. But then I thought some more, imagined a few possible optimized solutions, and ran a few tests of my own to verify them.

Here is the exercise: from a given array filled with numbers, you should return all the possible combinations which sum matches a given target (but return each possible combination only once).
For instance, from `arr = [1, 5, 2, 4, 4]` with `target = 6`, you should return `[1, 5], [2, 4]` (or `'4,2', '5,1'`, the way in which it is presented and the order don't matter). Easy enough.
Of course, said array could be much bigger (say 20000 elements). This is when optimization kicks in.

---

## How Do We Tackle That?

What do we have to solve that kind of problem? 

- `Array.map()` and `Array.flatMap()`, which take a callback and create a new array from the existing one. (`.flatMap()` returns, as its name suggests, a flattened array.)
- `Array.forEach()`, which also takes a callback, loops through the array, and runs whatever you ask it to run (say, `.push()` the result in another empty array).
- Or a plain, basic `for` loop. In the end, for what we are after, it works a bit like a `.forEach()`: you first create an empty array, then push whatever the loop returns.

From here, we don't have so many options. We have one array, where each element must be associated with every other element exactly once if the sum is correct. What this means is:

- We need a new array
- We need to loop over the array, to get each element
- And we need to loop a second time, to get the second element

A loop inside a loop, that's never ideal. But at this point I couldn't find a better solution.

---

{% spoiler There is actually a way to stay on a linear time method %}
Thanks to Vincent A. Cicirello in the comments who pointed this out to me.

If you:

- generate a Set A out of the initial array,
- then iterate over each value and store `y = target - value` in another array or Set B,
- then iterate over B and compare y to the values in A, and store the existing pairs `[y, target - value]`
- and finally check whether the initial array contains `target / 2` at least twice (because if your target is 6, `[3, 3]` is a valid answer; but if you only have one 3 in the array, you should remove `[3, 3]` from the pairs)

Your function takes way less time. That is better and smarter in every aspect than what I'm developing here under.
I won't linger on this in the article, though, because I want to compare `.forEach()`, `.map()` and `for` in a similar environment, which is here a quadratic time one.
{% endspoiler %}

---

## My First Thoughts

Ok, we know where we're heading.

As we are dealing with an array, my first thoughts were to use a `.forEach`. (*Don't ask me why I didn't start with a `.flatMap`, which seemed called for since we are basically* returning *a new array. My excuse is that I was stressed.*)

Here's my code, commented for the beginners among you:

```js
function combine(arr, target) {
    // I initiate an empty array
    const pairs = []

    // I loop once over arr
    // I keep in memory the element (e) and its index (i)
    arr.forEach((e, i) => {
        // I loop a second time over arr, 
        // and similarly keep in memory the element `el` and its index `j`
        arr.forEach((el, j) => {
            // I compare `i` and `j` to make sure I'm not 
            // combining the same element with itself,
            // and I check that the sum meets the target
            if (i !== j && e + el === target) {
                // By using a ternary operator to assign a value,
                // I make sure each pair is presented 
                // with the smallest number first
                const pair =
                    e <= el
                        ? [e, el]
                        : [el, e]
                // Two similar arrays [1, 2] are two distinct objects.
                // To compare them, I use a trick with `JSON.stringify()`,
                // because... Well, because strings are comparable.
                pairs.push(JSON.stringify(pair))
            }
        })
    })

    // Finally, I return a set from the array,
    // to make sure I have each combination only once
    return new Set(pairs)
}
```

---

## Improve on The First Try

You might see a few problems with my function already.

For instance, why stringify the combined array? We could just return a string. Remember: the form doesn't matter. That's a good guess: removing `JSON.stringify()` means removing a function, so less computing time. This is not the crucial point, though.

The true problem here is that I loop over elements which have already been used up. Take `[1, 2, 3]`: once I returned `[1, 2]`, I don't need to return `[2, 1]`. Instead of looping over the whole array the second time, I could start at `i + 1`, the index of the current element + 1. Let's use `.slice(i + 1)` to do it.

One could even argue that the `Set` is now useless. That's true if all the elements in the array are different, but not if you have duplicates. So let's keep it.

Here's the better version:

```js
function combine(arr, target) {
    const pairs = []

    arr.forEach((e, i) => {
        arr.slice(i + 1).forEach((el, j) => {
            if (e + el === target) {
                const pair =
                    e <= el
                        ? `${e}, ${el}`
                        : `${el}, ${e}`
                pairs.push(pair)
            }
        })
    })

    return new Set(pairs)
}
```

---

## Comparison Between .forEach(), .map() and for

That's better, but it wasn't good enough to pass the last 2 tests. I didn't have time to do better, but after the timer stopped, I ran some checks.

**So what do you think? Which one of `.forEach()`, `.map()` or `for` is the fastest, and to which extent?**

Let's try. We will run `test1()`, `test2()` and `test3()` to see the difference.

First, we initiate our array:
```js
// An array of 10000 elements, each corresponding to its index
const arr = Array.from({length: 10000}, (e,i) => i)
// Let's double the array for fun (and to create duplicates)
const pirate = [...arr, ...arr]
const target = 10000
```

The first test will check the time taken for `.forEach()`.

```js
function test1(arr, target) {
	let startTime = new Date()

    function combine(arr, target) {
        const pairs = []

        arr.forEach((e, i) => {
            arr.slice(i + 1).forEach((el, j) => {
                if (e + el === target) {
                    const pair =
                        e <= el
                            ? `${e}, ${el}`
                            : `${el}, ${e}`
                    pairs.push(pair)
                }
            })
        })

        return new Set(pairs)
    }

	combine(arr, target)
    return new Date() - startTime
}
```

Then, we'll check the time taken for a `.map()`

```js
function test2(arr, target) {
	let startTime = new Date()

	function combine(arr, target) {
		const pairs = arr.flatMap((e, i) =>
            arr
                .slice(i + 1)
                .map(el => {
                    if (e + el === target) {
                        return e <= el
                            ? `${e}, ${el}`
                            : `${el}, ${e}`
                    }
                })
                .filter(e => e)
        )

		return new Set(pairs)
	}

	combine(arr, target)
	return new Date() - startTime
}
```

Finally, we'll test the simple `for` loop.

```js
function test3(arr, target) {
	let startTime = new Date()

	function combine(arr, target) {
		let pairs = []
        
        for (let i = 0; i < arr.length; i++) {
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] === target) {            
                    const pair = arr[i] <= arr[j]
                        ? `${arr[i]}, ${arr[j]}`
                        : `${arr[j]}, ${arr[i]}`
                    
                    pairs.push(pair)
                }
            }
        }

		return new Set(pairs)
	}

	combine(arr, target)
	return new Date() - startTime
}
```

---

## Time For The Comparisons!

It's time for the results. But first: what are you expecting? What would your podium be?

To avoid exceptions, I run each test 10 times and calculate the average delay (in ms). Which gives us:

| forEach() | map()   | for   |
| :-------: | :-----: | :---: |
| 3212.9    | 16618.1 | 787.2 |

So it seems we have a winner. A really, really clear winner.

**Are you as astonished as I was?**

I mean, OK, for a seasoned developer, the victory of the `for` loop won't be much of a surprise. It is well documented after all. But to this extent? Boy, was I not expecting that!

It turns out the `for` loop is more than 4 times faster than `.forEach()` and 21 times faster than the `.map()`!

In fact, the margin is so big that even if I test the solutions without slicing the array to the current element on the second loop, they remain better than other options. In the end, the fastest solutions are:

1. `for` (with `j = i + 1`)
2. `for` (with `j = 0`)
3. `.forEach()` with `.slice()`
4. `.forEach()` without `.slice()`
5. `.map()` with `.slice()`
6. `.map()` without `.slice()`

{% spoiler Update on the linear time solution %}
It doesn't make much sense to compare this to the previous results, but just for fun, how long does a truly optimized function take?
Let's code the method suggested by Vincent A. Cicirello in the comments:

```js
function combine(arr, target) {
    const set = new Set(arr)
    let pairs = new Set()
    let potentialPairings = new Set()

    set.forEach(e => potentialPairings.add(target - e))

    potentialPairings.forEach(pairing => {
        if (set.has(pairing)) {
            const pair =  pairing > (target - pairing) 
                    ? `${target - pairing}, ${pairing}` 
                    : `${pairing}, ${target - pairing}`
            pairs.add(pair)
        }
    })

    if (arr.filter(n => n === (target / 2)).length < 2) pairs.delete((`${target / 2}, ${target / 2}`))

    return pairs
}
```

With 10000 items duplicated, this takes a whopping 5 ms to compute.
And what do we learn from this, kids? That you should really, reaaaally put some efforts in keeping a linear time function. Don't follow my lead.

{% endspoiler %}

---

## But Wait! There's More

What could there be left to be said? We have a podium, and that article is already too long!

Well, as I was writing this, I found out that the results are very, very different if you remove the target. Basically, instead of returning every pair that matches a target, you return every single possible pair. That obviously takes a lot more time to compute.

Because I like my laptop, I tested with an array of 3000 instead of 10000. Here are the results:

| forEach() | map()  | for    |
| :------:  | :----: | :----: |
| 9147.1    | 9097.4 | 8892.2 |

The results are much tighter. `for` remains the winner, but in this case all three options are fairly similar - and `.map()` is consistently, although slightly, better than `.forEach()`.

---

## Conclusion

Two things are certain:

1. If you can find a way, remove those nested loops.
2. `for` is your go-to if you need an optimization boost and you cannot reduce the number of nested loops. Additionnally, the less matches it finds, the faster `for` gets, and the bigger the gap between `for` and the rest. So if you have a very specific condition at the start of the second loop, it will trim the computed time.

For the rest, to be honest, I'm still trying to figure out where the huge differences in results comes from - and I'm talking of the difference between the 3 options in the first tests, as well as the difference between the first tests and the second ones. If you have an answer or an assumption, please leave a comment, I'll take it! :)