[LeetCode] 554. Brick Wall

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 the top to the bottom and cross the least bricks.
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.

Thought process:
Iterate the bricks one by one. Use a hash map to keep track of prefix sum -> count. The prefix sum with the largest count is the position where the lease number of bricks are crossed.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();
        for (List<Integer> row : wall) {
            int prefixSum = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                prefixSum += row.get(i);
                if (!map.containsKey(prefixSum)) {
                    map.put(prefixSum, 0);
                }
                map.put(prefixSum, map.get(prefixSum) + 1);
            }
        }
        
        int max = 0;
        for (int key : map.keySet()) {
            max = Math.max(max, map.get(key));
        }
        return wall.size() - max;
    }
}

Time complexity:
Say the height of the wall is h and width of the wall is w. Although I'm iterating brick by brick, the worst-case time complexity is O(hw).
Location: Philadelphia, PA, USA

Comments

Post a Comment

Popular posts from this blog

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers  prices , for which the  i -th element is the price of a given stock on day  i ; and a non-negative integer  fee  representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make. Example 1: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1 Selling at prices[3] = 8 Buying at prices[4] = 4 Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Note: 0 < prices.length <= 50000 . 0 < prices[i] < 50000 . 0 <= fee < 50000 . Thought process: Each day there are two options, buy or sell. Use two variables buy and sell to keep track of the max profit. Solutio...
Read more

[LeetCode] 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of  non-empty  words from the dictionary, where  words are sorted lexicographically by the rules of this new language . Derive the order of letters in this language. Example 1: Given the following words in dictionary, [ "wrt", "wrf", "er", "ett", "rftt" ] The correct order is:  "wertf" . Example 2: Given the following words in dictionary, [ "z", "x" ] The correct order is:  "zx" . Example 3: Given the following words in dictionary, [ "z", "x", "z" ] The order is invalid, so return  "" . Note: You may assume all letters are in lowercase. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary. If the order is invalid, return an empty string...
Read more

[LeetCode] 410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m  subarrays. Note: If  n  is the length of array, assume the following constraints are satisfied: 1 ≤  n  ≤ 1000 1 ≤  m  ≤ min(50,  n ) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8] , where the largest sum among the two subarrays is only 18. Thought process: Binary search. The range of the answer is between max(nums) and sum(nums). Do a binary search on this range. For every mid value, I check if the array can be split into m sub-arrays, where each sub-array's sum <= mid. If I can, that means mid is too large. Keep the left half. If I can't, that means mid is too small. Keep the...
Read more