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):
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)
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:]