CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
Kurt Peek
Kurt Peek

Reputation: 57471

Time Limit Exceeded on LeetCode's Coin Change problem

I'm trying to solve the Coin Change problem on LeetCode:

enter image description here

I came up with what I believe to be the same bottom-up, dynamic programming approach as mentioned in the solution:

import math


class Solution:
    def coinChange(self, coins, amount):
        fewest = [0] * (amount + 1)
        for i in range(1, amount + 1):
            fewest[i] = 1 + min(
                (fewest[i - coin] for coin in
                    [c for c in coins if i - c >= 0]),
                default=math.inf)
        return fewest[amount] if fewest[amount] < math.inf else -1

Here are some pytest test cases I used to verify the solution:

def test_1():
    assert Solution().coinChange([1, 2, 5], 1) == 1


def test_2():
    assert Solution().coinChange([1, 2, 5], 2) == 1


def test_3():
    assert Solution().coinChange([1, 2, 5], 3) == 2


def test_4():
    assert Solution().coinChange([1, 2, 5], 4) == 2


def test_5():
    assert Solution().coinChange([1, 2, 5], 5) == 1


def test_67():
    assert Solution().coinChange([1, 2, 5], 6) == 2
    assert Solution().coinChange([1, 2, 5], 7) == 2


def test_8():
    assert Solution().coinChange([1, 2, 5], 8) == 3


def test_11():
    assert Solution().coinChange([1, 2, 5], 11) == 3


def test_no_way():
    assert Solution().coinChange([2], 3) == -1

The problem is that I get a "Time Limit Exceeded" error:

enter image description here

However, if I copy this test case and run it locally, I find that the algorithm takes only 0.02s:

import pytest

def test_time_limit_exceeded():
    Solution().coinChange(
        [205, 37, 253, 463, 441, 129, 156, 429, 101, 423, 311],
        6653)


if __name__ == "__main__":
    pytest.main([__file__, '--duration', '1'])

leads to the following output:

============================= test session starts ==============================
platform darwin -- Python 3.6.6, pytest-3.8.1, py-1.6.0, pluggy-0.7.1
rootdir: /Users/kurtpeek/GoogleDrive/CodeRust, inifile:
collected 11 items

coin_changing_leetcode2.py ...........                                   [100%]

=========================== slowest 1 test durations ===========================
0.02s call     coin_changing_leetcode2.py::test_time_limit_exceeded
========================== 11 passed in 0.07 seconds ===========================

Any idea why LeetCode is failing this implementation?

Upvotes: 0

Views: 623

Answers (2)

Kurt Peek
Kurt Peek

Reputation: 57471

I realized that the list comprehension [c for c in coins if i - c >= 0] was being evaluated len(coins) times for each i, whereas it need only be evaluated once for each i. This slightly refactored solution was accepted:

import math


class Solution:
    def coinChange(self, coins, amount):
        fewest = [0] * (amount + 1)
        for i in range(1, amount + 1):
            eligible_coins = [c for c in coins if i - c >= 0]
            fewest[i] = 1 + min(
                (fewest[i - coin] for coin in eligible_coins),
                default=math.inf)
        return fewest[amount] if fewest[amount] < math.inf else -1

It's still among the bottom 10% for Python 3 solutions to this problem, though:

enter image description here

Upvotes: 0

MBo
MBo

Reputation: 80187

Seems that this piece:

  fewest[i] = 1 + min(
            (fewest[i - coin] for coin in
                [c for c in coins if i - c >= 0]),
            default=math.inf)

checks for all coins, filtering appropriate ones.

But you can sort coint nominals and traverse only small enough nominals for given i.

Upvotes: 1

Related Questions