Can someone let me know why this is returning wrong answer in leetcode if given input "[2] 1"?


  • 0
    S

    If I run with custom test case [2] 1, it returns -1, if I click submit button, leetcode says it returns 1 which is wrong. Is this a bug in leetcode?

    class Solution(object):

    cache = {}
    
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0:
            return 0
        self.find_min(coins, amount)
        if amount not in self.cache or self.cache[amount] == None:
            return -1
        return self.cache[amount]
    
    def find_min(self, coins, amount):
        if amount in self.cache:
            return self.cache[amount]
        min_count = None
        for current_coin in coins:
            if current_coin == amount:
                self.cache[amount] = 1
                return 1
            if current_coin > amount:
                return None
            for next_coin in coins:
                next_min = self.find_min(coins, amount - next_coin)
                if next_min == None:
                    continue
                if min_count == None:
                    min_count = 1 + next_min
                else:
                    min_count = min(min_count, 1 + next_min)
        self.cache[amount] = min_count

  • 0
    Q

    It's a bug in your code. If you still have not figured it out clicking 'submit' button will run your code against test cases.


  • 0
    S

    Can u kindly point out where is the big? I ran the exact same test in pycharm and in leetcode custom test mode, the resukt is -1.


  • 0
    Q
    1. That global cache variable is being used on multiple method calls, you need to set cache to {} inside coinChange method
    2. I don't see a need for 2 for loops in your recursive function. Lookup GWTW solution. It's java but it shouldn't matter for problem understanding.
    3. Probably should use Array instead of Map for your cache. (Edit: Array is faster)

  • 0
    S

    Thanks a lot sir, 1 resolved the issue, will look into 2 and 3.


Log in to reply
 

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