longest time lazy flappy bird can survive - consecutive gap between 2 arrays

Question

given two arrays:

import numpy as np
L1 = np.array([3, 1, 4, 2, 3, 1])
L2 = np.array([4, 8, 9, 5, 6, 7])

I want to efficiently find the longest consecutive gap that exists.

For example, let i be the ith index of both arrays.

    i = 0:  elements = (3,4) -> gap in range 3-4 -> longest path = 1
    i = 1: elements = (1,8)  -> 3-4 intersect 1-8 is 3-4 -> longest path = 2
    i = 2: elements = (4, 9) -> 3-4 intersect 4-9 is NULL -> longest path = 2

    ##this is what slows my approach down
    #now, we must return to i = 1

    i = 1: elements = (1,8) -> candidate interval is 1-8 -> path = 1, longest path = 2
    i = 2: elements = (4,9) -> 1-8 intersect 4-9 is 4-8 -> path = 2, longest path = 2
    i = 3: element = (2,5) -> 4-8 intersect 2-5 is 4-5 -> path = 3, longest path = 3
    ...

If you try to visualize it, it's a bit like that flappy bird game, and so what I'm trying to find is the longest time the bird can remain at the same level without dying

I want a way to not track back, so that I only go through each i one time. Any suggestions? preferably in python

update

I wrote some code to visualise the problem (note I assumed here that the maximum number of rows is 10, this isn't always the case:

def get_flappy_matrix(ceiling, floor):
    '''
    given ceiling and floor heights
    returns matrix of 1s and 0s
    representing the tunnel
    '''
    ceil_heights = np.array(ceiling)
    floor_heights = np.array(floor)
    nmb_cols = len(ceil_heights)
    flappy_m = np.ones(shape=(10, nmb_cols), dtype=np.int)

    for col in range(nmb_cols):
        for row in range(ceil_heights[col], floor_heights[col]):
            flappy_m[row, col] = 0

    return flappy_m

N = 6
L1 = np.array([3, 1, 4, 2, 3, 1])
L2 = np.array([4, 8, 9, 5, 6, 7])


m = get_flappy_matrix(L1, L2)

plt.pcolor(m, cmap=plt.cm.OrRd)
plt.yticks(np.arange(0, 10, 1), range(0, 11))
plt.xticks(np.arange(0, N+1),range(0,N+1))
plt.title(str(max_zero_len))
plt.gca().invert_yaxis()
plt.gca().set_aspect('equal')
plt.show()

Now, from another answer, this is one (still slow for large input) approach to the problem:

max_zero_len = max(sum(1 for z in g if z == 0) for l in m for k, g in itertools.groupby(l))
print(max_zero_len)
 # 5

Answer 1

Keep a window of consecutive holes the bird can fly through. Extend it at the right one hole at a time, and remove holes from the left when necessary using the following strategy. When you reach the end, the longest window you managed to construct is the solution.

Track the lowest upper wall in the window, and the lowest upper wall that comes after that wall, and the lowest upper wall that comes after that wall, up to the last upper wall in the window. Do something similar for lower walls. For example, if the window goes from holes 3 to 9 here:

    | | | | | | | | upper wall sections
    | | | | | | |
    |   |   |   |
    |   |   |
    |   |   |
... | ------------- window
    | -------------
    |   |
      | | | |     |
    | | | | |   | | lower wall sections
    2 3 4 5 6 7 8 9
    wall numbers

then the upper bound walls are 6, 8, and 9, and the lower bound walls are 4 and 9. (We break ties by picking walls to the right.)

Say we extend the window to the tenth hole, and the tenth hole looks like this:

    | | | | | | | | |upper wall sections
    | | | | | | |   |
    |   |   |   |   |
    |   |   |       |
    |   |   |
... | --------------- window
    | ---------------
    |   |
      | | | |     |
    | | | | |   | | | lower wall sections
    2 3 4 5 6 7 8 9 10
    wall numbers

Upper wall 10 is lower than upper walls 9 and 8, so 9 and 8 are no longer upper bounds. The upper bounds are now 6 and 10, and the lower bounds are now 4, 9, and 10.

On the other hand, if hole 10 looked like this:

    | | | | | | | | | upper wall sections
    | | | | | | |
    |   |   |   |
    |   |   |
    |   |   |       |
... |               |
    |               |
    |   |           |
      | | | |     | |
    | | | | |   | | |
    2 3 4 5 6 7 8 9 10
    wall numbers

Lower wall 10 is higher than the lowest upper bound, so we need to remove walls from the left of the window. We advance the window to start at hole 7, removing everything up to the old lowest upper bound (wall 6), and we find that the next upper bound, wall 8, is high enough to produce a valid window:

    | | | | | | | | | upper wall sections
    | | | | | | |
    |   |   |   |
    |   |   | ------- window
    |   |   |       |
... |               |
    |               |
    |   |           |
      | | | |     | |
    | | | | |   | | |
    2 3 4 5 6 7 8 9 10
    wall numbers

If upper wall 8 had still been too low, we would have advanced the window to start at hole 9, and so on.