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]