• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

LeetCode question Next Greater Element I Runtime error

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.




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!
 
Rancher
Posts: 508
15
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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:
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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
Rancher
Posts: 508
15
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
John Matthews
Rancher
Posts: 508
15
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Glad you managed to fix it.

Just couple of follow-ups - you've re-written your loops as:
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.
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Is that a spider in your hair? Here, threaten it with this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic