leetcode

Kth Largest Element in an Array

Kth Largest Element in an Array

sort solution - # O(nlgn) time 28ms

1
2
3
4
5
6
7
8
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return sorted(nums, reverse=True)[k-1]

heapq solution - # O(k+(n-k)lgk) time, min-heap 28ms

1
2
3
4
5
6
7
8
9
import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return heapq.nlargest(k, nums)[k-1]

test code

1
2
3
4
5
6
7
8
In [393]: nums= [3,2,3,1,2,4,5,5,6]
In [394]: k = 4
In [396]: s = Solution(); t = s.findKthLargest(nums, k)
In [397]: t
Out[397]: 4

ref

heapq

1
2
3
4
5
6
7
8
9
10
11
12
13
In [405]: import heapq
In [406]: heapq.nlargest(k, nums)
Out[406]: [6, 5, 5, 4]
In [407]: heapq.nlargest?
Signature: heapq.nlargest(n, iterable, key=None)
Docstring:
Find the n largest elements in a dataset.
Equivalent to:  sorted(iterable, key=key, reverse=True)[:n]
File:      /System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/heapq.py
Type:      function

leet code

leetcode

Rotate Image

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Clean Most Pythonic - 24ms

1
2
3
4
5
6
7
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = map(list, zip(*matrix[::-1]))

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In [13]: m = [
    ...:   [ 5, 1, 9,11],
    ...:   [ 2, 4, 8,10],
    ...:   [13, 3, 6, 7],
    ...:   [15,14,12,16]
    ...: ]
In [14]: zip(*m)
Out[14]: [(5, 2, 13, 15), (1, 4, 3, 14), (9, 8, 6, 12), (11, 10, 7, 16)]
In [15]: m[::-1]
Out[15]: [[15, 14, 12, 16], [13, 3, 6, 7], [2, 4, 8, 10], [5, 1, 9, 11]]
In [16]: zip(*m[::-1])
Out[16]: [(15, 13, 2, 5), (14, 3, 4, 1), (12, 6, 8, 9), (16, 7, 10, 11)]
In [17]: map(list, zip(*m[::-1]))
Out[17]: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
In [18]: m[:] = zip(*m[::-1])
In [18]: m[:] = zip(*m[::-1])
In [19]: m
Out[19]: [(15, 13, 2, 5), (14, 3, 4, 1), (12, 6, 8, 9), (16, 7, 10, 11)]

ref

This syntax is a slice assignment. A slice of [:] means the entire list. The difference between nums[:] = and nums = is that the latter doesn’t replace elements in the original list. This is observable when there are two references to the list

1
2
3
4
5
>>> a = list(range(10))
>>> b = a
>>> a[:] = [0, 0, 0] # changes what a and b both refer to
>>> b
[0, 0, 0]

To see the difference just remove the [:] from the above sequence.

1
2
3
4
5
>>> a = list(range(10))
>>> b = a
>>> a = [0, 0, 0] # a now refers to a different list than b
>>> b
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

What does colon at assignment for list[:] = […] do in Python [duplicate]

leet code

leetcode

Unique Paths

Unique Paths

Math Method

1
2
3
4
5
6
7
8
9
import math
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        return math.factorial(m+n-2) / math.factorial(m-1) / math.factorial(n-1)

Write down your command in a sequence, “right, down, down, right, …” it will always be m+n-2 slots, u just need to insert n-1 “right” commands uniquely in this sequence,and that is just binomial coefficient of m+n-2 choose n-1.

DP Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        aux = [[1 for x in xrange(n)] for x in xrange(m)]
        #print aux
        for i in range(1, m):
            for j in range(1, n):
                aux[i][j] = aux[i][j-1] + aux[i-1][j]
        #print aux
        return aux[-1][-1]

test code

1
2
3
4
5
6
In [329]: s = Solution(); t = s.uniquePaths(3, 2)
[[1, 1], [1, 1], [1, 1]]
[[1, 1], [1, 2], [1, 3]]
In [330]: t
Out[330]: 3

leet code

leetcode

Flatten Nested List Iterator

Flatten Nested List Iterator

Generators Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """
class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.ret = []
        def flat(List):
            for x in List:
                if x.isInteger():
                    yield x.getInteger()
                else:
                    for y in flat(x.getList()):
                        yield y
        self.ret = flat(nestedList)
    def next(self):
        """
        :rtype: int
        """
        return self.value
    def hasNext(self):
        """
        :rtype: bool
        """
        try:
            self.value = next(self.ret)
            return True
        except StopIteration:
            return False
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Stack Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """
class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.stack = nestedList[::-1]
    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop().getInteger()
    def hasNext(self):
        """
        :rtype: bool
        """
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack = self.stack[:-1] + top.getList()[::-1]
        return False
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

leet code

leetcode

Intersection of Two Arrays II

Intersection of Two Arrays II

dict version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        cnt = {}
        res = []
        for x in nums1:
            cnt[x] = cnt.get(x, 0) + 1
        for x in nums2:
            if x in cnt and cnt[x] > 0:
                res.append(x)
                cnt[x] -= 1
        return res

Counter version

1
2
3
4
5
6
7
8
9
10
import collections
class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        a, b = map(collections.Counter, (nums1, nums2))
        return list((a & b).elements())

output

1
2
3
4
In [270]: s = Solution(); t = s.intersect([4,9,5,4], [9,4,9,8,4])
In [271]: t
Out[271]: [9, 4, 4]

leet code