# single bidirectional pass

The "single bidirectional pass" is an algorithmic pattern that can be seen from time to time in super-duper optimized algos.

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

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

Output:

```
11 3 6 10
```

Please note this is equivalent to:

```
1from 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:

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

Output:

```
14, 7, 9, 10
```

Please note this is equivalent to:

```
1from 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]
24 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.

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

```
1def 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
11print(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]]