Why is it exceeding runtime complexity for perfect rectangle?


  • 0
    D

    Hi ,

    I ran my code for perfect rectangle on Eclipse and it is working fine however it is exceeding runtime on Leetcode.

    Could someone tell me what the problem is? It would be helpful if the admin could take a look at this code

    public class Solution {
    public boolean isRectangleCover(int[][] rectangles) {

        //Base case: if  less than 2 rows are present, return true
        if(rectangles.length<2)
            return true;
            
        //General case: if 2 or more rows are present
        int minRow=Integer.MAX_VALUE;
        int maxRow=Integer.MIN_VALUE;
        int minCol=Integer.MAX_VALUE;
        int maxCol=Integer.MIN_VALUE;
        
        //for loops to iterate through the matrix
        for(int i=0;i<rectangles.length;i++)
        {
            for(int j=0;j<rectangles[0].length;j++)
            {
                //Case 1: if row value, check if min row or max row
                if((j%2)==0)
                {
                    if(rectangles[i][j]<minRow)
                    {
                        minRow=rectangles[i][j];
                    }
                    
                    if(rectangles[i][j]>maxRow)
                    {
                        maxRow=rectangles[i][j];
                    }
                }
                //Case 2: if column value, check if min column or max column
                else
                {
                    if(rectangles[i][j]<minCol)
                    {
                        minCol=rectangles[i][j];
                    }
                    
                    if(rectangles[i][j]>maxCol)
                    {
                        maxCol=rectangles[i][j];
                    }
                }
                
            }
            
        }
        
        //find the size of the boolean matrix
        int columnSize=maxRow-minRow;
        
        int rowSize=maxCol-minCol;
        
        //create a boolean matrix with the bound of minRow, min Col, maxRow, MaxCol
        boolean[][] visited=new boolean[rowSize][columnSize];
        
        int counter=0;
        
        //mark all the areas which are part of the rectangle
        for(int i=0;i<rectangles.length;i++)
        {
            //mark upper and lower row and column bounds of each rectangle
            int lowerColumnIndex=rectangles[i][0]-minRow;
            int lowerRowIndex=rectangles[i][1]-minCol;
            
            int upperColumnIndex=rectangles[i][2]-minRow-1;
            int upperRowIndex=rectangles[i][3]-minCol-1;
            
            //if rectangle overlaps, return false, else update counter and loop through
            if(!visitTheMatrix(lowerRowIndex,upperRowIndex,lowerColumnIndex,upperColumnIndex,visited))
                return false;
            
            //update the value of counter
            counter+=(upperRowIndex-lowerRowIndex+1)*(upperColumnIndex-lowerColumnIndex+1);
            
        }
        
        //if counter is same as size of matrix, return true, else false
        if(counter==(rowSize*columnSize))
            return true;
        else
            return false;
        
    }
    
    public boolean visitTheMatrix(int row1,int row2,int col1, int col2,boolean[][] visited)
    {
        //traverse through these bounds in the boolean matrix
        for(int i=row1;i<=row2;i++)
        {
            for(int j=col1;j<=col2;j++)
            {
                //if already visited , return false
                if(visited[i][j])
                    return false;
                
                //else mark visited
                visited[i][j]=true;
                
                
            }
        }
        
        return true;
    }
    

    }


Log in to reply
 

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