Python: Sorting with lambda key confusion

Question

What is difference between .sort(key=lambda x: x[0]) and .sort(key=lambda x: (x[0], -x[1])). I thought they both would sort the list basically.

I tried with an example:

lst = [[2,1], [0,4], [6,7], [3, 5]]
lst.sort(key=lambda x: x[0])
print(last)

>>> [[0, 4], [2, 1], [3, 5], [6, 7]]

lst = [[2,1], [0,4], [6,7], [3, 5]]
lst.sort(key=lambda x: (x[0], -x[1]))
print(last)

>>> [[0, 4], [2, 1], [3, 5], [6, 7]]

They work ideally the same in this case.

In this LeetCode problem, however, when I use the first approach (key=lambda x: x[0]), I get the wrong answer

When I use the second approach (key=lambda x: (x[0], -x[1])), the solution is accepted.

My final code then looks like the following:

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        # intervals.sort(key=lambda x: x[0])
        intervals.sort(key=lambda x: (x[0], -x[1]))
        last = -1
        removed = 0
        for i in intervals:
            if i[1] <= last:
                removed += 1
            else:
                last = i[1]
        return len(intervals) - removed

Also, I guess that the problem is with the intervals which start with the same left-end (as in the wrong answer). When I tried that test case separately I got this:

lst = [[1,2], [1,4], [3,4]]
lst.sort(key=lambda x: x[0])
print(last)

>>> [[1, 2], [1, 4], [3, 4]]

lst = [[1,2], [1,4], [3,4]]
lst.sort(key=lambda x: (x[0], -x[1]))
print(last)

>>> [[1, 4], [1, 2], [3, 4]]

It seems to have a little difference with the order of right-ends, though.

What I think is it is first looking for first element of the sublist, then -second element of sublist. Then it is sorting according to that — user15801675
– user15801675, Commented Jul 28, 2021 at 5:30

Guy · Accepted Answer · 2021-07-28 05:35:00Z

1

In lst.sort(key=lambda x: x[0]) you are sorting the list by the first element in each sublist, when the rest are ignored.

In lst.sort(key=lambda x: (x[0], -x[1])) you are sorting the list by the first element, and in case there are two elements with the same value the sorting will be done by the second element.

In the second sort() -x[1] means the opposite of the value in the second element, so [1, 4] is smaller than [1, 2], while in the first sort the order remains since only the first value is considered.

edited Jul 28, 2021 at 5:35

answered Jul 28, 2021 at 5:31

Guy

51.2k10 gold badges49 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

VIVID Over a year ago

Thank you for the answer. Now it makes more sense. But could you please elaborate a bit more on how it works? I saw this technique in others' code some time in the past and kind of axiomatically accepted it for myself.

Guy Over a year ago

@VIVID do you want an explanation about how it works internally? the sublists by the first element and if there is an equality the second item in the key is considered. The source code is here if yo know C.

user15801675 · Accepted Answer · 2021-07-28 05:39:06Z

lst = [[1,2], [1,4], [3,4]]
lst.sort(key=lambda x: (x[0], -x[1]))
print(last)

This first checks the first element x[0] then minus x[1] as there is a - sign. So it is -x[1].

Let see the output:

[[1, 4], [1, 2], [3, 4]]

1 is the smallest element. So it is in the first. Now, you may ask that why not [1, 2] is the first. This, it due to presence of - in front of x[1]. So it becomes -4 for the first and -2 for the second.
Mathematically, -4 < -2, so [1, 4] comes first, followed by [1, 2].
[3, 4], 3 is the greatest in the first element of the nested list.

However, in the code:

lst = [[1,2], [1,4], [3,4]]
lst.sort(key=lambda x: x[0])
print(last)

You only take x[0] into consideration. So the list is not sorted.

Collectives™ on Stack Overflow

Python: Sorting with lambda key confusion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related