Find Top K sth

In [19]:

from collections import Counter
from typing import List
import heapq, random
import numpy as np
from itertools import chai

692.Top K Frequent Words

Hashmap + Sorting

Given $n$ words,

1. Build Hashmap: $O(n)$
2. Sorting: $O(nlogn)$

Therefore, it takes $O(nlogn)$.

In [7]:

class Solution1:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        ct = Counter(words)
        return sorted(ct.keys(), key=lambda x: (-ct[x], x))[:k]
    
sol1 = Solution1()

In [4]:

words = ["i", "love", "leetcode", "i", "love", "coding"]
k = 3
print(sol.topKFrequent(words, k))

['i', 'love', 'coding']

Hashmap + Heap

1. Build Hashmap takes $O(n)$
2. Build Heap by counts: $O(n)$
3. pop K words from the Heap: $O(klogn)$, where $k \le n$

Therefore, $O(n + klogn)$

In [6]:

class Solution2:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        ct = Counter(words)
        heap = [(-v, k) for k, v in ct.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in range(k)]
    
sol2 = Solution2()

In [8]:

words = ["i", "love", "leetcode", "i", "love", "coding"]
k = 3
print(sol.topKFrequent(words, k))

['i', 'love', 'coding']

451. Sort Characters By Frequency

In [9]:

class Solution:
    def frequencySort(self, s: str) -> str:
        cnt = Counter(s)
        reorder = sorted(cnt.keys(), key=lambda x: -cnt[x])
        ans = ''
        for c in reorder:
            ans += c * cnt[c]
        return ans

sol = Solution()

In [10]:

s = "tree"
print(sol.frequencySort(s))

eetr

In [11]:

class Solution:
    def frequencySort(self, s: str) -> str:
        cnt = Counter(s)
        heap = [(-v, k) for k, v in cnt.items()]
        heapq.heapify(heap)
        ans = ''
        while heap:
            c = heapq.heappop(heap)[1]
            ans += c * cnt[c]
        return ans

sol = Solution()

In [13]:

s = "tree"
print(sol.frequencySort(s))

eert

347. Top K Frequent Elements

The algorithm which use heap datas tructure takes $O(n + klogn)$

In [14]:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        heap = [(-v, k) for k, v in cnt.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in range(k)]

sol = Solution()
nums = [1,1,1,2,2,3]
k = 2
print(sol.topKFrequent(nums, k))

[1, 2]

378. Kth Smallest Element in a Sorted Matrix

Given $n \times n$ matrix, where the each rows and columns of the matrix is sorted in ascending order.
condition: $1 \le k \le n^2$

Unpack and Sorting

Ignored sorted conditions.

1. unpack: $O(n^2)$
2. sorting: $O(n^2logn^2)$

Therefore, $O(n^2logn^2)$

In [44]:

class Solution1:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        unpacked = list(chain.from_iterable(matrix))
        return sorted(unpacked)[k - 1]
sol1 = Solution1()

In [45]:

matrix = \
[[ 1,  5,  9],
 [10, 11, 13],
 [12, 13, 15]]
k = 8
print(sol1.kthSmallest(matrix, k))

13

Unpack and Selection

1. unpack: $O(n^2)$
2. selection(average time): $O(n^2)$

Therefore, $O(n^2)$

In [46]:

class Solution2:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        a = list(chain.from_iterable(matrix))
        def select(p, r, k):
            if p == r: return a[p]
            i = random.randint(p, r)
            a[i], a[r] = a[r], a[i]
            i = p - 1
            for j in range(p, r):
                if a[j] < a[r]:
                    i += 1
                    a[i], a[j] = a[j], a[i]
            a[i + 1], a[r] = a[r], a[i + 1]
            q = i + 1
            if q - p + 1 >= k:
                return select(p, q, k)
            else:
                return select(q + 1, r, k - (q - p + 1))
        return select(0, len(a) - 1, k)

sol2 = Solution2()

In [47]:

print(sol2.kthSmallest(matrix, k))

13

Use Heap, indexing of each node

1. build heap: $O(n^2)$
2. pop k elements: $O(klogn)$

Therefore, $O(klogn)$, but worst case $O(n^2logn)$

For helping understanding of this algorithm, I cited an article’s paragraph and exmaple as follows.

Since the matrix is sorted, we do not need to put all the elements in heap at one time.
We can simply pop and put for k times.
By observation, if we look at the matrix diagonally,
we can tell that if we do not pop matrix[i][j],
we do not need to put on matrix[i][j + 1] and matrix[i + 1][j] since they are bigger.
e.g., given the matrix below:

1 2 4 
3 5 7 
6 8 9

We put 1 first, then pop 1 and put 2 and 3, then pop 2 and put 4 and 5, then pop 3 and put 6…

I cited from this article

In [52]:

class Solution3:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = [(row[0], row, 1) for row in matrix]
        heapq.heapify(heap)

        # Since we want to find kth, we pop the first k elements
        for _ in range(k - 1):
            _, r, i = heap[0]
            if i < len(r):
                heapq.heapreplace(heap, (r[i], r, i + 1))
            else:
                heapq.heappop(heap)
        return heap[0][0]

sol3 = Solution3()

In [53]:

print(sol3.kthSmallest(matrix, k))

13