# single bidirectional pass

🏠

The "single bidirectional pass" is an algorithmic pattern that can be seen from time to time in highly optimized algorithms.

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]