Largest rectangle areas after drawing boundaries

Question

I was asked the following question while trying to get a Hackerrank certificate. I couldn't solve on time but I now completed the solution. Can you please check if my solution seems good? Suggestions on improvement are appreciated.

Q: You have a rectangle of width w and height h. You will start to draw boundaries. The number of boundaries is given by the length of the given array, distance. isVertical[i] represents whether or not i-th boundary is vertical or not. 1 means vertical and 0 means horizontal. distance[i] tells the distance between your boundary and the rectangle. In case of a horizontal boundary, it represents the distance from the bottom of your rectangle, and in case of a vertical boundary, it represents the distance from the left of your rectangle.

You need to return the largest areas of your rectangle as an array after drawing each of your boundaries.

ex) w = 4, h = 4, isVertical = [0,1], distance = [3,1] After drawing the first boundary, the largest possible rectangle area is 12. After drawing the second boundary, the largest possible rectangle area is 9. You are not given a new rectangle for each boundary. You draw boundaries on the same rectangle.

You should return [12, 9].

My solution:

• I created one grid using a 2d-array and computed the largest possible rectangle area after each boundary is drawn by choosing the larger between the area taken up by the boundary and the current largest rectangle area minus the boundary area. I used the same, one grid to do computation for every boundary.

function largestArea(w, h, isVertical, distance) {
    if (isVertical.length !== distance.length) return null;
    if (w == 0 || h == 0) return 0;
    let grid = new Array(h).fill(0).map(() => new Array(w).fill()); // -1 represents areas of the original rectangle
    let largestArea = w*h;
    let areas = [];
    for (let i = 0; i < isVertical.length; i++) {
        let boundaryArea = 0;
        if (isVertical[i] == 1) {
            boundaryArea = drawVerticalBoundary(distance[i], grid); // distance[i] for vertical boundary is distance from the left
        } else {
            boundaryArea = drawHorizontalBoundary(h-distance[i], grid); // distance[i] for horizontal boundary is distance from the bottom
        }
        largestArea = Math.max(largestArea-boundaryArea, boundaryArea);
        areas.push(largestArea);
    }
    return areas;
}

function drawVerticalBoundary(maxCol, grid) {
    let area = 0;
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < maxCol; col++) { // area already taken by another boundary is not part of current boundary
            if (!grid[row][col]) {
                area++;
                grid[row][col] = 1;
            }
        }
    }
    return area;
}

function drawHorizontalBoundary(maxRow, grid) {
    let area = 0;
    for (let row = 0; row < maxRow; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (!grid[row][col]) { // area already taken by another boundary is not part of current boundary
                area++;
                grid[row][col] = 1;
            }
        }
    }
    return area;
}

Answer 1

I do have a solution for this question but apology because I am proficient in python please add the answer who can write the same logic in JS also. Thanks

what I have done is maintain array of width and height and get amximum width difference and height difference between adjcent location of H and W. which leads to maxArea of rectangle

This is not efficient solution as it was giving timelimit exceed on 3-4 test cases.so appreciate if anyone can optimize it.

def getMaxArea(w, h, isVertical, distance):
    # Write your code here
    def insort(test_list, k):
        for i in range(len(test_list)):
            if test_list[i] > k:
                break
        return test_list[:i] + [k] + test_list[i:]
        
    maxy = 0
    wline = [0,w]
    hline = [0,h]
    res = []
    for i in range(len(isVertical)):
        if isVertical[i]:
            wline = insort(wline, distance[i])
        else:
            hline = insort(hline, distance[i])
        wmax = 0
        hmax = 0
        for i in range(1,len(wline)):
            if wline[i] - wline[i-1] > wmax:
                wmax = wline[i] - wline[i-1]
        for i in range(1,len(hline)):
            if hline[i] - hline[i-1] > hmax:
                hmax = hline[i] - hline[i-1]
     
        res.append(hmax * wmax)
    return res