# 1 line Python solution, UPDATE to O(nk)

• 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)]``````

• 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 :-(

• Just the same strategy as Sliding Window Maximum

• 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 :-)

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

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

• 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))
``````

• 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)

• 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!

``````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)]``````

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

• 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 :-)

• 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 :-)

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

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

``````return map(operator.add, house, tmp)
``````

but that's a bit longer.

• Really smart O(nk) time solution!

• 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;
}));
``````

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