One-liner in Python

• Solution

``````def minimumTotal(self, t):
return reduce(lambda a,b:[f+min(d,e)for d,e,f in zip(a,a[1:],b)],t[::-1])[0]
``````

Explanation

Starting with the bottom row, I move upwards, always combining the current row and the next upper row. At the end, I have combined everything into the top row and simply return its only element. Here's a longer version with meaningful variable names:

``````def minimumTotal(self, triangle):
def combine_rows(lower_row, upper_row):
return [upper + min(lower_left, lower_right)
for upper, lower_left, lower_right in
zip(upper_row, lower_row, lower_row[1:])]
return reduce(combine_rows, triangle[::-1])[0]``````

• It's awesomly cool! Python's simplicity is why I love it.

• This literally makes no sense.

Do you mind expand it and provide an explanation of what is going on?

• I have added some explanation and more understandable code. Is it clear now?

• @sidazhang I can give ur an example so that it helps ur understand this code better.

we start with the list [ [-1], [2,3], [1, -1, -3] ]

the last line reduce(combine_rows, triangle[::-1])[0]
tells you to reverse the list to [ [1, -1, -3], [2,3], [-1] ]
so that [1, -1, -3] and [2,3] will be lower_row and upper_low for the reduce function correspondingly.
Then, combine_rows function will create a list of tuple ( [2,3], [ 1,-1,-3], [-1,-3] ) in zip(upper_row, lower_row, lower_row[1:])
and the next step we use list comprehension to reduce list to [ [2-1,3-3 ] [-1]].
at the end reduce will advance and return result from it last iteration , [ [1,0 ], [-1] ].

• Slightly longer 1-liner. Well, pretty close if you don't rename `triangle` with `t` and stuff :-)

I think this one is easier to understand because it keeps the DP structure better.

``````class Solution(object):
def minimumTotal(self, triangle):
return reduce(lambda a, b:[min(a[i], a[i+1])+n for i, n in enumerate(b)], triangle[::-1])[0]
``````

Which is equivalent to:

``````class Solution(object):
def minimumTotal(self, triangle):
dp = triangle[-1][:]
for i in range(len(triangle)-2, -1, -1):
for j in range(i+1):
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
return dp[0]
``````

• @o_sharp What do you mean with "it keeps the DP structure better"?

• @StefanPochmann Sorry for the confusion! I mean the induction thing, like `dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]` stuff is still intact. No big deal.

• @o_sharp Ah, ok. I guess if you're coming from there, then your oneliner might be easier. I just probably didn't come from there but wrote mine directly like that. I don't see the need/point to think in meaningless indexes, and I'm very used to zipping like that.

• @StefanPochmann In this case, I believe I had a good reason of coming from that angle, because it takes O(1) space like this:

``````class Solution(object):
def minimumTotal(self, triangle):
dp = triangle[-1]
for i in range(len(triangle)-2, -1, -1):
for j in range(i+1):
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
return dp[0]
``````

Or do `dp = triangle[-1][:]` if I wanna avoid changing the input data. Too bad 1-liners lose that advantage. They take O(n^2) space.

• @o_sharp Yeah, I don't mean your angle is bad, I just mean I had a different one and find it just as easy :-)

I understand your view that our one-liners take O(n^2) space, but I don't share it. Because they only ever hold two extra rows, the current accumulated row and the next accumulated row. And I see it as similar to for example a usual recursive traversal of a balanced binary tree, which I think you'd say takes O(log n) space, not just O(n) space.

• @StefanPochmann I think I have an important question: does this code take O(n) space or O(mn) space?

``````l = [x for x in range(n)]
for i in range(m):
l2 = [x*2 for x in l]
l = l2
``````

I used to think it was worst-case O(mn) space because objects never get destroyed until gc kicks in, but after looking at your reply, I can't say I'm sure. Do you have a definitive answer?

• @o_sharp That's definitely not O(n) space. Because you build n-1 ints with at least m bits each. I don't think Python optimizes them, so it's Ω(mn) space. But that's not what you meant, right? Only shows that one shouldn't over-complicate their examples? :-P

But about what you probably meant: Note that `id` gives me an object's memory address:

``````>>> help(id)
Help on built-in function id in module __builtin__:

id(...)
id(object) -> integer

Return the identity of an object.  This is guaranteed to be unique among
simultaneously existing objects.  (Hint: it's the object's memory address.)
``````

And now let's track the ids, i.e., the memory addresses, of `l` in your example:

``````>>> from collections import Counter
>>> ids = Counter()
>>> n, m = 10, 1000
>>> l = [x for x in range(n)]
>>> for i in range(m):
l2 = [x*2 for x in l]
l = l2
ids[id(l)] += 1

