I'm trying to solve this LeetCode problem.

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

My solution below works well on vscode on my Mac, but when I run it with the exact same test case on leetcode it throws compile error. Does anyone have any idea why?

/// my solution
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i = m - 1;
    int j = n - 1;
    int k = nums1Size - 1;

    while(k >= 0){
        if (nums1[i] < nums2[j]){
            nums1[k--] = nums2[j--];
        } else {
            nums1[k--] = nums1[i--];
        }
    }
}

int main(void){
    int arr1[] = {1, 2, 3, 0, 0};
    int arr2[] = {5, 6};
    merge(arr1, 5, 3, arr2, 2, 2);
    for (int i = 0; i < 5; i  ){
        printf("%i\n", arr1[i]);
    }
}

This code prints 1,2,3,5,6 correctly.

But on leetcode when I give the same input, it shows

==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000000c at pc 0x564b115dfc07 bp 0x7ffecbbcf300 sp 0x7ffecbbcf2f0
READ of size 4 at 0x60200000000c thread T0
    #2 0x7f4f899f30b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6 0x270b2)
0x60200000000c is located 4 bytes to the left of 8-byte region [0x602000000010,0x602000000018)
allocated by thread T0 here:
    #0 0x7f4f8a638bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5 0x10dbc8)
    #3 0x7f4f899f30b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6 0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa[fa]00 fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: 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

CodePudding user response：

Imagine the case where is something like this:

nums1 = {10, 11, 12, 0, 0, 0};   
nums2 = {1, 2, 3};

At some point in while loop index i will become -1 and index j will be 2, and you will compare nums1[-1] and nums2[2] which cause an error. And you also forgot that after while loop there can be some elements that aren't inserted in nums1. I think this code will help you understand better:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i = m - 1, j = n - 1, k = nums1Size - 1;

    while(i >= 0 && j >= 0){
        if (nums1[i] < nums2[j]){
            nums1[k--] = nums2[j--];
        } else {
            nums1[k--] = nums1[i--];
        }
    }

    while (i >= 0) nums1[k--] = nums1[i--];
    while (j >= 0) nums1[k--] = nums2[j--];
}

I suggest you to execute your code on paper to see where the error is.