Index Mapping: Simple Python Solution


  • 0
    Y

    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.add(left_start)
                relevant.add(left_start + length -1)
            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
    
    

Log in to reply
 

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