How to interpret the error message in "Merge Sorted Array"


  • 0
    H
    Submission Result: Wrong Answer
    
    Input:	[], [1]
    
    Output:	[0]
    
    Expected:	[1]
    

    I got the error message as above. what i did is simply chain two lists and sort it. how could it be a zero in the list where merged from [] and [1]? doe it indicate A is initialized with zeros to hold extra space?

    and my code for testing.

    A.extend(B)
    A.sort()

  • 0
    Y

    I met the same problem. My program can output the correct answer [1] for this test case on my local computer. But the result running on leetcode is [0]. I would like to know the answer as well. Please help.

    if m == 0:
    A = [0] * n
    for x in range(0, n):
    A[x] = B[x]
    return A
    if n == 0: return A


  • 0
    M

    This type of thing should probably be a comment. Typically, when an answer has been given, it makes it less likely for others to open the question and answer it themselves.


  • 2
    M

    Assuming that your code is something like yang3's, the problem is that A is passed by reference, but the overwriting (A=[0]*n) is changing which array A is pointing to. Since you return nothing, the original array is being observed from outside the function and by overwriting A, any changes in it will not propagate to the outside array. Therefore, the original value, [0], is what the function sees you having returned.

    I assume that what you did to check your answer was print A inside the merge function, or returned A and printed the returned value? If so, that is using the local reference you changed it to, not the one leetcode is checking for correctness, which is the original array passed in.

    As the description says, # @return nothing.

       def merge(self,A,m,B,n):
            if n!=0:
                while m>0 and n>0:
                    if A[m-1] < B[n-1]:
                        A[m+n-1] = B[n-1]
                        n=n-1
                    else:
                        A[m+n-1] = A[m-1]
                        m=m-1
                while n>0:
                    A[n-1] = B[n-1]
                    n=n-1
    

    EDIT The original inputs, while stating that A=[] and B=[1], aren't quite what is passed in. Under the assumption from the problem description, A has space for B to be added to it. In this version, that space is represented by a string of 0s equal in length to B at the end of A. Because of this, the A passed in is actually [0], since it is the empty list, with one 0 appended to it.

    EDIT2 Thanks to now having the code, I believe I've identified what is happening. You do A.extend(B), changing A from [0] to [0,1]. You then sort it, which has no effect, as it is already sorted. The problem arises from the tester, which knows there are n+m elements, 1 in this case, so only looks at the first n+m (1) indices of your array. That is the [0]. Your solution assumes there isn't space for B to be added to A. Instead of A.extend(B), try A[m:]=B That allows B to be placed in A, without leaving the empty spaces.

    def merge(self,A,m,B,n):
        A[m:]=B
        A.sort()
    

    was accepted for me.


  • 0
    H

    hi, since it says return nothing, I of course changed A in place. like I said, what I did is simply something like chain(A,B) then A.sort().


  • 0
    H

    also I think in my case the original value should be [] and [1], not [0].


  • 0
    M

    So, itertools.chain? If I understood what I read, that would create an iterator with first A, then B which could be added to a new list, not add B to the end of A. Could you edit your question with some or all of the code? That might help understand what caused the error.


  • 0
    H

    thanks for replying. I added my code to the question.


  • 0
    H

    sorry for late response. your edit is correct. the questions setup is weird.


Log in to reply
 

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