Question: Weird behaviour with max in C++

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	djm03178	153

I was trying out a problem (irrelevant) on LeetCode — 1372. Longest ZigZag Path in a Binary Tree. I posted this question on the forum but got no reply. Hence, I am asking the same question here.

I noticed some weird behaviour when using the max function. I took a max in two ways:

Solution 1: max(1 + a, 1 + b)

Solution 2: 1 + max(a, b)

Both of these do exactly the same task of getting the 1 + max. However:

Solution 1: — Runtime Error!
Solution 2: — Accepted

The full code is also given below:

Solution 1

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        return zigzag(root)[2];
    }
    
    vector<int> zigzag(TreeNode* node) {
        if(!node)
            return {-1, -1, -1};
        vector<int> left, right;
        left = zigzag(node->left);
        right = zigzag(node->right);
        int h = max(max(1 + left[1], 1 + right[0]), max(left[2], right[2]));
        return {1 + left[1], 1 + right[0], h};
    }
};

Solution 2

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        return zigzag(root)[2];
    }
    
    vector<int> zigzag(TreeNode* node) {
        if(!node)
            return {-1, -1, -1};
        vector<int> left, right;
        left = zigzag(node->left);
        right = zigzag(node->right);
        int h = max(1 + max(left[1], right[0]), max(left[2], right[2]));
        return {1 + left[1], 1 + right[0], h};
    }
};

The details for Solution 1 are given below:

Runtime Error Message: AddressSanitizer: stack-overflow on address 0x7ffee1685ab8 (pc 0x7f4840414c34 bp 0x7ffee1686300 sp 0x7ffee1685aa0 T0)
Failed Input

If you notice, the code for both of them is exactly the same except for line 13. Could someone please tell me why Solution 1 fails? It really makes no sense to me.

Thank you for all your help!

Comments (2)

Write comment?

Mustang98

5 years ago, # |

+56

Hi there!

Take a look at the following snippet:

Spoiler

class Solution {
public:
    int longestZigZag(TreeNode* root) {
        return zigzag(root)[2];
    }
    
    vector<int> zigzag(TreeNode* node) {
        if(!node)
            return {-1, -1, -1};
        vector<int> left, right;
        left = zigzag(node->left);
        right = zigzag(node->right);
        int h = max(1 + max(left[1], right[0]), max(left[2], right[2]));
        h = max(1 + max(left[1], right[0]), max(left[2], right[2]));
        return {1 + left[1], 1 + right[0], h};
    }
};

It's exactly your Solution 2, where I duplicated line 13, so actually it's the same code. However this version now gives RE, but if you comment unnecessary 14th line it will turn into AC.

So what's the problem here? It's definitely not with using max function. From this point, both your solutions are the same and correct.

Let's take a closer look at the error message. First of all, it says stack-overflow. I think you know what that means. Usually, stack size in online compilers is $$$256$$$ $$$MB$$$. If you look on your Solution 2 run report, you will see that it consumes $$$205$$$ $$$MB$$$, that's quite close to the limit. Now you can ask, how is that possible to consume so much memory? Obviously, the solution uses linear amount of memory, and restrictions on the input are quite low ($$$n\le50000$$$).

The answer to that question appears if you look at the other word in the error message. It says AddressSanitizer:.... It means that leetcode runs your solution under the sanitizer. It's a special tool that controls memory access of your program during runtime. And the important thing that you have to know about it, is that in order to make this control sanitizer uses a lot of additional memory and time. That's why, for example, Codeforces uses sanitizer only on small tests. In order to explain the exact differences between your solutions, you have to know, how the sanitizer works inside. I just can assume, that Solution 1 uses 2 temporary values instead of 1 in the Solution 2.

So the conclusion is that it's neither your fault nor max function's fault. Both solutions are correct and identical. The only problem is that the testing system uses sanitizer and one of the solutions was more lucky to fit in the limit.

Hope it helped and have a nice day :)

→ Reply

Mohammed-Shoaib

5 years ago, # ^ |

← Rev. 2 →

+11

Thank you for your reply!

Wow, this sure is really interesting to me. I never knew what AddressSanitizer actually does, but now I do! I also did not know CodeForces uses it for small test cases.

I can only imagine how long it must have taken you to provide such a detailed analysis. You explained everything really well and I appreciate your time and effort in checking this out!

This kept bothering me in the back of my head so it definitely helped me a lot. I am glad that I finally understand this, so thank you so much! I hope you have a nice day ahead too :)

Mohammed-Shoaib's blog