Seemingly equivalent list initialization results in different behavior

Question

I'm solving this challenge on HackerRank in Python 3 and came up with the following solution:

def dynamicArray(n, queries):
    seqList = [[] for _ in range(n)]
    lastAnswer = 0
    result = []

    for query in queries:
        if query[0] == 1:
            seqList[(query[1] ^ lastAnswer) % n].append(query[2])
        elif query[0] == 2:
            seq = seqList[(query[1] ^ lastAnswer) % n]
            lastAnswer = seq[query[2] % len(seq)]
            result.append(lastAnswer)

    return result

This works fine and passes all test cases.

The problem is when i change the initialization of seqList from the following:

seqList = [[] for _ in range(n)]

To this:

seqList = [[]] * n

Then all test cases fail and i cannot figure out why. There are no other changes in the code.

I've even created the following simple test case just to compare the results of these initialization methods:

n = 3

a1 = [[]] * n
a2 = [[] for _ in range(n)]

print(a1)
print(a2)
print(a1 == a2)

And the result is as expected:

[[], [], []]

[[], [], []]

True

I'd really appreciate if someone could explain this behavior to me.

score 2 · Accepted Answer · answered Dec 25 '19 at 13:00

This:

seqList = [[]] * n

is the same as this:

lst = []
seqList = [lst for _ in range(n)]

When you use * to create lists, Python doesn't do any copying. All sublists reference the same list. So this line:

seqList[(query[1] ^ lastAnswer) % n].append(query[2])

appends to all the lists.

Piyush Singh · Answer 2 · 2019-12-25T13:10:40.133

It might appear the same till here as you show:

n = 3

a1 = [[]] * n
a2 = [[] for _ in range(n)]

print(a1)
print(a2)
print(a1 == a2)

Output:

True

But here is where the difference is visible:

a1[0].append('_')
a2[0].append('_')
print(a1)
print(a2)

Output:

[['_'], ['_'], ['_']]
[['_'], [], []]

This is because lists are "mutable" data type. The two initialization styles work in different ways: In first one compiler builds it all at once (and hence will be faster) whereas second one builds incrementally. With immutable data-types you wont see anything like this.

score 1 · Answer 3 · answered Dec 25 '19 at 13:23

Method 1:

n = 5
seqList = [[] for _ in range(n)]
seqList
>>[[], [], [], [], []]

seqList[0].append(8)
seqList
>>[[8], [], [], [], []]

Method 2:

seqList2 = [[]] * n
seqList2
>>[[], [], [], [], []]

seqList2[0].append(8)
seqList2
>>[[8], [8], [8], [8], [8]]

Method 2 creates a list of lists and each member list refers to the same list instance.

[[] for _ in range(n)] evaluates or creates a [] once for each iteration of n whereas [[]] * n evaluates [] only once. Hence only one instance is created

Seemingly equivalent list initialization results in different behavior

3 Answers3