554.Brick Wall

Tags: [sorted_data], [binary_search], [left_sum], [trick], [map]

Com: {fb}

Link: https://leetcode.com/problems/brick-wall/#/description

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from thetopto thebottomand cross theleastbricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

Input:
[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]

Output:
 2

Explanation:

Note:

1. The width sum of bricks in different rows are the same and won't exceed INT_MAX.
2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

Solution: Map

class Solution(object):
    def leastBricks(self, wall):
        """
        :type wall: List[List[int]]
        :rtype: int
        """
        if not wall:
            return 0

        cut_locations = {}
        for row in wall:
            cut_location = 0
            for brick in row:
                cut_location += brick
                if cut_location not in cut_locations:
                    cut_locations[cut_location] = 1
                else:
                    cut_locations[cut_location] += 1

        row_sum = sum(wall[0])
        num_of_rows = len(wall)
        min_num_of_cross_bricks = num_of_rows
        for cut_location in cut_locations:
            if cut_location == row_sum:
                continue
            min_num_of_cross_bricks = min(min_num_of_cross_bricks, 
                                          num_of_rows - cut_locations[cut_location])

        return min_num_of_cross_bricks

Revelation:

• Using map to record all cut_locations, and count the number of rows have this cut_location.

Note:

• Time complexity = O(num_of_bricks).
• Space complexity = O(num of different row left sum).

Solution: Sorted Data, Left Sum, Binary Search

class Solution(object):
    def leastBricks(self, wall):
        """
        :type wall: List[List[int]]
        :rtype: int
        """
        if not wall or not wall[0]:
            return 0

        # calculate the left_sum for each row.
        min_brick_width = sys.maxint
        for row in wall:
            for i in xrange(1, len(row)):
                min_brick_width = min(min_brick_width, row[i])
                row[i] += row[i - 1]

        row_sum = wall[0][-1]
        min_num_of_cross_bricks = len(wall) # num of rows.
        for i in xrange(1, row_sum, min_brick_width):
            cross_brick_counter = 0
            for row in wall:
                if not self.binary_search(row, i):
                    cross_brick_counter += 1

            min_num_of_cross_bricks = min(min_num_of_cross_bricks, cross_brick_counter)

        return min_num_of_cross_bricks

    def binary_search(self, arr, target):
        start = 0
        end = len(arr) - 1
        while start <= end:
            mid = start + (end - start) / 2
            if arr[mid] == target:
                return True
            elif arr[mid] < target:
                start = mid + 1
            else:
                end = mid - 1

        return False

Revelation:

• 首先我想到在坐标系上把这些砖块都标注出来，因为每个砖块都有一个宽度，所以每个砖块在坐标的x轴上就有一个start和一个end，然后我们可以移动一个竖线，每移动一格，就看一下所有的row，看看是否竖线穿过当前的row的砖块，当我把坐标[start, end]都画出来后，我发现每一行的end其实就是left_sum，是sorted的， 而且start也是sorted的，那么其实我们在判断是否竖线穿过了当前row的brick，我就可以用binary search来找当前竖线在哪一个[start, end]中，找到那个[start, end]后，再看如果竖线正好在start或在end上，那么就认为竖线没有穿过brick，但细想一下其实我们不需要start，只需要这一个row上所有的end，如果binary search没有找到target，那么这个竖线一定在某一个[start, end]里(not at start or end)，就说明当前竖线穿过了这个row的brick，如果binary search找到了target，就说明当前竖线正好在某个end上，由于前一个brick的end和后一个start是挨着的，所以这个竖线就是在某两块brick之间，就没有穿过这个row的brick，但其实竖线每次移动1，是没必要的，我们可以上竖线每次移动的长度为最短的brick的长度，这样既不会漏掉brick又可以节省时间.

Note:

• Time complexity = O((row_sum / min(brick_width)) * num_of_rows * lg(max(num_of_cols))).
• Space complexity = O(1).