1 line Python solution, UPDATE to O(nk)


  • 6

    Almost same as my original Paint House solution:

    return min(reduce(lambda x, y: [y[i] + min(x[i+1:]+x[0:i] or [0]) for i in range(len(x))], costs)) if costs else 0
    

    O(nk) solution:

    class Solution:
        # @param {integer[][]} costs
        # @return {integer}
        def minCostII(self, costs):
            return min(reduce(lambda x, y: self.combine(y, x), costs)) if costs else 0
    
        def combine(self, house, tmp):
            m, n, i = min(tmp), len(tmp), tmp.index(min(tmp))
            tmp = [m]*i + [min(tmp[0:i]+tmp[i+1:])] + [m]*(n-i-1)
            return [sum(i) for i in zip(house, tmp)]

  • 0

    Yeah, when I suggested this extension problem, I actually used your old solution as an example of an already generalized O(n*k^2) one :-)

    The whole point of this extension problem is to achieve O(n*k) runtime, though (I wish it weren't just a "follow-up" now, I asked to request it). Do that as well?

    And another challenge: Make the scroll bar disappear while staying at one line, and you can't change the function signature. If I'm not mistaken, that means the line can't be longer than 89. I got down to 90 in three slightly different ways :-(


  • 0

    Just the same strategy as Sliding Window Maximum


  • 0

    Yep, that's one of the two ways I know. Not sure which one is simpler. Also, see the other challenge I just added while you were ninja'ing me :-)


  • 0

    I don't know how to trim the one line solution.

    Perhaps there're trick in Python I don't know yet.


  • 6

    Very nice, the O(nk) solution in your update. Some improvements:

    class Solution:
        def minCostII(self, costs):
            return min(reduce(self.combine, costs)) if costs else 0
    
        def combine(self, tmp, house):
            m, n, i = min(tmp), len(tmp), tmp.index(min(tmp))
            tmp, tmp[i] = [m]*n, min(tmp[:i]+tmp[i+1:])
            return map(sum, zip(house, tmp))
    

  • 1

    Here are my attempts:

    return min(reduce(lambda p,N:[n+min(p[:i]+p[i+1:])for i,n in enumerate(N)],costs or[[0]]))
    return min(reduce(lambda p,N:[n+min(p[:i]+p[i+1:])for i,n in enumerate(N)],[[0,0]]+costs))
    return min(reduce(lambda p,N:[n+min(p[:i]+p[i+1:])for i,n in enumerate(N)],[[0]*2]+costs))
    

    (Note that comments are less wide than questions... in a question, I'd only need to shave off one more character to avoid the scroll bar)


  • 0

    Hi, xcv58. Elegant code! Well, I am just a little confused by those reduce, lambda, zip. Could you share a plain Python code :-) Thanks a lot!


  • 1

    How about this:

    class Solution:
        # @param {integer[][]} costs
        # @return {integer}
        def minCostII(self, costs):
            if not costs:
                return 0
            tmp = [0] * len(costs[0])
            for i in costs:
                tmp = self.combine(i, tmp)
            return min(tmp)
    
        def combine(self, house, tmp):
            m, n, i = min(tmp), len(tmp), tmp.index(min(tmp))
            tmp = [m]*i + [min(tmp[0:i]+tmp[i+1:] or [0])] + [m]*(n-i-1)
            return [sum(i) for i in zip(house, tmp)]

  • 0

    @jianchao.li.fighter reduce, lambda and zip really are plain Python :-P (actually I'm not joking)


  • 0

    Hi, @xcv58. Thanks! I see your idea now. The original 1-line code makes me have no idea of what is executed even (mainly due to I don't konw how reduce is done) :-) Your decomposition of it into several lines actually help :-)

    @ StefanPochmann Yeah, Stefan. I could understand that may be just like A, B, C for Pythoners. Well, I need to learn more about Python, anyway :-)


  • 0

    Hi, Stefan. Please help me check whether I've understoond your code: does your code loop with tmp = costs[0] at the very beginning? BTW, the usage of map looks cool :-)


  • 0

    Yes, the first time combine is called, tmp will be costs[0] and house will be costs[1].


  • 0

    And yes, I like that map usage as well :-). An alternative is

    return map(operator.add, house, tmp)
    

    but that's a bit longer.


  • 0
    C

    Really smart O(nk) time solution!


  • 0
    X

    Here is the java implementation with lambda:

    return Arrays.stream(Arrays.stream(costs).reduce((a, b) -> {
            final int len = costs[0].length;
            int[] now = new int[len];
            for (int i = 0; i < len; i++) {
                int tmp = a[i];
                a[i] = Integer.MAX_VALUE;
                now[i] = Arrays.stream(a).min().getAsInt() + b[i];
                a[i] = tmp;
            }
            return now;
        }).get()).min().getAsInt();
    

    Or with AbacusUtil (A tool developed by me :-))

    return N.min(N.reduce(costs, (a, b) -> {
            final int len = costs[0].length;
            int[] now = new int[len];
            for (int i = 0; i < len; i++) {
                int tmp = a[i];
                a[i] = Integer.MAX_VALUE;
                now[i] = N.min(a) + b[i];
                a[i] = tmp;
            }
            return now;
        }));
    

Log in to reply
 

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