Editor's note: This guide is part of a series on useful Python tricks. Read more about the series and find links the other guides here.
This is the second of two guides on iterable Python tricks. In the first, we learned many useful iterable Python tricks. Check it out if you missed it.
In this guide, we will continue to add more iterable python tricks to our arsenal.
The map
function applies a function to all the items in a given iterable.
1map(function, iterables) -> iterables
map
returns a list of the results after applying the given function to each item of a given iterable.
1"""map to node children recursively"""
2# L104: get depth in binary tree
3def max_depth(root: TreeNode) -> int:
4 return 1 + max(map(maxDepth, (root.left, root.right))) if root else 0
5
6"""comparison map find with map index"""
7# L290: given a pattern and a string words, find if words follows the same pattern.
8# i.e. pattern = 'abba', words = 'dog cat cat dog'
9def valid_word_pattern(pattern: str, words: str) -> bool:
10 s, t = pattern, words.split()
11 return list(map(s.find, s)) == list(map(t.index, t))
12
13"""map dict.get"""
14# L506: given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal"
15def find_relative_ranks(nums: List[int]) -> List[str]:
16 sorted_nums = sorted(nums, reverse=True)
17 rank = ["Gold Medal", "Silver Medal", "Bronze Medal"] + list(map(str, range(4, len(nums) + 1)))
18 return list(map(dict(zip(sorted_nums, rank)).get, nums))
reduce
returns a single value constructed by applying a rolling computation to sequential pairs of values in a given iterable.
1reduce(function, sequence[, initial]) -> value
1# L136: every numbers appears twice except for one, find that single one
2def single_number(nums: List[int]) -> int:
3 return reduce(lambda x, y: x ^ y, nums)
4
5# L47: generate all possible permutations
6def permute(nums: List[int]) -> List[List[int]]:
7 return reduce(lambda P, n: [p[:i] + [n] + p[i:] for p in P for i in range(len(p)+1)], nums, [[]])
zip
takes an iterator that aggregates elements based on the iterables passed and returns an iterator of tuples. Its syntax is as follows:
1zip(*iterables) -> iterator
Notice the iterator stops when the shortest iterable is exhausted. If you prefer to match the longest iterable, you can try zip_longest(*iterables, fillvalue=None)
in itertools
module.
1a = [1,2,3]
2b = ['one','two','three']
3zipped=zip(a,b)
4list(zipped)
5# output: [(1, 'one'), (2, 'two'), (3, 'three')]
1"""construct dict"""
2keys = ['a', 'b', 'c']
3vals = [1, 2, 3]
4zipped_dict = dict(zip(keys, vals))
5
6"""difference of neighbor pairs"""
7arr, diffs = [1, 2, 3, 4, 5], []
8for pre, post in zip(arr[:-1], arr[1:]): # zip(arr, arr[1:]) is ok too, zip matches the shortest
9 diffs.append(post - pre)
10
11"""transpose matrix"""
12# L867: The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
13def transpose(matrix: List[List[int]]) -> List[List[int]]:
14 return list(map(list, zip(*matrix)))
15
16"""zip into a set"""
17# L290: given a pattern and a string words, find if words follows the same pattern.
18# i.e. pattern = 'abba', words = 'dog cat cat dog'
19def valid_word_pattern(pattern: str, words: str) -> bool:
20 s, t = pattern, words.split()
21 return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)
We use the operators *
(for tuples) and **
(for dictionaries) to unpack arguments in Python.
1def product(a, b):
2 return a * b
3
4"""use * to unpack tuple, list or other iterables"""
5param_tuple = (2, 3)
6product(*param_tuple)
7# output: 6
8
9"""use ** to unpack dict"""
10param_dict = {'a': 2, 'b': 3}
11product(**param_dict)
12# output: 6
More advanced usages of unpacking:
1"""get rest of all"""
2a, *b, c = range(5)
3# b = [1, 2, 3]
4[(c, *d, [*e]), f, *g] = [[1, 2, 3, 4, [5, 5, 5]], 6, 7, 8]
5# d = [2, 3, 4], e = [5, 5, 5], g = [7, 8]
6
7"""merge dicts"""
8a = {'1': 1, '2': 2}
9b = {'2': 3, '4': 4}
10merged_dict = {**a, **b} #{'1': 1, '2': 3, '4': 4}
11
12"""[*a] = list(a), [*zip(*matrix)]: transpose matrix"""
13# L54: traverse matrix in spiral order.
14def traverse_spiral_order(matrix: List[List[int]]) -> List[int]:
15 return matrix and [*matrix.pop(0)] + traverse_spiral_order([*zip(*matrix)][::-1])
The sum
function takes an iterable and returns the sum of items in it. Its syntax is as follows:
1sum(iterable[, start]) -> number
1"""sum"""
2# L771: S is stones you have, J is types of stones which are jewels, and you want to know how many stones are also jewels.
3def num_jewels_in_stones(J: str, S: str) -> int:
4 return sum(map(J.count, S))
5
6# L389: string t is generated by random shuffling string s and then add one more letter at a random position, find the letter.
7def find_the_difference(s: str, t: str) -> str:
8 return chr(sum(map(ord, t)) - sum(map(ord, s)))
9
10# L266: determine if a permutation of the string could form a palindrome
11def can_permute_palindrome(s: str) -> bool:
12 """at most one odd count character"""
13 return sum(v % 2 for v in Counter(s).values()) <= 1
The max
function returns the largest of the input values. Its syntax is as follows:
1max(iterable[, default=obj, key=func]) -> value
The min
function is similar to this.
1"""max"""
2# L169: find the majority element which appears more than ⌊ n/2 ⌋ times.
3def majority_element(nums: List[int]) -> int:
4 counts = Counter(nums)
5 return max(counts.keys(), key=counts.get)
6
7"""min"""
8# L14: find the longest common prefix string amongst an array of strings.
9def longest_common_prefix(strs: List[str]) -> str:
10 shortest = min(strs, key=len)
11 for i, ch in enumerate(shortest):
12 if any(s[i] != ch for s in strs):
13 return shortest[:i]
14 return shortest
The any
function tests whether any item in the iterable evaluates to True
to not. Its syntax is as follows:
1any(iterable) -> bool
The all
function is similar to this.
1"""any"""
2# L36: determine if a 9x9 Sudoku board is valid, which means 1-9 in row, column, 3x3 sub-boxes
3def is_valid_sudoku(board: List[List[str]]) -> bool:
4 seen = set()
5 return not any(x in seen or seen.add(x)
6 for i, row in enumerate(board)
7 for j, c in enumerate(row)
8 if c != '.'
9 for x in ((c, i), (j, c), (i/3, j/3, c)))
10
11"""all"""
12# L766: a matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
13def is_toeplitz_matrix(matrix: List[List[int]]) -> bool:
14 return all(r == 0 or c == 0 or matrix[r-1][c-1] == val
15 for r, row in enumerate(matrix)
16 for c, val in enumerate(row))
17
18# L246: verify the number is strobogrammatic, strobogrammatic number looks the same when rotated 180 degrees
19def is_strobogrammatic(num: str) -> bool:
20 return all(map('696 00 11 88'.count, map(operator.add, num, num[::-1])))
21
22# L261: given n nodes labeled from 0 to n-1 and a list of undirected edges, check whether these edges make up a valid tree.
23def valid_tree(n: int, edges: List[List[int]]) -> bool:
24 """all check in union find"""
25 parent = range(n)
26 def find(x):
27 return x if parent[x] == x else find(parent[x])
28 def union(xy):
29 x, y = map(find, xy)
30 parent[x] = y
31 return x != y
32 return len(edges) == n-1 and all(map(union, edges))
bisect
module provides support for maintaining a list in sorted order without having to sort the list after each insertion.
The bisect_left
/bisect
function locates the insertion point for x
in a
to maintain sorted order.
1bisect.bisect_left(a, x[, lo=0, hi=len(a)]) -> int
In the following examples, bisect
usage is generalized to customized iterables. The key point is the idea of constructing an appropriate iterable
. We need to use __getitem__
for bisect
to index.
1"""use binary search to find the first number that's less than or equal to the last."""
2# L153: find the minimum element in rotated sorted array
3def find_min_in_rotated_sorted_arr(self, nums: List[int]) -> int:
4 """construct iterable which distinguish the two parts of rotated array"""
5 self.__getitem__ = lambda i: nums[i] <= nums[-1]
6 return nums[bisect.bisect(self, False, 0, len(nums))]
7
8"""construct a boolean iterable and use binary search"""
9# L4: find the median of the two sorted arrays
10def find_median_in_two_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
11 a, b = sorted((nums1, nums2), key=len)
12 m, n = len(a), len(b)
13 after = (m + n - 1) // 2
14 class Range:
15 def __getitem__(self, i):
16 return after-i-1 < 0 or a[i] >= b[after-i-1]
17 i = bisect.bisect_left(Range(), True, 0, m)
18 nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
19 return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2
In this guide, we have learned more iterable Python tricks, such as map/reduce, pack/unpack, and the advanced skills for some built-in functions. I hope some of them will be useful for you.
There are other advanced techniques not mentioned here. This guide simply offers a good starting point to travel in the Python world. You can also download an example notebook, iterables.ipynb, from Github.
This guide is one of a series of Python tricks guides:
I hope you enjoyed it. If you have any questions, you're welcome to contact me at [email protected].