Python Bug: dictionary iterated backwards in Leetcode

Question

I attempted to do the problem 1313. Decompress Run-Length Encoded List on Leetcode, my code runs perfectly on my IDE, however when I submit it on Leetcode, sometimes, the dictionary is iterated backwards, causing my output list to be in reverse order. I'm 95% certain that my code is correct because it passed 3-4 test cases before the dictionary is iterated backwards on the same test case. Is this a bug, or is there something wrong with my code? Thanks for you help!

class Solution(object):
    def decompressRLElist(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        d = {}
        l = []
        for i in range(0, len(nums), 2):
            d[nums[i+1]] = nums[i]
        print(d)
        for (k,v) in d.items():
            for j in range(v):
                l.append(k)
        return l

in python, dictionaries do not have a fixed ordering. You should assume that the order in which you iterate over a dict, or dict.items() is arbitrary/random. — Kevin Wang, May 06 '20 at 21:35
@KevinWang not exactly - Python v3.7+ does have fixed ordering (by insertion) for `dict`. In Python 2 and python 3 lower than 3.6 however are arbitrarily ordered. — r.ook, May 06 '20 at 21:36
@r.ook yes, I do remember hearing about that, but I thought it was merely an implementation detail in the C Python interpreter, and not part of the python language. EDIT I see now that 3.7 made the ordering (present since 3.6) an official part of the spec. Thanks for the correction. — Kevin Wang, May 07 '20 at 01:37

Martijn Pieters · Accepted Answer · 2020-05-06T22:07:47.983

If Leetcode runs Python 3.5 or older, then the dictionary implementation is not ordered. See Why is the order in dictionaries and sets arbitrary?

You don't need a dictionary here, anyway, you can eliminate the dictionary entirely:

class Solution(object):
    def decompressRLElist(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l = []
        for i in range(0, len(nums), 2):
            k = nums[i+1]
            v = nums[i]
            for j in range(v):
                l.append(k)
        return l

In fact, your dictionary solution is incorrect, because the same value could appear in the LRE more than once, with different lengths; here is a simple example that would demonstrate that issue:

This should expand to:

[
    42, 42, 42,
    17, 17,
    42, 42, 42, 42
]

but your solution would output incorrect results, as putting the input into a dictionary d first means you then operate on {42: 4, 17: 2} and so you output

[
    42, 42, 42, 42,
    17, 17
]

Python Bug: dictionary iterated backwards in Leetcode

1 Answers1