# 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]