leetcode 88. Merge Sorted Array c++ runtime error

Question

I am doing leetcode problem 88. Here is the link: Merge Sorted Array.

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

I use c++ to solve this problem. But I always got runtime error like this:

Runtime Error Message:
Line 922: Char 34: runtime error: reference binding to null pointer of type 'value_type' (stl_vector.h)
Last executed input:
[1]
1
[]
0

Here is my code:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int output[m+n] = {0};
        int i = 0;
        int j = 0;
        if(sizeof(nums1) == 0)
        {
            for(i = 0; i < n; i++)
            {
                nums1[i] = nums2[i];
            }
            return;
        }
        if(sizeof(nums2) == 0)
        {
            return;
        }
        for(int k = 0; k < m+n; k++)
        {
            if(nums1[i] <= nums2[j])
            {
                if(i < m)
                {
                    output[k] = nums1[i];
                    i++; 
                }
                else if(j < n)
                {
                    output[k] = nums2[j];
                    j++;
                }
            }
            else if(nums1[i] >= nums2[j])
            {
                if(j < n)
                {
                    output[k] = nums2[j];
                    j++;
                }
                else if(i < m)
                {
                    output[k] = nums1[i];
                    i++;
                }
            }
        }
        for(i = 0; i < m+n; i++)
        {
            nums1[i] = output[i];
        }
    }
};

It's easy to test, just click the link above and copy my code then submit it. I hope someone could help me.

sizeof(nums1) == 0 is never true. Neither is sizeof(nums2) == 0 — Igor Tandetnik
– Igor Tandetnik, Commented Dec 24, 2019 at 5:05
Note that you don't need an additionalp array. The question suggests not to do it (num1 large enough). Try filling num1 by the end first — Damien
– Damien, Commented Dec 24, 2019 at 5:15
You must test validity of i and j before using num1[i] and num2[j]. UB — Damien
– Damien, Commented Dec 24, 2019 at 5:22

Wander3r · Accepted Answer · 2019-12-24 05:05:15Z

2

When using std::vector, to check if it's empty the member function size() should be used. sizeof is not the right check.

  if(sizeof(nums1) == 0)

should be

nums1.size()==0

Same goes for nums2 vector as well. Another thing to note is the output array size is unknown at compile time and VLA is not typically supported, instead use vector here as well

std::vector<int> output(m+n,0); //Initialized with m+n elements with value 0

answered Dec 24, 2019 at 5:05

Wander3r

1,9091 gold badge17 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Stephane Over a year ago

I modified my code and it improved a little bit. But it run into another problem.

Runtime Error Message: AddressSanitizer: heap-buffer-overflow on address 0x602000000274 at pc 0x00000040756f bp 0x7ffe441385f0 sp 0x7ffe441385e8

Ajay Dabas · Accepted Answer · 2019-12-24 06:24:49Z

There are some flaws in your current approach, like:

sizeof(nums1) operator will only give you 0 in case: nums1[],m=0,nums2[],n=0, because for all other cases when m=0 but n!=0, nums1 will contain 0's and it won't be an empty list. Ex. nums1[0,0],m=0,nums2[1,2],n=2. To handle this, check if m==0 or n==0 instead of using sizeof.
In line if(nums1[i] <= nums2[j]), if j>=n, it will throw a segmentation error.
You may find more flaws if you check all test cases on LeetCode.

A correct approach is given below. This solution is accepted on LeetCode. I've added comments which are mostly self-explanatory. Feel free to comment if you have any queries.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int output[m+n] = {0};
        int i = 0;
        int j = 0;
        int k = 0;
        if(m == 0) // nums1 is empty. Ex. nums1[0,0],m=0 and nums2[1,2],n=2
        {
            for(i = 0; i < n; i++)
            {
                nums1[i] = nums2[i];
            }
            return;
        }
        if(n == 0) // nums2 is empty. Ex. nums1[1,2],m=2 and nums2[],n=0
        {
            return;
        }
        for(k = 0; k < m+n; k++)
        {
            if(i>=m || j>=n) // Check if we've exhausted any of nums1 or nums2 list
                break;
            if(nums1[i] <= nums2[j]) // if nums1[i] <= nums2[j]
            {
                output[k] = nums1[i];
                i++;
            }
            else{ // else, nums1[i] > nums2[j]
                output[k] = nums2[j];
                j++;
            }
        }
        while(i<m){ // If some elements are left in nums1. Ex: nums1[4,0,0],m=1 and nums2[1,2],n=2
            output[k] = nums1[i];
            i++;
            k++;
        }
        while(j<n){ // If some elements are left in nums2. Ex: nums1[1,2,0],m=2 and nums2[4],n=1
            output[k] = nums2[j];
            j++;
            k++;
        }
        for(i = 0; i < m+n; i++) // Copy back to nums1
        {
            nums1[i] = output[i];
        }
    }
};

Collectives™ on Stack Overflow

leetcode 88. Merge Sorted Array c++ runtime error

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related