Error in solution for merge


  • 1
    K

    Below is my solution for merge of two sorted arrays A,B. I implemented the merge section of merge sort, but for some reason the system does not accept my solution and points it has a wrong answer for input [] [1]. The algorithm return [1] when I run it in my machine. But the system gets an output of [0] for this input. Not sure what is wrong with the code. Any help would be useful. Thanks

    class Solution:
        # @param A  a list of integers
        # @param m  an integer, length of A
        # @param B  a list of integers
        # @param n  an integer, length of B
        # @return nothing
        def merge(self, A, m, B, n):
            sorted_array = []
            if m>0 and n > 0:
                i,j = 0,0
                while i < m and j < n:
                    if A[i] < B[j]:
                        sorted_array.append(A[i])
                        i += 1
                    else:
                        sorted_array.append(B[j])
                        j += 1
                if j == n:
                    sorted_array.extend(A[i:])
                else:
                    sorted_array.extend(B[j:])
                #assigning back to A
                A = sorted_array
            elif B:
                A = B
            
            return

  • 0
    B

    The same problem I met when I submitted my code. That's odd...


  • 0
    K

    did you happen to get through the system later?


  • 0
    B

    Not yet. Did you?


  • 0
    K

    No Alex, not yet. I will update here if I do.


  • 3
    W

    I met this problem too. But after reading the problem again, I notice that we should merge B into A without create a new array. Maybe this is the reason why our code can not pass the "[],[1]" input. And the following is my ac code. Wish it can help you.

    class Solution:
        def merge(self, A, m, B, n):
            i = m - 1
            j = n - 1
            k = m + n - 1
    
            for num in range(m, m+n):
                A.insert(num, 0)
    
            while i >= 0 and j >= 0:
                if A[i] > B[j]:
                    A[k] = A[i]
                    k -= 1
                    i -= 1
                else:
                    A[k] = B[j]
                    k -= 1
                    j -= 1
            while j >= 0:
                A[k] = B[j]
                k -= 1
                j -= 1

  • 1
    K

    I do think OJ has some thing not quite right with List.extend(). Even though in local python env list.extend(L) is equivalent to list[len(list):] = L, it is not the case when OJ judges the answer. I am not sure why though, has to do with how the backend processes the answer and test cases.

    See my example below, note the comment.

    class Solution:
        # @param A  a list of integers
        # @param m  an integer, length of A
        # @param B  a list of integers
        # @param n  an integer, length of B
        # @return nothing
        def merge(self, A, m, B, n):
            i = m-1
            j = n-1
            # change this line to A.extend(B) and it falls apart
            A[m:] = B 
            for x in range(len(A)-1, -1, -1):
                if i >= 0 and j >= 0:
                    if A[i] > B[j]:
                        A[x] = A[i]
                        i -= 1
                    else:
                        A[x] = B[j]
                        j -= 1
                elif j >= 0:
                    A[x] = B[j]
                    j -= 1
                else:
                    break

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.