1

https://leetcode.com/problems/largest-number/

When I was solving the above problem, I came across the case where std::sort() was giving me a runtime error, but replacing it with std::stable_sort() then there was no runtime error. Why?

Line is highlighted with the arrow sign on right

Code:

class Solution {
public:
    string reverse(string str)
    {
        int n=str.length();
        for(int i=0;i<n/2;i++)
        {
            swap(str[i],str[n-i-1]);
        }
        return str;
    }

    static bool comp(string s1,string s2)
    {
        int min_val=min(s1.length(),s2.length());
        int i=0;
        bool flag=false;
        for(;i<min_val;i++)
        {
            if((s1[i]-'0')==(s2[i]-'0'))
            {
                flag=true;
                continue;
            }

            return (s1[i]-'0')>(s2[i]-'0');
        }

        if(flag==true && s1.length()==s2.length())
        {
            return s1==s2;
        }

        string s1_temp=s1;
        string s2_temp=s2;
        s1_temp+=s2;
        s2_temp+=s1;

        return s1_temp>s2_temp;
    }

    string largestNumber(vector<int>& nums)
    {
        string str="";
        vector<string> inp;

        for(int i=0;i<nums.size();i++)
        {
            string temp="";
            long long int num=nums[i];
            if(num!=0)
            {
                while(num!=0)
                {
                    temp+=((num%10)+'0');
                    num/=10;
                }
            }
            else
            {
                temp+=(num+'0');
            }

            inp.push_back(reverse(temp));
        }

        stable_sort(inp.begin(),inp.end(),comp); // <-- This Line

        string res="";

        for(int i=0;i<inp.size();i++)
        {
            res+=inp[i];
        }
        cout<<"yes"<<endl;
        if(res[0]=='0')
        {
            return "0";
        }

        return res;
    }
};

TestCase:

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Can anybody give me the reason why this happened?

11
  • What was the error with regular sort? Commented May 27, 2020 at 6:03
  • Why do you need a custom compare function? Can you not leave comp away entirely? Commented May 27, 2020 at 6:06
  • Please edit and show a minimal reproducible example. Commented May 27, 2020 at 6:20
  • ** Following was the run time error **: Line 431: Char 55: runtime error: pointer index expression with base 0xbebebebebebebebe overflowed to 0x7d7d7d7d7d7d7d7c (basic_string.h)
    – VK Singh
    Commented May 27, 2020 at 6:25
  • 1
    Your code is incomplete. Where is main? Where are your #includes? Commented May 27, 2020 at 6:27

1 Answer 1

1

This is actually a very interesting bug! I have not tested whether this is a leetcode specific issue, but running this code with sort() on leetcode, we get the following error:

Line 431: Char 55: runtime error: pointer index expression with base 0xbebebebebebebebe overflowed to 0x7d7d7d7d7d7d7d7c (basic_string.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/basic_string.h:440:55

which seems to suggest that we're running out of memory for some reason. The fact that this code works with stable_sort() but not sort() suggests that this might have something to do with the fact that "stable_sort preserves the relative order of the elements with equivalent values" (http://www.cplusplus.com/reference/algorithm/stable_sort/).

The line of code where this is relevant is here

if(flag==true && s1.length()==s2.length())
{
    return s1==s2;
}

And indeed if we change this to

if(flag==true && s1.length()==s2.length())
{
    return s1!=s2;
}

which doesn't affect the results, because if, at this point, flag == true and both strings have the same length, then they are both equivalent, and swapping string positions does not affect the outcome.

BUT we bypass the error. @Vikram Keswani I hope this solves your issue. Personally I would also just replace the code in the comp() function with return s1 > s2; which should provide the same behaviour as the code that you have.

p.s. I shall leave the pieces of the puzzle here, but if someone more experienced (or when I find more time) would like to investigate this mysterious memory issue further, that'd be great.

Incidentally, the minimum length input required to reproduce this error on leetcode is [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] which is 17 0's (a strange number).

1
  • 1
    Yes, this is the answer. std::sort requires the comparator to fulfill certain requirements. Specifically it must be a strictly weak ordering, and must fulfill comp(a,a)==false. In other words, an element must not compare true with itself. OP's function does not fulfill this (comp("0", "0") returns true). Your fix flips this and makes the comparator compliant with the requirements.
    – Frodyne
    Commented May 27, 2020 at 7:45

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