I would first transform the window arrays into key => value pairs where the key would be the starting key of the corresponding value.

Then I would iterate over all the possible values, checking for key existence in either transformed window arrays, and when we find one, it creates a new item in the resulting array with the new value from the changing array and the previous value of the other array.

The tricky part is the end since there's no more "starting value" but I assume you can have a last key => null value pair for this.

For your example, the transformed arrays would look like this:

left = [0 => 'foo', 2 => 'bar', 5 => null]
right = [1 => 'bas', 3 => 'qux', 4 => null]

Of course this method requires the windows to be contiguous.

unfortunately, iteration is precisely what I'm trying to avoid here -- in the wild, these windows will sometimes be very large

I do have some code that seems to work

https://github.com/Tactical-Metaphysics/LiSE/blob/query/LiSE/LiSE/query.py#L403-L582

but it's a maze of special cases and I feel like there must be a better way

Actually, my code turns out not to work in a lot of cases!

Thanks for your help

Did you end up using part of my suggestion or did my suggestion prompt you to revisit your code?

Uh, I guess the latter

Might have provided inspiration since the code was advancing down the list too quickly and I needed to take it step by step

Either way I’m glad it helped you!