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:

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