1 month

# Coding Patterns: Top K Numbers

Top K numbers pattern is very useful to solve the problems that ask us to find the top / smallest / frequent K elements among a given set.

If the problem asking us to find the top / smallest / frequent K elements among a given set, we need to think about Top K numbers  pattern.

LeetCode 215 - Kth Largest Element in an Array [medium]

Given an integer array `nums` and an integer `k`, return the `kth` largest element in the array.

Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

You must solve it in `O(n)` time complexity.

We can use Heap data structure to keep track of K elements.

Solution 1:

import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums = [-elem for elem in nums]
heapq.heapify(nums)
for i in range(k - 1):
heapq.heappop(nums)
return - heapq.heappop(nums)

Time ComplexityO(N log K).   Space ComplexityO(K)

Solution 2:

class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[-k]

Time ComplexityO(N log K). The Python list `sort()` has been using the Timsort algorithm. Timsort is a kind of adaptive sorting algorithm based on merge sort and insertion sort.

Note: Both sort and sorted are used to sort the elements in a list. There are two differences :

* Sorted() is an in-built Python function while sort() is a method of the class list.

* Sorted() returns a list with its element sorted while sort() is an in-place method.sort()  updates the original list.

973. K Closest Points to Origin

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the X-Y plane and an integer `k`, return the `k` closest points to the origin `(0, 0)`.

The distance between two points on the X-Y plane is the Euclidean distance (i.e., `√(x1 - x2)2 + (y1 - y2)2`).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Input: points = [[1,3],[-2,2]], k = 1       Output: [[-2,2]]

Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Solution 1:

class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for x, y in points:
dist = (x)** 2 + (y)** 2
heap.append([dist, x, y])
result = []
heapq.heapify(heap)
for i in range(k):
dist, x, y = heapq.heappop(heap)
result.append([x, y])
return result

Solution 2:

class Solution:

def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

points.sort(key = lambda p: p*p+p*p)

return points[:k]

#### Responses(0)  Related