single bidirectional pass

Go Back home

The "single bidirectional pass" is an algorithmic pattern that can cut an algorithm's time complexity in half, and makes an appearance surprisingly often in highly optimised array algorithms.

It can actually make your algorithms simpler to implement, more elegant, and turn algorithms that are costly in both time and space, into single pass algorithms that use constant space.

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