Ones and Zeroes Python O(m*n*len(strs)) TLE


  • 1
    Q

    Can anyone let me know what the complexity of this problem? I got TLE with O(mnlen(strs)). Here's my code:

    class Solution(object):
        def findMaxForm(self, strs, m, n):
            """
            :type strs: List[str]
            :type m: int
            :type n: int
            :rtype: int
            """
            k = len(strs)
            if k ==  0: return 0
            
            a = [0]*(k+1)
            b = [0]*(k+1)
            
            for i in range(k):
                a[i+1] = strs[i].count('0')
                b[i+1] = strs[i].count('1')
                
            f = [[0]*(n+1) for i in range(m+1)]
            
            for t in range(1, k+1):
                for i in range(m, -1, -1):
                    for j in range(n, -1, -1):
                        if i >= a[t] and j >= b[t] and f[i][j] < f[i-a[t]][j-b[t]] + 1:
                            f[i][j] = f[i-a[t]][j-b[t]] + 1
                
            return f[m][n]
    

  • 1
    P

    I wrote such a solution in C++ and it got accepted.


  • 0
    K

    Yeah, I got TLE with what I think is the same solution (O(nmk) where k is len(strs)) in Python so I rewrote it in C++ and it got accepted. (Although I had a memory limit exceeded for using a dp table that was O(nmk) until I changed it to be O(nm))


  • 1

    @quanhoang I have just increased the time limit, your solution is now accepted.


  • 0

    @1337c0d3r What was the time limit before and what is it now? I had submitted the above code twice and it got accepted both times, in around 3000 ms. And after replacing the wasteful a[t] and b[t] with variables at and bt set as the first thing in the t-loop (since they never change inside), it got accepted in around 2200 ms. And after integrating them in the ranges (like range(m, at-1, -1)) it got accepted in around 1700 ms.


  • 0

    @StefanPochmann The time limit before was around 2 seconds, which is the default time limit. Now I have increased the time limit to around 7 seconds, just to be safe. It seems that Python solutions' runtime can vary a lot depending on the language construct you use.


  • 0
    K

    @1337c0d3r When I ran the test-case that was timing out for me, it said it took 52 ms.


  • 0
    Q

    @StefanPochmann said in Ones and Zeroes Python O(m*n*len(strs)) TLE:

    nd 2200 ms.

    Thanks Stefan, I was so stupid to calculate a[t] and b[t].


  • 0
    Z

    @1337c0d3r There are several other problems that suffer from the same dynamic programming Python table construction TLE like:

    1. Coin Change
    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            T = [None] * (amount+1)
            T[0] = 0
            
            for i in range(1, amount+1):
                for coin in coins:
                    if i-coin >= 0 and T[i-coin] != None:
                        T[i] = T[i-coin] + 1 if T[i] == None else min(T[i], T[i-coin]+1)
            
            return T[-1] if T[-1] != None else -1
    
    1. Longest Palindromic Substring
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            best = ''
            
            T = [[False for __ in range(len(s))] for _ in range(len(s))]
            
            for i in range(len(s)):
                T[i][i] = True
                best = s[i]
            for i in range(len(s)):
                if i + 1 < len(s) and s[i]==s[i+1]:
                    best = s[i:i+2]
                    T[i][i+1] = True
            
            for length in range(3, len(s)+1):
                for i in range(0, len(s)-length+1):
                    if T[i+1][i+length-1-1] and s[i] == s[i+length-1]:
                        T[i][i+length-1] = True
                        best = s[i:i+length]
                        
            return best
    

  • 0

    @zizhengwu I have fixed both of them.


  • 0
    Z

    @1337c0d3r And one more

    1. Perfect Squares
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            T = [i for i in range(n+1)]
            perfects = []
            i = 1
            
            for n in range(1, n+1):
                if n == i*i:
                    perfects.append(i*i)
                    i += 1
                for p in perfects:
                    T[n] = min(T[n], T[n-p]+1)
            
            return T[n]
            
            
    

  • 0

    @zizhengwu Fixed.


Log in to reply
 

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