pythonmergeindexoutofboundsexception

Getting index out of bounds error in leetcode when I'm not out of bounds


I tried to solve an easy leecode question and I keep getting index out of bounds error, when I try the same solution on visual studio I dont get this error. Here is the question and the code (I am failing a example 3): enter image description here

Here is my code:

def merge(nums1, m, nums2, n ):
        """
        Do not return anything, modify nums1 in-place instead.
        """

        i1 = 0
        i2 = 0
        tmp = 0
        while i1 < n + m :
            if nums1[i1] == 0:
                nums1[i1] = nums2[i2]
                i1+=1
                i2+=1

            elif nums1[i1] <= nums2[i2]:
                i1 += 1
            else:
                tmp = nums2[i2]
                nums2[i2] = nums1[i1]
                nums1[i1] = tmp
                i1 += 1

It says Im out of bounds on this line: nelif nums1[i1] <= nums2[i2]: But I never reach this line because at this point I am out of the loop. The error:

Runtime Error
IndexError: list index out of range
                      ~~~~~^^^^
    elif nums1[i1] <= nums2[i2]:
Line 16 in merge (Solution.py)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    ret = Solution().merge(param_1, param_2, param_3, param_4)
Line 58 in _driver (Solution.py)
    _driver()
Line 70 in <module> (Solution.py)

Solution

  • Here's a fixed version of your method; we bound i2 too, and insert values from nums2 into nums1. Note that, due to the complexity of list.insert(), the average complexity of this algorithm will be O(mn).

    def merge(nums1, m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
    
        i1 = 0
        i2 = 0
        while i1 < n + m and i2 <n:
            if nums1[i1] == 0:
                nums1[i1] = nums2[i2]
                i1 += 1
                i2 += 1
    
            elif nums1[i1] <= nums2[i2]:
                i1 += 1
            else:
                nums1.insert(i1, nums2[i2])
                nums1.pop()
                i1 += 1
                i2 += 1
    

    Example:

    a = [4, 10, 11, 0, 0]
    b = [1, 10]
    merge(a, 3, b, 2)
    print(a)
    # [1, 4, 10, 10, 11]
    

    Here's another version that makes a copy of nums1, then fills nums1 with the relevant values from nums1 and nums2. This one runs in O(m+n).

    def merge2(nums1, m, nums2, n):
        """
        Do not return anything, modify nums1 in-place instead.
        """
    
        i1 = 0
        i2 = 0
        source = nums1[:m]
        while i1 < m and i2 <n:
            if source[i1] <= nums2[i2]:
                nums1[i1 + i2] = source[i1]
                i1 += 1
            else:
                nums1[i1 + i2] = nums2[i2]
                i2 += 1
        if i1 < m:
            nums1[i1 + i2:] = source[i1:]
        else:
            nums1[i1 + i2:] = nums2[i2:]