Comparators in Python
tags: public, programming
The LeetCode problem in question: Here
As one usually does (obviously), I was doing a Daily LeetCode challenge. The problem gives you an input of an array of integers, and they must be arranged so that their combined string concatenation number is the largest it could possibly be.
I initially thought of sorting the numbers based on their leftmost number, since we want to maximize the biggest digits first. However, this reasoning fell short when I encountered the values 3 and 32. According to my thought process, 32 is greater than 3, so the ordering should result in 323. However, the opposite, 332, is actually greater than 323, meaning that I would need to place 3, a smaller value, to the left first. I was aware that this problem required some sort of sorting, but not the typical sorting that I was used to. Begrudgingly, I hovered my mouse over the solutions and to my surprise, learned a new feature in Python!
Turns out, having custom comparators isn't anything new, and I should've been aware of this. After all, I've used them in C++ before. They go something like this:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//Descending order comparator
bool compare(int a, int b) {
return a > b;
}
int main() { vector<int> vec({1,2,3});
sort(vec.begin(), vec.end(), compare);
cout << "Sorted vector: ";
for(int val : vec) {
cout << val << " ";
}
/*
We would expect to see:
Sorted vector: 3 2 1
*/
return 0;
}How the comparator works in C++ is that it takes a look at the two values and tries to maintain the order which makes an expression true. Since a comes before b, we want to set a > b to be true so that the vector is sorted in a manner that has the left value greater than the values to its right. (for descending order)
However, in Python, it's slightly different. In a Python comparator, you return 1 if you want the right value to have priority, and you return -1 if you want the left value to have priority. We can implement all this using the cmp_to_key function from the functools module. Let's see how we can use this in this LeetCode problem:
def compare(x,y):
if x + y > y + x:
return -1
else:
return 1Let's say x = 3 and y = 32 like in our example earlier. Since we know that since 332 is bigger than 323, we would want x to take priority in our sorting. Hence, we return -1. Otherwise, if x = 32 and y = 3, then we'd want the y to take priority in this case, so we return 1 for this condition. The rest of the code follows:
from functools import cmp_to_key
Class Solution:
def largestNumber(self, nums: List[int]) -> str:
def compare(x,y):
if x + y > y + x:
return -1
else:
return 1
strNums = list(map(str,nums))
strNums.sort(key = cmp_to_key(compare))
#Handle edge case where the first digit is 0
return "".join(strNums) if strNums[0] != '0' else '0'As you can see, it does pretty well performance-wise:
