FilesExpand file tree

 master

/

BrickWall554.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (54 loc) · 1.82 KB

 master

/

BrickWall554.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (54 loc) · 1.82 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

/**

* 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:

* https://leetcode.com/static/images/problemset/brick_wall.png

*

* Note:

* The width sum of bricks in different rows are the same and won't exceed INT_MAX.

* 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.

*

*/

public class BrickWall554 {

public int leastBricks(List<List<Integer>> wall) {

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i<wall.size(); i++) {

List<Integer> row = wall.get(i);

int sum = 0;

for (int j = 0; j<row.size()-1; j++) {

sum += row.get(j);

map.put(sum, map.getOrDefault(sum, 0) + 1);

}

}

int res = 0;

for (Integer v: map.values()) {

res = Math.max(res, v);

}

return wall.size()-res;

}

}