Simple "0ms" C++ solution using min and max- updated again to avoid overflow


  • 12
    D

    The original version wasn't passing anymore because of new test cases that cause overflow. So now we're avoiding computing the differences below if the result will be negative. This avoids overflow in cases where the rectangles are far apart. It looks like this is basically the same thing that @shw1500 was suggesting, but you don't need the extra max function on the outside.

    The return statement is based on comments from @StefanPochmann. We want to avoid forming the sum area(R1) + area(R2). This avoids overflow in cases where area(R1) + area(R2) will overflow, but area(R1) + area(R2) - overlap(R1, R2) fits in an int. There aren't any test cases for this. Add some maybe? Edit: There are test cases for this, but the overflow didn't matter.

    New version- avoids overflow when area(R1) + area(R2) overflows but the answer shouldn't.

    class Solution {
        public:
            int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
                int overlap_width = min(C, G) > max(A, E) ? min(C, G) - max(A, E) : 0; 
                int overlap_height = min(D, H) > max(B, F) ? min(D, H) - max(B, F) : 0;
                return ((C - A) * (D - B) - overlap_width * overlap_height) + (G - E) * (H - F); // order avoids overflow
            }
        };
    

    Second version- avoids overflow when rectangles are far apart

    class Solution {
    public:
        int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
            int overlap_width = min(C, G) > max(A, E) ? min(C, G) - max(A, E) : 0; 
            int overlap_height = min(D, H) > max(B, F) ? min(D, H) - max(B, F) : 0;
            return (C - A) * (D - B) + (G - E) * (H - F) - overlap_width * overlap_height;
        }
    };
    

    Old version- overflows for some inputs where the rectangles are far apart.

    class Solution {
    public:
        int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
            int overlap_width = max(min(C, G) - max(A, E), 0), overlap_height = max(min(D, H) - max(B, F), 0);
            return (C - A) * (D - B) + (G - E) * (H - F) - overlap_width * overlap_height;
        }
    };

  • 0
    A

    Nice solution but are you making following assumption?

    1. (C - A) * (D - B) + (G - E) * (H - F) won't cross range of int
    2. Rectangles are parallel to x and y axis

  • 0
    D

    Yes, I'm basically making these assumptions. I think we're only considering rectangles parallel to the axes. If they weren't, the formula would be a little more complicated but the basic idea would be similar. With regard to overflow, it's possible that (C - A) * (D - B) + (G - E) * (H - F) would overflow, but the final result shouldn't. In general we can't enforce the order in which the compiler evaluates the terms in the sum, but we could probably write a different expression to avoid overflow...


  • -3
    S

    adding some judgment can help pass all cases;

    class Solution {
    public:
        int max(int a,int b){
            return a>b?a:b;
        }
        int min(int a,int b){
            return a>b?b:a;
        }
        int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
            int w=max(min(C,G)>max(A,E)?min(C,G)-max(A,E):0,0),h=max(min(D,H)>max(B,F)?min(D,H)-max(B,F):0,0);
            return (C-A)*(D-B)+(G-E)*(H-F)-w*h;
        }
    };
    

  • 0

    That is utterly unreadable. I even have to scroll a lot just to see it all. Not good.


  • 0

    Of course they're axis-parallel. If not, then not only the formula would be more complicated but also the input! @deck: You can enforce any order by writing it in that order. All those operations are evaluated left-to-right. Also, while the above overflow doesn't matter, your solution doesn't get accepted (anymore) because of overflow in the overlap calculation. Try submitting it again.


  • 0
    D

    What I was thinking about when I made the comment about order was the last expression. Here I was kind of lazy but this is not the best way to do it. It is possible that area(R1) + area(R2) overflows, but area(R1) + area(R2) - overlap(R1, R2) fits in an int (or whatever type you're using). We can't rely on the compiler to evaluate terms in that sum in any particular order. We really should avoid "double counting" the overlap and then subtracting it. So we should add the pieces of R1 not in the overlap, the pieces of R2 not in the overlap, and then add the overlap. I haven't worked out the expression yet but maybe someone else wants to take a shot?


  • 0

    The evaluation order is specified in the standard, why do you say we can't rely on it?

    And area(R1) - overlap(R1, R2) + area(R2), i.e., first subtracting the overlap, is safe from overflows during those two operations. Unless you're right about the evaluation order not reliably being left-to-right, which I doubt. But even then, simply (area(R1) - overlap(R1, R2)) + area(R2) should really guarantee it. Don't tell me the compiler ignores parentheses :-)


  • 0
    D

    Relying on some order of evaluation causes a lot of bugs. In general you can't. Here's what Stroustrup has to say about it in The C++ Programming Language 4th Edition (page 259):

    "The order of evaluation of subexpressions within an expression is undefined. In particular, you cannot assume that the expression is evaluated left-to-right. For example:

    int x = f(2) + g(3) // undefined whether f() or g() is called first

    Better code can be generated in the absence of restrictions on expression evaluation order. However, the absence of restrictions on evaluation order can lead to undefined results. For example:

    int i = 1;
    v[i] = i++; // undefined result

    The assignment may be evaluated as either v[1] = 1 or v[2] = 1 or may cause some even stranger behavior. Compilers can warn against such ambiguities. Unfortunately, most do not, so be careful not to write an expression that both reads and writes an object, unless it does so using a single operator that makes it well defined, such as ++ and +=, or explicitly express sequencing using , (comma), &&, or ||.

    The operators , (comma), && (logical and), and || (logical or) guarantee that their left-hand operand is evaluated before their right-hand operand..."

    So you can rely on , (comma), &&, and || to evaluate their arguments in order, but that's basically it (well, also the conditional expression (? :) and function call operators). You also can't rely on arguments to a function to be evaluated in any particular order, which is another source of bugs and exception unsafe code...

    The issue is that the subexpressions have equal precedence, so it's not an issue of order of operations. The compiler is granted quite a bit of freedom here. Consequently, the compiler may also optimize away or re-associate parenthesis by default, but there could be compiler options available to prevent this.


  • 0

    No. You're reading that wrong. How did you not notice that f(2) + g(3) even only has one operation? He's talking about the order of evaluating the SUBexpressions / operaNDS. Not about the expression and its operators. From page 257 of the same book:

    Unary operators and assignment operators are right-associative; all others are left-associative.
    For example, a=b=c means a=(b=c) whereas a+b+c means (a+b)+c.

    In f(2) - g(3) + h(4) it's undefined in which order f(2), g(3) and h(4) get evaluated, but it is defined that - is evaluated before +.


  • 0
    D

    OK I see what you're saying now. The compiler parses the expression f(2) - g(3) + h(4) like (f(2) + g(3)) + h(4). It should whether or not their are parenthesis. So the result of the subtraction has to be available before the addition is happens. I'm going to update the solution...

    Is there any chance that the parenthesis could be optimized away at some point long after the parse tree is built? I think that's what I'm still worried about, but I can't find a resource on that.


  • 0

    As the order is standardized and you're not causing overflow, no, I don't think the correct behavior could be "optimized away". That would be violating the standard.

    Apparently some C/C++ compilers turn for example x < x+1 into true (or 1) if x is an int because only overflow could make it false and in C/C++, overflow behavior for int isn't defined so the compiler is allowed to do that. So if I use x < x+1 and expect it to be false if x is MAX_INT, then the compiler might mess that up for me. But that's because I'm trying to use something that is undefined. It should never break a safe correct calculation that only relies on defined behavior.

    I see your answer now says "There aren't any test cases for this. Add some maybe?". You're wrong. There is such a case. You just don't notice it because after the addition overflows, the following subtraction overflows right back, to the correct end result. That's not guaranteed by the standard, but it's pretty much a fact. That's why I earlier said that "[that] overflow doesn't matter". Also see this thread.


  • 0

    See this question and its answers and their links for a bit more about integer overflow in C/C++.


  • 0
    D

    That's interesting that the test cases worked. Once the signed intermediate result overflows can't we not rely on the answer anymore? It overflows back here, but in general unsigned overflow is undefined as explained in the link. What if we just changed the area computations to unsigned, then returned the requested signed result at the end? Since the unsigned computations are done modulo 2^n overflowing and then subtracting back would seem OK.


  • 0

    Well you can't rely on it in the sense of it being guaranteed by the standard, but you pretty much can rely on it in practice. Just don't rely on it for anything critical :-). Like someone said on that StackOverflow page:

    "undefined behaviour" doesn't mean "doesn't work"

    With most hardware/compilers, signed integers also work "modulo 2^n". If I'm not mistaken, then in Java it's even "defined" to be that way:

    If an integer addition overflows, then the result is the low-order bits of the mathematical sum as represented in some sufficiently large two's-complement format.


  • 0
    S

    Thx for your comment,the code has been updated.


  • 0

    Still a bit wide and hard to read, but a lot better :-). Why do you redefine max and min, though? And why do you still max with zero after already having ensured that the value is non-negative?


  • 0
    S

    Redefinition of max and min is not necessary.I defined them because I didn't know those two functions are included before.

    The second question:
    For two int in a 32 bits machine : A and B. When A>B, A-B is not always non-negative,for example A=1500000000 and B=-1500000000,
    A-B = -1294967296,so the redundant check is just to prevent overflow.


  • 0

    But if you get 1500000000 and -1500000000 there, then the overlap is actually 3000000000 wide (or high), not 0. Zero is wrong (although it doesn't matter).

    Also, that can only happen if both of the two given rectangles are at least 3000000000 wide (or high), so they must both have height zero because we're told that the result fits in an int. And then h will be zero, so the overflow in w won't matter.

    That said, my question was bad and you're right in your reply in general. Thanks.


  • 0
    Q
    This post is deleted!

Log in to reply
 

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