>>> ids
Counter({40450688: 500, 51567832: 500})
``````

You can see that in the 1000 iterations, `l` was only ever at one out of two addresses. Switching between them because you're switching it to `l2`. So if I'm not mistaken, I actually did use only O(n) space (for the lists) because Python did reuse the same space over and over again.

Overall I think both viewpoints are valid, but I don't know what others think. Quickly googling didn't find me anything. Might be a good question for the appropriate stack exchange site or so. Maybe I'll do that.

Btw, why do you use the list comprehension in `[x for x in range(n)]`?

• @o_sharp Oh, or maybe you did mean the ints as well (ignoring their sizes, but considering their number)? Here's another experiment:

``````from collections import Counter
with open('test_space_management.txt', 'w') as f:
i = 1000
while i < 1000000:
f.write('%d ' % id(i))
i += 1
with open('test_space_management.txt') as f:
print ctr.most_common()
``````

That gave me:

``````[('50272932', 428390), ('41689012', 367095), ('41689108', 203514), ('50272800', 1)]
``````

So Python quickly reused space for those ints as well.

(I went with writing the ids into a file because storing them in a dict didn't allow this great reuse, I guess because the dict entries kept occupying the memory spots previously used by obsolete int objects, preventing the new int objects to take them.)

• @StefanPochmann Thanks for introducing `id`! It's such a great tool, but it just blew my mind.

Under Python 3.4,

``````n = 1000
a = 0
d = {}
for i in range(n):
a += 1
d[id(a)] = True
print(len(d))
``````

gave me:

``````1000
``````

This simple `a+=1` loop takes O(n) space? I thought `operator.iadd` was in place. It is in place for adding lists, but not for integers?

Actually, it takes exactly min(n,32770) different addresses. Maybe 32770 is the point when gc kicks in.

• @o_sharp What do you get when you run my version, where I write the ids into a file?

• @StefanPochmann

I have the same result with yours if I do a while-loop.

But if I do a for-loop:

``````from collections import Counter
with open('test_space_management.txt', 'w') as f:
n = 1000000
a = 0
for i in range(n):
f.write('%d ' % id(a))
a += 1
with open('test_space_management.txt') as f:
print(ctr)
``````

it gave me:

``````Counter({'35801712': 483616, '24647416': 483615, '36296688': 10838, '36296736': 10837, '36296848': 10837, '1463013904': 1, '1463015392': 1, '1463014448': 1, '1463017904': 1, '1463016944': 1, '1463015936': 1, '1463015424': 1, '1463017200': 1, '1463016288': 1, '1463014080': 1, '1463015584': 1, '1463014544': 1, '1463014208': 1, '1463014368': 1, '1463017056': 1, '1463016800': 1, '1463016144': 1, '1463016080': 1, '1463016352': 1, '1463014576': 1, '1463016656': 1, '1463016416': 1, '1463014816': 1, '1463015120': 1, '1463015072': 1, '1463016896': 1, '1463017824': 1, '1463015648': 1, '1463014304': 1, '1463017136': 1, '1463015776': 1, '1463017120': 1, '1463014272': 1, '1463014048': 1, '1463016704': 1, '1463014880': 1, '1463017792': 1, '1463017568': 1, '1463016512': 1, '1463015200': 1, '1463014752': 1, '1463015488': 1, '1463015520': 1, '1463017376': 1, '1463014976': 1, '1463015744': 1, '1463015296': 1, '1463015472': 1, '1463017872': 1, '1463015952': 1, '1463017664': 1, '1463017696': 1, '1463016272': 1, '1463015872': 1, '1463015856': 1, '1463017536': 1, '1463017744': 1, '1463013936': 1, '1463016112': 1, '1463014768': 1, '1463014496': 1, '1463014848': 1, '1463015600': 1, '1463016368': 1, '1463014096': 1, '1463015632': 1, '1463013984': 1, '1463017488': 1, '1463016032': 1, '1463014432': 1, '1463015088': 1, '1463017472': 1, '1463016576': 1, '1463017840': 1, '1463013840': 1, '1463015680': 1, '1463017504': 1, '1463014016': 1, '1463014560': 1, '1463015552': 1, '1463017712': 1, '1463017424': 1, '1463013872': 1, '1463015040': 1, '1463013824': 1, '1463016304': 1, '1463017680': 1, '1463014112': 1, '1463015248': 1, '1463017632': 1, '1463016448': 1, '1463016480': 1, '1463013888': 1, '1463017264': 1, '1463016496': 1, '1463017856': 1, '1463016192': 1, '1463017440': 1, '1463017776': 1, '1463015904': 1, '1463016592': 1, '1463017328': 1, '1463016880': 1, '1463017008': 1, '1463016960': 1, '1463015376': 1, '1463015888': 1, '1463014960': 1, '1463017920': 1, '1463014160': 1, '1463015920': 1, '1463016720': 1, '1463015152': 1, '1463015616': 1, '1463016624': 1, '1463014528': 1, '1463014288': 1, '1463017296': 1, '1463014864': 1, '1463016832': 1, '1463017088': 1, '1463015504': 1, '1463014704': 1, '1463014736': 1, '1463014320': 1, '1463015136': 1, '1463015568': 1, '1463017600': 1, '1463017888': 1, '1463014144': 1, '1463014832': 1, '1463014592': 1, '1463017408': 1, '1463016160': 1, '1463016672': 1, '1463017104': 1, '1463017344': 1, '1463014256': 1, '1463014512': 1, '1463017456': 1, '1463016992': 1, '1463014656': 1, '1463016816': 1, '1463017728': 1, '1463017760': 1, '1463016976': 1, '1463015808': 1, '1463014192': 1, '1463017552': 1, '1463016640': 1, '1463014352': 1, '1463015360': 1, '1463015536': 1, '1463016240': 1, '1463013952': 1, '1463015440': 1, '1463014064': 1, '1463015264': 1, '1463017616': 1, '1463016048': 1, '1463014464': 1, '1463014688': 1, '1463016256': 1, '1463015728': 1, '1463014608': 1, '1463017584': 1, '1463014784': 1, '1463017248': 1, '1463015344': 1, '1463014640': 1, '1463013856': 1, '1463015184': 1, '1463016688': 1, '1463017072': 1, '1463015792': 1, '1463014720': 1, '1463015232': 1, '1463017808': 1, '1463015840': 1, '1463016560': 1, '1463014896': 1, '1463014624': 1, '1463016016': 1, '1463016864': 1, '1463017168': 1, '1463014672': 1, '1463016464': 1, '1463017216': 1, '1463014400': 1, '1463015168': 1, '1463015312': 1, '1463014224': 1, '1463016912': 1, '1463016176': 1, '1463016528': 1, '1463014480': 1, '1463017232': 1, '1463017360': 1, '1463016128': 1, '1463014912': 1, '1463015056': 1, '1463016432': 1, '1463015008': 1, '1463017280': 1, '1463016544': 1, '1463016096': 1, '1463014384': 1, '1463015328': 1, '1463017184': 1, '1463014416': 1, '1463015280': 1, '1463016736': 1, '1463015824': 1, '1463015984': 1, '1463015216': 1, '1463014928': 1, '1463014336': 1, '1463015712': 1, '1463015024': 1, '1463016000': 1, '1463016336': 1, '1463016384': 1, '1463017152': 1, '1463015456': 1, '1463014128': 1, '1463017040': 1, '1463014992': 1, '1463014800': 1, '1463016848': 1, '1463016400': 1, '1463015408': 1, '1463013920': 1, '1463014032': 1, '1463016224': 1, '1463014944': 1, '1463017024': 1, '1463015968': 1, '1463016784': 1, '1463017520': 1, '1463014000': 1, '1463016064': 1, '1463016320': 1, '1463017312': 1, '1463015760': 1, '1463017392': 1, '1463016768': 1, '1463015104': 1, '1463013968': 1, '1463015664': 1, '1463016208': 1, '1463015696': 1, '1463016928': 1, '1463017648': 1, '1463016608': 1, '1463014240': 1, '1463016752': 1, '1463014176': 1})
``````

I hope it doesn't mean range() is bad for memory consumption.

• @o_sharp Yeah, no idea what `range` does under the hood, but apparently it blocks some memory spots as well or so. I wouldn't worry about it, the Python makers probably know what they're doing.

• Nice solution! I was inspired by your bottom-up one-liner to create a top-bottom one-liner:

``````def minimumTotal(self, triangle):
return min(reduce(lambda a, b: [c+min(d,e) for c,d,e in zip(b,['']+a,a+[''])], triangle, [0]))
``````

This has the advantage of not having to duplicate the reversed triangle in memory in order to process it.

I used the Python2 hack that for any integer n:
'' > n

I'm not sure how to fix the one-liner for Python3 without making that 1 line extremely long. But anyway I would typically write it in the more traditional form, even if it's a bit longer :-). This is how I had originally written it:

``````def minimumTotal(self, triangle):
r = [0]
for row in triangle:
r = [row[i] + min (r[max(i-1,0)], r[min(i,len(r)-1)]) for i in range(len(row))]
return min(r)
``````

• This post is deleted!

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