1+ lines Ruby, Python


  • 14

    First two solutions could easily be generalized to arbitrary number of colors.

    Solution 1 ... Ruby

    def min_cost(costs)
      costs.reduce([0]*3) { |prev, now| now.map { |n| n + prev.rotate![0,2].min } }.min
    end
    

    Solution 2 ... Python

    def minCost(self, costs):
        prev = [0] * 3
        for now in costs:
            prev = [now[i] + min(prev[:i] + prev[i+1:]) for i in range(3)]
        return min(prev)
    

    Solution 3 ... Python

    def minCost(self, costs):
        return min(reduce(lambda (A,B,C), (a,b,c): (a+min(B,C), b+min(A,C), c+min(A,B)),
                          costs, [0]*3))

  • 0

    I like the second one --- now and prev are very readable :-)


  • 0

    What about the first one? It's shorter and it also uses those names :-)


  • 0

    Hi, Stefan. Yeah, it is similar or even better :-) It is just that Ruby grammar is still not accesible to me...


  • 0
    R

    well it's still O(n*k^2) time complexity. As pre[0:i] + pre[i+1:] need O(k)


  • 0

    What is k? Number of colors? That's constant here, so it's O(n).

    It would be O(n*k^2) if generalized naively, but can be made O(nk) in a nice way, which is why I suggested that extension :-)


  • 0
    R

    yes, I have seen your elegant python code. So strong you are!


  • 1
    X

    Similar solution in Java:
    Here is the java implementation with lambda:

    if (costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    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;
        }));
    

  • 0
    D

    @StefanPochmann thx. I like your python solution


  • 0
    K

    You know, although I admire your solutions...
    But sometimes you are being too pythonic...


  • 0
    H

    you can do

    min(prev[(i+1)%3],prev[(i+2)%3])
    

    instead of

    min(prev[:i] + prev[i+1:])
    

    which slice the list and create new lists.


  • 0

    @hzc930916 Yes, but with three colors both ways are O(1) and with an arbitrary number of colors, I think yours doesn't work, does it? I didn't think it through now... Anyway, I like mine for the simplicity and the generality.

    But yours is also good, yes. I think I'd prefer min(prev[(i+1)%3], prev[(i-1)%3]), though. I somehow find that nicer, and it supports the two-colors case as well (although that one is trivial).


  • 0
    Z

    Haha, we have similar solution again and I have a feeling before I came to the discussion if you have posted the solution, this solution must be one of them, but yours definitely better than mine:

    return costs and min(reduce(lambda x, y: (y[0] + min(x[1], x[2]), y[1] + min(x[0], x[2]), y[2] + min(x[0], x[1])), costs)) or 0
    

    I just know today the third parameter of reduce function is initializer


  • 0
    A

    Why I have this error?

    In [68]: f = lambda (A,B,C),(a,b,c): (a + min(B, C), b + min(A, C), c + min(A, B))
      File "<ipython-input-68-2a9c6badd44d>", line 1
        f = lambda (A,B,C),(a,b,c): (a + min(B, C), b + min(A, C), c + min(A, B))
                   ^
    SyntaxError: invalid syntax
    

  • 0

    @algowl Because you're using Python 3. https://www.python.org/dev/peps/pep-3113/


Log in to reply
 

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