|
34 | 34 | 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. |
35 | 35 | */ |
36 | 36 | publicclass_554 { |
37 | | -//credit to: https://leetcode.com/articles/brick-wall/ |
| 37 | +publicstaticclassSolution1 { |
| 38 | +/** |
| 39 | + * credit: https://leetcode.com/articles/brick-wall/ |
| 40 | + * |
| 41 | + * we make use of a HashMap |
| 42 | + * map which is used to store entries in the form: |
| 43 | + * (sum,count). Here, |
| 44 | + * sum refers to the cumulative sum of the bricks' widths encountered in the current row, and |
| 45 | + * count refers to the number of times the corresponding sum is obtained. Thus, |
| 46 | + * sum in a way, represents the positions of the bricks's boundaries relative to the leftmost boundary. |
| 47 | + * |
| 48 | + * This is done based on the following observation: |
| 49 | + * We will never obtain the same value of sum twice while traversing over a particular row. |
| 50 | + * Thus, if the sum value is repeated while traversing over the rows, it means some row's brick boundary coincides with some previous row's brick boundary. |
| 51 | + * This fact is accounted for by incrementing the corresponding count value. |
| 52 | + * But, for every row, we consider the sum only upto the second last brick, since the last boundary isn't a valid boundary for the solution. |
| 53 | + */ |
38 | 54 |
|
39 | | -/**we make use of a HashMap |
40 | | - map which is used to store entries in the form: |
41 | | - (sum,count). Here, |
42 | | - sum refers to the cumulative sum of the bricks' widths encountered in the current row, and |
43 | | - count refers to the number of times the corresponding sum is obtained. Thus, |
44 | | - sum in a way, represents the positions of the bricks's boundaries relative to the leftmost boundary. |
45 | | -
|
46 | | - This is done based on the following observation: |
47 | | - We will never obtain the same value of sum twice while traversing over a particular row. |
48 | | - Thus, if the sum value is repeated while traversing over the rows, it means some row's brick boundary coincides with some previous row's brick boundary. |
49 | | - This fact is accounted for by incrementing the corresponding count value. |
50 | | -
|
51 | | - But, for every row, we consider the sum only upto the second last brick, since the last boundary isn't a valid boundary for the solution.*/ |
52 | | - |
53 | | -publicintleastBricks(List<List<Integer>>wall) { |
54 | | -Map<Integer,Integer>map =newHashMap(); |
55 | | -for (List<Integer>row :wall) { |
56 | | -intsum =0; |
57 | | -for (inti =0;i <row.size() -1;i++) { |
58 | | -//NOTE: i < row.size()-1 |
59 | | -sum +=row.get(i); |
60 | | -if (map.containsKey(sum)) { |
61 | | -map.put(sum,map.get(sum) +1); |
62 | | - }else { |
63 | | -map.put(sum,1); |
| 55 | +publicintleastBricks(List<List<Integer>>wall) { |
| 56 | +Map<Integer,Integer>map =newHashMap(); |
| 57 | +for (List<Integer>row :wall) { |
| 58 | +intsum =0; |
| 59 | +for (inti =0;i <row.size() -1;i++) { |
| 60 | +//NOTE: i < row.size()-1 |
| 61 | +sum +=row.get(i); |
| 62 | +if (map.containsKey(sum)) { |
| 63 | +map.put(sum,map.get(sum) +1); |
| 64 | + }else { |
| 65 | +map.put(sum,1); |
| 66 | + } |
64 | 67 | } |
65 | 68 | } |
| 69 | +intresult =wall.size(); |
| 70 | +for (intkey :map.keySet()) { |
| 71 | +result =Math.min(result,wall.size() -map.get(key)); |
| 72 | + } |
| 73 | +returnresult; |
66 | 74 | } |
67 | | -intresult =wall.size(); |
68 | | -for (intkey :map.keySet()) { |
69 | | -result =Math.min(result,wall.size() -map.get(key)); |
70 | | - } |
71 | | -returnresult; |
72 | 75 | } |
73 | | - |
74 | 76 | } |