I DON'T THINK THERE IS A BETTER PERSON THAN ME TO ANSWER THIS QUESTION


  • 108

    We want to cut from the edge of the most common location among all the levels, hence using a map to record the locations and their corresponding occurrence. Most importantly, Mexico will pay for it! (I wish)

    public class Solution {
        public int leastBricks(List<List<Integer>> wall) {
            if(wall.size() == 0) return 0;
            int count = 0;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(List<Integer> list : wall){
                int length = 0;
                for(int i = 0; i < list.size() - 1; i++){
                    length += list.get(i);
                    map.put(length, map.getOrDefault(length, 0) + 1);
                    count = Math.max(count, map.get(length));
                }
            }
            return wall.size() - count;
        }
    }

  • 0
    Y
    This post is deleted!

  • 2
    X

    How about this:

    public int leastBricks(List<List<Integer>> wall) {
        final Map<Integer, Integer> occursMap = new HashMap<>();
        
        for (List<Integer> row : wall) {
            for (int i = 0, to = row.size() - 1, sum = 0; i < to; i++) {
                sum += row.get(i);
                occursMap.put(sum, occursMap.getOrDefault(sum, 0) + 1);
            }
        }
        
        return wall.size() - occursMap.values().stream().mapToInt(i -> i).max().orElse(0);
    }
    

  • 1

    @DonaldTrump terrific! I added an additional check at the end of your nested for-loop that sped my solution up to 85%:
    if (count == wall.size()) return 0;


  • 1

    lmfaoooooooooooo


  • 1
    J

    Totally agree with your title.


  • 0
    S

    hey , can anyone explain how to come up with this solution? I am still confused about this problem. What does hashmap store??


  • 2

    @shaunzeng HashMap stores the frequency of edges at different locations. The location with largest number of edges will have a vertical line cross the least number of braicks.


  • 3
    C

    You definitely played Donald well.


  • 0
    D

    @DonaldTrump said in I DON'T THINK THERE IS A BETTER PERSON THAN ME TO ANSWER THIS QUESTION:

    return wall.size() - count;

    took me a while to understand this line.! Awesome!


  • 0
    T
    This post is deleted!

  • 1
    F

    Same idea. Before I seeing your solution, I think my solution is the best. HaHa~

    public class Solution {
        public int leastBricks(List<List<Integer>> wall) {
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int i = 0;i<wall.size();i++){
                int sum = 0;
                for(int j = 0;j<wall.get(i).size()-1;j++){
                    int num = wall.get(i).get(j);
                    sum += num;
                    map.put(sum,map.getOrDefault(sum,0)+1);
                }
            }
            int max = 0;
            for(int value:map.values()){
                max = Math.max(max,value);
            }
            return wall.size()-max;
        }
    }
    

  • 1
    K

    Had exactly the same idea as yours!!! But ya, your topic title name is better than mine ;)

    public int leastBricks(List<List<Integer>> wall) {
            int max = Integer.MIN_VALUE;
            int sum = 0;        
            Map<Integer, Integer> map = new HashMap<>();
            for(List<Integer> l : wall) {
                sum = 0;
                l.remove(l.size()-1);
                for(int i : l) {
                    sum += i;
                    map.put(sum, map.getOrDefault(sum,0)+1);
                    max = Math.max(max, map.get(sum));
                }
            }
            return (max==Integer.MIN_VALUE)?wall.size():wall.size()-max;
        }
    

  • 0
    W

    Attracted by your title, Great President Trump build the Mexican Wall, Jesus!


  • 0
    S

    @dreamer92 Would you be able to explain what the line is really doing? The count is the maximum number of bricks crossed taking into consideration all vertical lines (I think), so is it that the max number of bricks that might be crossed - the maximum number of bricks that actually can be crossed = the minimum number of bricks required for crossing? I am not too sure why this works.


  • 1
    H

    @synchronizer "count", possibly better named by "maxEdges", is the maximum number of edges that pass through a single x coordinate. This is the path that we want to take when we are getting the solution, because we avoid crossing through the most number of rows.

    So say after the for loops, count is set to 5. This means that if we take that path, we avoid 5 rows. Say the total number of rows is 7. We know that since we avoid 5 rows, the number of rows that we pass through is equal to

    wall.size() - count
    

    AKA

    "Number of rows" - "Max edges that pass through a single x coordinate"

  • 0
    S

    Love the title! Lmao


  • 0
    A

    Exactly the same idea.

    class Solution {
        public int leastBricks(List<List<Integer>> wall) {
            Map<Integer,Integer> map  = new HashMap<>();
            int max = 0;
            for(int i = 0 ; i<wall.size();i++){
                int sum  = 0;
                for(int j = 0; j < wall.get(i).size() - 1 ; j++ ){          //-1 because the last one is the most right. it does not count
                    sum += wall.get(i).get(j);
                    map.put( sum , map.getOrDefault( sum , 0) + 1 );
                    max = Math.max( max , map.get(sum) );
                }
            }
            return wall.size() - max;
        }
    }
    

  • 0
    G

    Cannot agree with you Donald. LOL


  • 0

    +1 jus because you think algorithm to make mexicans pay!


Log in to reply
 

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