# Index Mapping: Simple Python Solution

• The first version below is what I want to do, (one bucket for each unit of x) but we obviously can't have an array that large.

So instead, we can simply map the x positions to a new x-axis (0, 1, 2, 3, ...) that only keeps track of the original indices that we care about.

For example, consider input
[[1,2], [2,3], [6,1]], which corresponds to left, right indices:
[1,3, 2,5, 6,7].
We map 1,2,3,5,6,7 to 0,1,2,3,4,5, respectively.

This results in version two (fallingSquares) below.

One:

``````
def fallingSquares_not_okay(self, positions):
"""
:type positions: List[List[int]]
:rtype: List[int]
"""
# positions[i] = (left, side_length)
if not positions:
return []
x_buck = [0 for _ in range(10**8 + 10**6)] # one bucket for each unit of x.
best = -float('inf')
result = []
for position in positions:
left_start, length = position
max_in_length_range = max(x_buck[left_start: left_start+length])
height_now = max_in_length_range + length
best = max(best, height_now)
for index in range(left_start, left_start + length):
x_buck[index] = height_now
result.append(best)
return result
``````

Two:

``````    def fallingSquares(self, positions):
# positions[i] = (left, side_length)
if not positions: return []
best = -float('inf')
result = []
relevant = set()
for left_start, length in positions:
relevant = sorted(list(relevant)); length = len(relevant)
get_index = {position: index for index, position in enumerate(relevant)}
x_buck = [0 for _ in range(length)]
for left_start, length in positions:
left = get_index[left_start]
right = get_index[left_start + length-1]
max_in_length_range = max(x_buck[left: right+1])
height_now = length + max_in_length_range
best = max(best, height_now)
for index in range(left, right+1):
x_buck[index] = height_now
result.append(best)
return result

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.