Top K Frequent Elements

Photo by Zeke Goodyear on Unsplash

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.

Your algorithm’s time complexity must be better than O(n log n), where n is the array's size.

Approach 1: The idea here is to first traverse an array and create a hash map of all numbers and it’s count. The ideal data structure for storing key and value pairs is HashMap. The next step is to sort the HashMap by its value and pick only k elements.

The time complexity of this approach is O(nlogn) and its space complexity is O(n).

Approach 2: Let’s improve our previous solution using a MaxHeap using C# SortedSet<IComparer<object>>. To solve this problem first create a map of each element and its count. Then use a SortedSet to implement MaxHeap and we keep its size equal to k.

Take all the keys of a map and put them in a SortedSet. If the size of a set is greater than k, In that case, we remove the minimum element from the set. Once all the elements of HashMap are put in a set, we only get the top k elements.

The time complexity of this approach is O(nlogk) and its space complexity is O(n).

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The Politics of Developing Games as a Service

Introducing Biconomy

Level Up Your SQL Skills

Decorator Pattern in Go

How to be a rockstar developer in 3 months

Introducing WorkManager

Illustration by Virginia Poltrack

Solving Constraint Problems using Neo4j

Elastic Search Simplified: Part 1

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Koko Eating Bananas

CRACKING THE SYSTEM DESIGN INTERVIEW — The Plan

LeetCode Hard DP Problem [Asked in Google]

Amazon Interview : Reorder Data in Log Files