LeetCode next permutation Problem Runtime error
Karan Verma
74

When the following code was exectued with input [1,1] gave a run time error on leetcode platform but when i ran this code on my c++ enviornment on my computerwith the same input it ran successfully without any run-time error

,,,
class Solution {
public:

int partitionalgo(vector<int>& arr,int l,int h)
{
    int pivot=arr[l];
    int i=l;
    int j=h;
    while(i<j)
    {
        do
        {
            i++;
        }while(arr[i]<=pivot);
        do
        {
            j--;
        }while(arr[j]>pivot);
        if(i<j)
        {
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[l],arr[j]);
    return j;
}
void quicksort(vector<int>& arr,int l,int h)
{
    if(l<h)
    {
        int j=partitionalgo(arr,l,h);
        quicksort(arr,l,j);
        quicksort(arr,j+1,h);
    }
}



void nextPermutation(vector<int>& nums) 
{
    int h = 0;
    vector<int>::iterator i;
    for(i = nums.end() - 1; i>nums.begin(); i--)
    {
        if(*(i-1) < *i)
        {
            int temp = *(i-1);
            *(i-1) = *i ;
            *i = temp;
            h=1;
            break;
        }
    }
    int s = nums.end() - nums.begin() - 1;
    if(h==1)
    {
        int l = i - nums.begin();
        quicksort(nums,l,s);
    }
    else
        quicksort(nums,0,s);
}

};
,,,

**Algorithm of the code is:
Iterate on the vector from the end till vector.begin() + 1
if the next element of vector is smaller than the current element than swap these elements and then break out from the loop else continue in the loop.

if swapping happend than sort the vector in ascending order from the index where swapping has happend.
else sort the whole vector in ascending order**

Runtime Error Message:

==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000002b8 at pc 0x000000382ab9 bp 0x7fff4d4e5b40 sp 0x7fff4d4e5b38
READ of size 4 at 0x6020000002b8 thread T0
#5 0x7f22fc1f582f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
0x6020000002b8 is located 0 bytes to the right of 8-byte region [0x6020000002b0,0x6020000002b8)
allocated by thread T0 here:
#6 0x7f22fc1f582f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
Shadow bytes around the buggy address:
0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8010: fa fa fd fd fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8020: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8030: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8040: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
=>0x0c047fff8050: fa fa fd fa fa fa 00[fa]fa fa fa fa fa fa fa fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==31==ABORTING

What could be the possible issue ?

Comments (0)