Dumb question, but I couldn't figure out what's wrong with my bfs


  • 0
    J

    It should have passed many cases, while fails on a large test case:

    public class Solution {
        public int minArea(char[][] image, int x, int y) {
            LinkedList<int[]> queue = new LinkedList<>();
            HashSet<Integer> visited = new HashSet<>();
            queue.add(new int[]{x, y});
            int xMin = x, xMax = x, yMin = y, yMax = y;
            while(queue.size() > 0) {
                int[] curr = queue.poll();
                x = curr[0];
                y = curr[1];
                if(isValid(image, visited, x, y)) {
                    visited.add(Arrays.hashCode(new int[]{x, y}));
                    xMin = Math.min(x, xMin);
                    xMax = Math.max(x, xMax);
                    yMin = Math.min(y, yMin);
                    yMax = Math.max(y, yMax);
                    queue.add(new int[]{x + 1, y});
                    queue.add(new int[]{x - 1, y});
                    queue.add(new int[]{x, y + 1});
                    queue.add(new int[]{x, y - 1});
                }
            }
            
            return (yMax - yMin + 1) * (xMax - xMin + 1);
        }
        
        private boolean isValid(char[][] image, Set<Integer> visited, int x, int y) {
            return x >= 0 && x < image.length && y >= 0 && y < image[0].length
                    && image[x][y] == '1' && !visited.contains(Arrays.hashCode(new int[]{x, y}));
        }
    }
    

    Here is the case:

    ["000000000000000000000010000000000000000000000000000000000000000000000000000","000000000000000000000110000000000000000000000000000000000000000000000000000","000000000000000000011100000000000000000000000000000000000000000000000000000","000000000000000000111100000000000000000000000000000000000000000000000000000","000000000000000100111000000000000010001000000000100000000000000000000000000","000000000000011111011000000000000011111100000011110000101000000000000000000","000000000000011011111100100000000011111110001111100111111100000000000000000","000000000000000001111111110000001111111111011110100111111110000000000000000","000000000000000000110011111110000111111100011111110101111100000000000000000","000000000000000000000111111111110111111111111111111111111111000000000000000","000000000000000000000111111111111111111111111111111111111111000000000000000","000000000000000000000111111111111000111000001111111111111011000000000000000","000000000000000000011111101111111000111111111110010111111111100000000000000","000000000000000000010111111111111111111111100000000111111111011000000000000","000000000000000000000111101100100111110000100011100111111111111000000000000","000000000000000000000111111111111111110001111111101111111111111100000000000","000000000000000000001111111111111111111111101111111111111111111100000000000","000000000000000000001000011111111000001000001111111111111111111100000000000"]
    17
    63

  • 0
    C

    I think it's hashcode collision.
    Instead of using hashcode as the key, just simply change the visited position to another character.
    Nearly the same code as yours and AC.
    BTW...Don't use hashcode as key and binary search maybe the best solution.

    public class Solution {
    public int minArea(char[][] image, int x, int y) {
        LinkedList<int[]> queue = new LinkedList<>();
        //HashSet<Integer> visited = new HashSet<>();
        queue.add(new int[]{x, y});
        int xMin = x, xMax = x, yMin = y, yMax = y;
        while(queue.size() > 0) {
            int[] curr = queue.poll();
            x = curr[0];
            y = curr[1];
            if(isValid(image, x, y)) {
                image[x][y] = '*';
                xMin = Math.min(x, xMin);
                xMax = Math.max(x, xMax);
                yMin = Math.min(y, yMin);
                yMax = Math.max(y, yMax);
                queue.add(new int[]{x + 1, y});
                queue.add(new int[]{x, y + 1});
                queue.add(new int[]{x - 1, y});
                queue.add(new int[]{x, y - 1});
            }
        }
        return (yMax - yMin + 1) * (xMax - xMin + 1);
    }
    
    private boolean isValid(char[][] image, int x, int y) {
        return x >= 0 && x < image.length && y >= 0 && y < image[0].length && image[x][y] == '1';
    }
    

    }


Log in to reply
 

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