Top K Frequent Words

Problem Statement: Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] consists of lowercase English letters.
• k is in the range [1, The number of unique words[i]]

Source: https://leetcode.com/problems/top-k-frequent-words/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

    def topKfrequent(self, words, k):
        """
        words: List[str]
        k: int
        return: List[str]
        """
        counter={}
        for i in words:
            if i in counter:
                counter[i]+=1
            else:
                counter[i]=1
    
        heap=[]
        for key,value in counter.items():
            heapq.heappush(heap, (-1*value, key))
    
        return [heapq.heappop(heap)[1] for word in range(k)]

Thought Process / Explanation:

Heapq uses a priority queue to implement heaps. So by default, we will get lexicographically sorted strings. Now the task is to main freq and word pair in a heap where the top is max-freq.

Thank You!

K Closest Points to Origin

Problem Statement: 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).

Example 1:

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]].

Constraints:

• 1 <= k <= points.length <= 104
• -104 < xi, yi < 104

Source: https://leetcode.com/problems/k-closest-points-to-origin/

Leetcode Difficulty: Medium

Code:

    def get_distance(self, point):
        origin=[0,0]
        return ((point[1]-origin[1])**2 + (point[0]-origin[0])**2)**0.5
    
    def kclosest(self, points, k):
        """
        points: List[List[int]]
        k: int
        return: List[List[int]]
        """
        
        heap=[]
        for point in points[:k]:
            distance = self.get_distance(point)
            heapq.heappush(heap, (-1*distance,point))
        
        for point in points[k:]:
            distance = -1*self.get_distance(point)
            
            top = heapq.heappop(heap)
            
            if top[0]<distance:
                heapq.heappush(heap, (distance,point))
            else:
                heapq.heappush(heap, top)
        
        return [heapq.heappop(heap)[1] for _ in range(k)]

Thought Process / Explanation:

The keyword "k closest" hints me to give a shot to heaps. Since heapq implements min-heap by default. We multiply the distance by -1 to make sure the absolute largest is on top every time (acting as max-heap). The rest is just a comparison from the top and updating things.

Thank You!

Top K Frequent Elements

Problem Statement: Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

• 1 <= nums.length <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Source: https://leetcode.com/problems/top-k-frequent-elements/

Leetcode Difficulty: Medium

Asked in: Amazon

Code:

    def topKfrequent(self, nums, k):
        """
        nums: List[int]
        k: int
        return: List[int]
        """
        counter={}
        for i in nums:
            if i in counter:
                counter[i]+=1
            else:
                counter[i]=1
        
        heap=[]
        for idx, (key,value) in enumerate(counter.items()):
            if idx<k:
                heapq.heappush(heap,(value,key))
            else:
                top=heapq.heappop(heap)
                if top[0]<value:
                    heapq.heappush(heap,(value,key))
                else:
                    heapq.heappush(heap,top)
           
        return [heapq.heappop(heap)[1] for _ in range(k)]

Thought Process / Explanation:

The keyword "k frequent" hints me to give a shot to heaps. Heap of size K is enough as we will need to return atmost k elements. Since we need to return k frequent, we can create a min-heap with (value,key) pair and later compare it with the value on the pop operation. Finally, return the key corresponding to each value in min-heap.

Thank You!

Kth Largest Element in an Array

 Problem Statement: 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.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

Source: https://leetcode.com/problems/kth-largest-element-in-an-array/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

import heapq

def findKthlargest(self, nums, k):
        """
        nums: List[int]
        k: int
        return: int
        """
        
        heap=[]
        
        for i in nums[:k]:
            heapq.heappush(heap, i)
        
        for i in nums[k:]:
            top = heapq.heappop(heap)
            if i>top:
                heapq.heappush(heap, i)
            else:
                heapq.heappush(heap, top)
        
        
        return heapq.heappop(heap)

Thought Process / Explanation:

The keyword "kth largest" hints me to give a shot to heaps. Heap of size K is enough as we will need to return atmost k elements even if the problem is extended. Min heap suits here because we can replace the top if it's shorter than the new element to be examined.

Thank You!