# single bidirectional pass

The "single bidirectional pass" is an algorithmic pattern that can cut an algorithm's time complexity in half, and makes an appearance surprisingly often in highly optimised array algorithms.

It can actually make your algorithms simpler to implement, more elegant, and turn algorithms that are costly in both time and space, into single pass algorithms that use constant space.

Let's say you want to sum the elements of a list, from left to right. This is a very straightforward task:

```
1 A = [1,2,3,4]
2 s = 0
3 for i in range(len(A)):
4 s = s + A[i]
5 print(s, end=' ')
6 print('')
```

Output:

```
1 1 3 6 10
```

Please note this is equivalent to:

```
1 from itertools import accumulate
2 [*accumulate([1,2,3,4])]
```

Now let's say you want to do the same thing, but:

- you now need to sum the values from the
**right to the left**of the list - you also want to add these two sums (from the left, and from the right) and store the result in a new list
- you want to do this in one pass, without using additional space (the resulting list non-withstanding)

The sum from the right is easy to conceptualise:

```
1 A = [1,2,3,4]
2 s = 0
3 for i in range(len(A)):
4 s = s + A[~i]
5 print(s, end=' ')
6 print('')
```

Output:

```
1 4, 7, 9, 10
```

Please note this is equivalent to:

```
1 from itertools import accumulate
2 [*accumulate([1,2,3,4][::-1])]
```

The issue is that, we want to add values from the opposite ends of each list:

```
1 [1] 3 6 10 1 [3] 6 10 1 3 [6] 10 1 3 6 [10]
2 4 7 9 [10] 4 7 [9] 10 4 [7] 9 10 [4] 7 9 10
3 + + + +
4 =11 =12 =13 14
```

Q: The first addition consists of 1 being added to 10. But **how can you access that 10, since it only gets computed at the end of the loop?**

You may be tempted to pre-compute the RTL sum and store the result into a list for later use.

```
1 from itertools import accumulate
2
3 A = [1,2,3,4]
4 rtl_sum = [*accumulate([1,2,3,4][::-1])][::-1]
5 ltr_sum = 0
6 result = [0] * len(A)
7
8 for i in range(len(A)):
9 ltr_sum = ltr_sum + A[i]
10 result[i] = ltr_sum + rtl_sum[i]
11
12 print(result)
```

Output:

```
1 [11, 12, 13, 14]
```

Although the result would be correct, you'd be using additional space unnecessarily, not to mention inverting the data twice with slicing is ugly and confusing.

A: The trick is to stop thinking from left to right only! That's when the single bidirectional pass comes into play: add the LTR sum *so far* and also the RTL sum *so far* by using the array index complement `~`

. By the time the single pass has finished, our resulting array contains the sums of the LTR and RTL computations.

```
1 def two_way_swipe(A):
2 l_s, r_s = 0, 0
3 res = [0] * len(A)
4 for i in range(len(A)):
5 l_s = l_s + A[i]
6 r_s = r_s + A[~i]
7 res[i] += l_s
8 res[~i] += r_s
9 return res
10
11 print(two_way_swipe([1,2,3,4]))
```

Output:

```
1 [11, 12, 13, 14]
```

See also:

list index complement

product of array except self

trapping rain water