LeetCode question Next Greater Element I Runtime error

[josh yen]

Hi this is my first time on CodeRanch!
LeetCode question:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.


In my solution I used a stack to hold the element i wanted to compare, and recorded their next greatest elements in a map.

class Solution { public:    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {        stack<int> s;        unordered_map<int,int> nextgreatest;                for(int i = 0; i < nums2.size(); i++)        {            while(!s.empty())            {                if(s.top() < nums2[i]){                    nextgreatest[s.top()] = nums2[i];                    s.pop();                }                nextgreatest[s.top()] = -1;            }            s.push(nums2[i]);        }                vector<int> result;        for(int j = 0; j < nums1.size(); j++)        {            result.push_back(nextgreatest.at(nums1[j]));        }        return result;            } };


This is my code, and I received this runtime error:
Line 171: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0ba for type 'int', which requires 4 byte alignment (stl_deque.h)
0xbebebebebebec0ba: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_deque.h:180:16


I am confused what reference binding to misaligned address would mean here, any help would be appreciated thanks so much!

[John Matthews]

Hi Josh

I can compile your code using g++ -Wall -std=c++11 and just get a couple of warnings about signed/unsigned comparison (your for() loop variables are signed but size() is unsigned).

Although I can see you are getting a runtime error - perhaps it's something in the calling code. Can you show that as well?

[josh yen]

Hi John,
Thanks so much for your help. This was on leetcode, so unfortunately they did not provide what was in the calling code, but only provided examples of input/output:

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
   For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
   For number 1 in the first array, the next greater number for it in the second array is 3.
   For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
   For number 2 in the first array, the next greater number for it in the second array is 3.
   For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

This probably is not enough info, but thank you anyways!

[josh yen]

Also a general question with c++, does runtime error usually mean something is wrong in the driver? And compile error usually means an issue with the code in your files? Or does it all depend on situations. I am not too experienced with projects in general, thank you!

[John Matthews]

josh yen wrote:This probably is not enough info, but thank you anyways!

It is - I wrote my own calling code, using the Example 1 inputs you've given, and when I ran it I got a segmentation fault - a runtime error. I suspect it's the same underlying error as the one you've quoted, but some additional run-time checking has been enabled to give your error message.

If it was my code I would now start adding the C++ equivalent of C printf statements (I'm a C programmer) to find out where it's going wrong. I don't know anything about 'LeetCode', and I'm too lazy to look it up - does it allow you to do that?

My calling code - apologies for the C-ness:

int main()
{
    Solution sol;
    vector<int> nums1, nums2;

    nums1.push_back(4);
    nums1.push_back(1);
    nums1.push_back(2);

    nums2.push_back(1);
    nums2.push_back(3);
    nums2.push_back(4);
    nums2.push_back(2);

    vector<int> res = sol.nextGreaterElement(nums1, nums2);

    printf("res: ");

    for (unsigned i = 0; i < res.size(); i++)
        printf(" %d", res[i]);

    printf("\n");

    return 0;
}

[John Matthews]

josh yen wrote:Also a general question with c++, does runtime error usually mean something is wrong in the driver? And compile error usually means an issue with the code in your files? Or does it all depend on situations. I am not too experienced with projects in general, thank you!

I think "it all depends" covers it nicely

[josh yen]

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> s;
        unordered_map<int,int> nextgreatest;
        
        for(int i = 0; i < nums2.size(); i++)
        {
            while(!s.empty())
            {
                if(s.top() < nums2[i]){
                    nextgreatest[s.top()] = nums2[i];
                    s.pop();
                }
                nextgreatest[s.top()] = -1;
                cout<<"test1";
            }
            s.push(nums2[i]);
            
            
        }
        
        vector<int> result;
        for(int j = 0; j < nums1.size(); j++)
        {
            result.push_back(nextgreatest.at(nums1[j]));
        }
        return result;
        
    }
};

I tested print statements and it seems like the first time "test1" does not print is on line 16. When i put it anywhere before line 16, it prints, but not after. I'm suspecting there is an issue with putting the value -1 into the map, but i'm not sure why. Would this have something to do with signed and unsigned?

[John Matthews]

With my own printfs, when i is 1, it does s.pop() inside the 'if' leaving s empty. But then it does s.top() after the 'if', and if s is empty, that's an error.

[josh yen]

Hi John thanks so much for your help! I was finally able to figure it out! I realized there were some small issues with edge cases and some indexing with the for loop and the stack error you mentioned. This code now works with all possible scenarios. Also printing was super useful, it was a great way to get better at debugging.
Thanks so much for your help I really appreciate it!

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> s;
        unordered_map<int,int> nextgreatest;
        vector<int> result;
        
        if(nums1.empty()){
            return result;
        }
        
        for(int i = 0; i <= nums2.size() - 1; i++)
        {
            while(!s.empty())
            {
                if(s.top() < nums2[i]){
                    nextgreatest[s.top()] = nums2[i];
                }
                else if(s.top() > nums2[i]){
                    for(int j = i; j <= nums2.size() - 1; j++)
                    {
                        if(s.top() < nums2[j]){
                            nextgreatest[s.top()] = nums2[j];
                            break;
                        }
                        else
                            nextgreatest[s.top()] = -1;  
                    }
                    
                }    
                s.pop();
            }
            
            s.push(nums2[i]);           
        }
        
        nextgreatest[s.top()] = -1; 
        //cout << nextgreatest.at(nums1[nums1.size()-1]);
        //s.pop();
        
        
        for(int j = 0; j <= nums1.size() - 1; j++)
        {
            result.push_back(nextgreatest.at(nums1[j]));
        }
        return result;
        
    }
};

[John Matthews]

Glad you managed to fix it.

Just couple of follow-ups - you've re-written your loops as:

for(int i = 0; i <= nums2.size() - 1; i++)

Apart from the issue that you're still comparing signed (i) with unsigned (nums2.size()), which should be avoided if possible/practical, the way you wrote it originally is better ie.

for(int i = 0; i < nums2.size(); i++)

It's simpler - avoids the subtraction - and most programmers would recognize that as the 'standard' way to iterate over 0..size-1 values.

But also there's your Solution class. The calling code has to define a Solution variable (or 'object') in order to use the methods. But the variable itself doesn't have any data, and you shouldn't need it. Unfortunately I don't have enough C++ experience to know what the best approach is, but I suspect it involves static methods, or perhaps a static class if there is such a thing? I know static methods don't operate on objects of the class they belong to, and I think that's what you want here - you would just call Solution::nextGreaterElement(nums1, nums2), without needing to define a Solution variable.

This might be stuff which you haven't covered yet in your lessons (or whatever), in which case apologies and ignore.

[josh yen]

Thanks so much for the follow-up these are very useful to know! And i'll do some research on the different types of classes for different approaches. Again I really appreciate your help thank you.