5
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Hello, I highly suggest you to edit your question and add a language tag (javascript, ect) to your question; you will have more answers this way, in my opinion. \$\endgroup\$
    – Doi9t
    Nov 1, 2020 at 13:28
  • 1
    \$\begingroup\$ Can you link to the original question? \$\endgroup\$ Nov 4, 2020 at 4:39
  • \$\begingroup\$ Also, can you give a quick high-level explanation of how you are thinking about the problem, and how you solved it? I'm having trouble seeing how this code relates to the problem as I understand it. If you haven't verified your solution is correct on hackerrank, please do so first. We can only comment on style and speed. You're expected to have a correct solution already. \$\endgroup\$ Nov 4, 2020 at 4:42
  • \$\begingroup\$ Oh, didn't know that. Which community should I go instead to ask such question? There is no link to the original question as the question came up while I was trying to earn a certificate. This solution definitely works but uses unnecessarily too much space. I have written a new solution here: github.com/hbjORbj/interview_prep/blob/master/Second%2099/… \$\endgroup\$
    – Benny Joo
    Nov 4, 2020 at 21:16
  • \$\begingroup\$ We are making guillotine cuts here. Given e.g. a cardboard rectangle you slice, evaluate, and permanently discard the smaller portion. Keep repeating till having exhausted the input instructions. You may find it convenient to write a single helper function that accepts is_vertical_cut and which operates on (w, h) for one cut orientation and on (h, w) for the other orientation, always returning the (w, h) size of the surviving rectangle. \$\endgroup\$
    – J_H
    Nov 11, 2023 at 17:26

1 Answer 1

-2
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ May 21, 2021 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.