Range of each building in array

I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, X[i]+H[i] ], both ends inclusive, will collapse, too. Those collapsed building may cause more buildings to collapse and so on, just like a domino effect. For each building, we want to find its range of effect, represented by the largest coordinate that will be affected.

Example

X = {5 6 9 11}

H = {2 3 1 5}

ans = {10 10 10 16}

Explanation: the collapse of building 0 will cause building 1 to collapse since 6 is in [5+1, 5+2]. The collapse of building 1 will cause building 2 to collapse since 9 is in [6+1, 6+3]. Finally, building 2 will affect [9+1, 9+1], which does not contain 11, the coordinate of building 3. So the range for building 0, 1 or 2 is 9+1=10. The range of building 3 is 11+5=16.

There is a $$O(|X|)$$ algorithm for this problem using a stack.

Algorithmic details:

• For a building $$i\in \{1, ..., n\}$$, we will be pushing $$i$$ onto the stack $$S$$. For building $$i$$, let $$X_i$$ be its coordinate, $$H_i$$ be its height and $$R_i$$ be its range.

• While iterating over the data (i.e. $$i = 1 ... n$$), we maintain the loop invariant that $$S$$ will only contain indices $$j$$ such that $$R_j \ge X_i$$ at the end of $$i$$-th iteration.

• The loop invariant implies that for buildings $$k$$ and $$k'$$, where $$k, which are next to each other in $$S$$, we have $$R_k=\max(X[k]+H[k], R_{k'})$$.

• At the start of $$i$$-th iteration, to maintain the loop-invariant, we must pop all indices $$j$$ from top of $$S$$ such that $$R_j \lt X[i]$$.

• The loop invariant also forces us to push $$i$$ on top of $$S$$ at the end of $$i$$-th iteration.

• (Edit) Running time will be $$O(|X|)$$ because each $$X_i$$ gets pushed on to the stack $$S$$ (and subsequently popped off) only once for each $$i \in \{1,...,n\}$$. And we need not do more than $$O(1)$$ work with each operation on $$S$$.

• (Edit) Space complexity will be $$O(|X|)$$. Observe the case where $$X=\{1,2,3,...,n\}$$ and $$H=\{n,n-1,n-2,...,1\}$$ for some $$n\in \mathbb{N}$$. That is, pushes onto the stack will happen before any pops.

Insight:

Think about maximal sets of buildings (not necessarily contiguous) where if one falls, then all the ones on its right within the same set will fall too. Now if we look at lowest and highest indices of buildings in such a set as endpoints of an interval, then intervals are either contained within one another or they don't overlap at all. That is, there is always at least one set of contiguous buildings. If this set is removed from the list of buildings, another set will now have contiguous buildings.

Code (Python 3.x):

import random

MAX_RANGE = 2**32

#implementation of the explained O(|X|) algorithm
def building_dominoes(X, H):
''' For building i, we store (i, X[i] + H[i]) on the stack
to simplify some aspects of the implementation. Same is
the reason for using MAX_RANGE. These can be done away
with easily.
'''

s, result, rang = [], *len(X), 0

for i in range(len(X)):
clear_stack(s, X[i], result)
s.append((i, X[i] + H[i]))

clear_stack(s, MAX_RANGE + 1, result)

return result

def clear_stack(s, x, result):
range_max = 0
while s and s[-1] < x:
j, new_range = s.pop()
result[j] = range_max = max(range_max, new_range)

# brute-force version
def brute_force(X, H):
n = len(X)
res =  * n
for i in range(n-1, -1, -1):
res[i] = max([X[i] + H[i]] + [res[j] for j in range(i+1, n) if X[j] <= X[i] + H[i]])
return res

# small set of tests
META_X = [
[5, 6, 9, 11],
[0, 1],
[1, 2, 3, 4, 5],
[1, 2, 3, 4, 5],
[1, 2, 3, 6, 8, 10],
]
META_H = [
[2, 3, 1, 5],
[9, 1],
[2, 4, 6, 8, 10],
[10, 8, 6, 4, 2],
[8, 3, 1, 2, 1, 1],
]

success = 0
for i in range(len(META_X)):
if building_dominoes(META_X[i], META_H[i]) == brute_force(META_X[i], META_H[i]):
success += 1
print(f"Passed {success} tests from the specified set of {len(META_X)} tests.")

# randomized tests
VALS = list(range(100000))
MIN_N, MAX_N = 10, 500
NUM_TESTS = 500
success = 0
for i in range(NUM_TESTS):
size = random.randint(MIN_N, MAX_N + 1)
X = sorted([random.choice(VALS) for _ in range(size)])
H = [random.choice(VALS) for _ in range(size)]
if building_dominoes(X, H) == brute_force(X, H):
success += 1
print(f"Passed {success} tests from the set of {NUM_TESTS} randomized tests.")
• @Apass.Jack thanks for pointing it out. I have fixed the answer accordingly. – Arsalan Jumani Aug 3 at 11:50
• @Apass.Jack Thanks. Just added it. – Arsalan Jumani Aug 4 at 8:19