BitSet Memory Maxed Out


  • 0
    C

    I tried to store every square that is filled in as a 1 bit in a BitSet because that was the first solution that came to me. If a square gets filled twice, return false. Otherwise check if every square has been filled with comparing the area to the amount of squares that have been filled in. Pretty sure this works but keep hitting memory limit errors.

    Any way to simplify further or is this approach just too high complexity for it to work on the larger test cases? Thanks for any help!

    import java.util.BitSet;
    
    public class Solution {
        public boolean isRectangleCover(int[][] rectangles) {
            int xmin = getMinX(rectangles), ymin = getMinY(rectangles), xmax = getMaxX(rectangles), ymax = getMaxY(rectangles);
            int count = 0;
           
            int xadj = 0, yadj = 0;
            if (xmin < 0)
                xadj = -xmin;
            if (ymin < 0)
                yadj = -ymin;
                
            BitSet bs = new BitSet((xmax - xmin) * (ymax - ymin));
            for(int r = 0; r < rectangles.length; r++) {
                int[] cur = rectangles[r];
                for(int y = cur[1]; y < cur[3]; y++) {
                    for(int x = cur[0]; x < cur[2]; x++) {
                        if(bs.get(((y + yadj) * (xmax - xmin)) + x + xadj) == true)
                            return false;
                            
                        bs.set(((y + yadj) * (xmax - xmin)) + x + xadj, true); 
                        count++;
                    }
                }
            }
            
            int sum = (xmax - xmin) * (ymax - ymin);
            return count == sum;
        }
        
        public int getMinX(int[][] rectangles) {
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < rectangles.length; i++) {
                if(rectangles[i][0] < min)
                    min = rectangles[i][0];
            }
            return min;
        }
        public int getMinY(int[][] rectangles) {
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < rectangles.length; i++) {
                if(rectangles[i][1] < min)
                    min = rectangles[i][1];
            }
            return min;
        }
        public int getMaxX(int[][] rectangles) {
            int max = 0;
            for(int i = 0; i < rectangles.length; i++) {
                if(rectangles[i][2] > max)
                    max = rectangles[i][2];
            }
            return max;
        }
        public int getMaxY(int[][] rectangles) {
            int max = 0;
            for(int i = 0; i < rectangles.length; i++) {
                if(rectangles[i][3] > max) 
                    max = rectangles[i][3]; 
                
            }
            return max;
        }
    }
    

  • 0
    L

    The same idea as yours, "Memory Limit Exceeded"

    public class Solution {
        public boolean isRectangleCover(int[][] rectangles) {
            int left = Integer.MAX_VALUE, down = Integer.MAX_VALUE;
            int right = Integer.MIN_VALUE, up = Integer.MIN_VALUE;
            
            for (int i = 0; i < rectangles.length; i++) {
                left = Math.min(left, rectangles[i][0]);
                down = Math.min(down, rectangles[i][1]);
                right = Math.max(right, rectangles[i][2]);
                up = Math.max(up, rectangles[i][3]);
            }
            
            BitSet bs = new BitSet((right-left)*(up-down));;
            int count = 0;
            for (int i = 0; i < rectangles.length; i++) {
                for (int j = rectangles[i][0]; j < rectangles[i][2]; j++) {
                    for (int k = rectangles[i][1]; k < rectangles[i][3]; k++) {
                        if (bs.get((k-down)*(right-left)+j-left) == true) return false;
                        
                        bs.set((k-down)*(right-left)+j-left); ++count;
                    }
                }
            }
            return (count == (right-left)*(up-down)) ? true : false;
        }
    }
    

Log in to reply
 

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