Skip to content

Commit 7856de9

Browse files
ashishps1ashishps1
committed
add top k elements pattern code
1 parent d590ec3 commit 7856de9

File tree

7 files changed

+684
-0
lines changed

7 files changed

+684
-0
lines changed

‎patterns/c#/TopKElements.cs

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
5+
public class TopKElements {
6+
7+
// K Largest Elements using Sorting
8+
public int[] KLargestElementsSortingApproach(int[] nums, int k) {
9+
Array.Sort(nums, (a, b) => b.CompareTo(a));
10+
return nums.Take(k).ToArray();
11+
}
12+
13+
// K Largest Elements using Max Heap
14+
public int[] KLargestElementsMaxHeapApproach(int[] nums, int k) {
15+
PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
16+
foreach (var num in nums) {
17+
maxHeap.Enqueue(num, num);
18+
}
19+
var result = new int[k];
20+
for (int i = 0; i < k; i++) {
21+
result[i] = maxHeap.Dequeue();
22+
}
23+
return result;
24+
}
25+
26+
// K Largest Elements using Min Heap
27+
public int[] KLargestElementsMinHeapApproach(int[] nums, int k) {
28+
PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
29+
for (int i = 0; i < k; i++) {
30+
minHeap.Enqueue(nums[i], nums[i]);
31+
}
32+
for (int i = k; i < nums.Length; i++) {
33+
minHeap.Enqueue(nums[i], nums[i]);
34+
if (minHeap.Count > k) {
35+
minHeap.Dequeue();
36+
}
37+
}
38+
var result = new int[k];
39+
for (int i = 0; i < k; i++) {
40+
result[i] = minHeap.Dequeue();
41+
}
42+
return result;
43+
}
44+
45+
// Top K Frequent Elements using Sorting
46+
public int[] TopKFrequentElementsSortingApproach(int[] nums, int k) {
47+
var frequencyMap = new Dictionary<int, int>();
48+
foreach (var num in nums) {
49+
if (!frequencyMap.ContainsKey(num)) {
50+
frequencyMap[num] = 0;
51+
}
52+
frequencyMap[num]++;
53+
}
54+
55+
var sortedEntries = frequencyMap.OrderByDescending(e => e.Value).Take(k).Select(e => e.Key).ToArray();
56+
return sortedEntries;
57+
}
58+
59+
// Top K Frequent Elements using Min Heap
60+
public int[] TopKFrequentElementsMinHeapApproach(int[] nums, int k) {
61+
var frequencyMap = new Dictionary<int, int>();
62+
foreach (var num in nums) {
63+
if (!frequencyMap.ContainsKey(num)) {
64+
frequencyMap[num] = 0;
65+
}
66+
frequencyMap[num]++;
67+
}
68+
69+
var minHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => a.CompareTo(b)));
70+
foreach (var entry in frequencyMap) {
71+
minHeap.Enqueue(entry.Key, entry.Value);
72+
if (minHeap.Count > k) {
73+
minHeap.Dequeue();
74+
}
75+
}
76+
77+
var result = new int[k];
78+
for (int i = 0; i < k; i++) {
79+
result[i] = minHeap.Dequeue();
80+
}
81+
return result;
82+
}
83+
84+
// K Closest Points to Origin using Max Heap
85+
private int GetDistance(int[] point) {
86+
return point[0] * point[0] + point[1] * point[1];
87+
}
88+
89+
public int[][] KClosestPointsToOriginMaxHeapApproach(int[][] points, int k) {
90+
PriorityQueue<int[], int> maxHeap = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b - a));
91+
foreach (var point in points) {
92+
maxHeap.Enqueue(point, GetDistance(point));
93+
if (maxHeap.Count > k) {
94+
maxHeap.Dequeue();
95+
}
96+
}
97+
var result = new int[k][];
98+
for (int i = 0; i < k; i++) {
99+
result[i] = maxHeap.Dequeue();
100+
}
101+
return result;
102+
}
103+
}

‎patterns/c++/TopKElements.cpp

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
#include <iostream>
2+
#include <vector>
3+
#include <queue>
4+
#include <unordered_map>
5+
#include <algorithm>
6+
7+
using namespace std;
8+
9+
class TopKElements {
10+
public:
11+
// K Largest Elements using Sorting
12+
vector<int> kLargestElementsSortingAppraoch(vector<int>& nums, int k) {
13+
sort(nums.begin(), nums.end(), greater<int>());
14+
return vector<int>(nums.begin(), nums.begin() + k);
15+
}
16+
17+
// K Largest Elements using Max Heap
18+
vector<int> kLargestElementsMaxHeapAppraoch(vector<int>& nums, int k) {
19+
priority_queue<int> maxHeap(nums.begin(), nums.end());
20+
vector<int> result;
21+
for (int i = 0; i < k; i++) {
22+
result.push_back(maxHeap.top());
23+
maxHeap.pop();
24+
}
25+
return result;
26+
}
27+
28+
// K Largest Elements using Min Heap
29+
vector<int> kLargestElementsMinHeapAppraoch(vector<int>& nums, int k) {
30+
priority_queue<int, vector<int>, greater<int>> minHeap;
31+
for (int i = 0; i < k; i++) {
32+
minHeap.push(nums[i]);
33+
}
34+
for (int i = k; i < nums.size(); i++) {
35+
minHeap.push(nums[i]);
36+
if (minHeap.size() > k) {
37+
minHeap.pop();
38+
}
39+
}
40+
vector<int> result;
41+
while (!minHeap.empty()) {
42+
result.push_back(minHeap.top());
43+
minHeap.pop();
44+
}
45+
return result;
46+
}
47+
48+
// Top K Frequent Elements using Sorting
49+
vector<int> topKFrequentElementsSortingApproach(vector<int>& nums, int k) {
50+
unordered_map<int, int> frequencyMap;
51+
for (int num : nums) {
52+
frequencyMap[num]++;
53+
}
54+
55+
vector<pair<int, int>> freqVec(frequencyMap.begin(), frequencyMap.end());
56+
sort(freqVec.begin(), freqVec.end(), [](pair<int, int>& a, pair<int, int>& b) {
57+
return b.second < a.second;
58+
});
59+
60+
vector<int> result;
61+
for (int i = 0; i < k; i++) {
62+
result.push_back(freqVec[i].first);
63+
}
64+
return result;
65+
}
66+
67+
// Top K Frequent Elements using Min Heap
68+
vector<int> topKFrequentElementsMinHeapApproach(vector<int>& nums, int k) {
69+
unordered_map<int, int> frequencyMap;
70+
for (int num : nums) {
71+
frequencyMap[num]++;
72+
}
73+
74+
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
75+
for (auto& entry : frequencyMap) {
76+
minHeap.push({entry.second, entry.first});
77+
if (minHeap.size() > k) {
78+
minHeap.pop();
79+
}
80+
}
81+
82+
vector<int> result;
83+
while (!minHeap.empty()) {
84+
result.push_back(minHeap.top().second);
85+
minHeap.pop();
86+
}
87+
return result;
88+
}
89+
90+
// K Closest Points to Origin using Max Heap
91+
int getDistance(vector<int>& point) {
92+
return point[0] * point[0] + point[1] * point[1];
93+
}
94+
95+
vector<vector<int>> kClosestPointsToOriginMaxHeapApproach(vector<vector<int>>& points, int k) {
96+
priority_queue<pair<int, vector<int>>> maxHeap;
97+
for (vector<int>& point : points) {
98+
maxHeap.push({getDistance(point), point});
99+
if (maxHeap.size() > k) {
100+
maxHeap.pop();
101+
}
102+
}
103+
104+
vector<vector<int>> result;
105+
while (!maxHeap.empty()) {
106+
result.push_back(maxHeap.top().second);
107+
maxHeap.pop();
108+
}
109+
return result;
110+
}
111+
};

‎patterns/go/top_k_elements.go

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package main
2+
3+
import (
4+
"container/heap"
5+
"sort"
6+
)
7+
8+
// ********** K Largest Elements **********
9+
// K Largest Elements using Sorting
10+
func kLargestElementsSortingApproach(nums []int, k int) []int {
11+
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
12+
return nums[:k]
13+
}
14+
15+
// K Largest Elements using Max Heap
16+
func kLargestElementsMaxHeapApproach(nums []int, k int) []int {
17+
h := &MaxHeap{}
18+
heap.Init(h)
19+
for _, num := range nums {
20+
heap.Push(h, num)
21+
}
22+
result := make([]int, k)
23+
for i := 0; i < k; i++ {
24+
result[i] = heap.Pop(h).(int)
25+
}
26+
return result
27+
}
28+
29+
// K Largest Elements using Min Heap
30+
func kLargestElementsMinHeapApproach(nums []int, k int) []int {
31+
h := &MinHeap{}
32+
heap.Init(h)
33+
for i := 0; i < k; i++ {
34+
heap.Push(h, nums[i])
35+
}
36+
for i := k; i < len(nums); i++ {
37+
heap.Push(h, nums[i])
38+
if h.Len() > k {
39+
heap.Pop(h)
40+
}
41+
}
42+
result := make([]int, k)
43+
for i := 0; i < k; i++ {
44+
result[i] = heap.Pop(h).(int)
45+
}
46+
return result
47+
}
48+
49+
// ********** Helper Structures **********
50+
51+
type MaxHeap []int
52+
type MinHeap []int
53+
54+
func (h MaxHeap) Len() int { return len(h) }
55+
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // Max heap
56+
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
57+
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
58+
func (h *MaxHeap) Pop() interface{} {
59+
old := *h
60+
n := len(old)
61+
x := old[n-1]
62+
*h = old[0 : n-1]
63+
return x
64+
}
65+
66+
func (h MinHeap) Len() int { return len(h) }
67+
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] } // Min heap
68+
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
69+
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
70+
func (h *MinHeap) Pop() interface{} {
71+
old := *h
72+
n := len(old)
73+
x := old[n-1]
74+
*h = old[0 : n-1]
75+
return x
76+
}
77+
78+
// ********** Main **********
79+
80+
func main() {
81+
// Example test cases
82+
nums := []int{3, 2, 1, 5, 6, 4}
83+
k := 2
84+
85+
// Sorting Approach
86+
result := kLargestElementsSortingApproach(nums, k)
87+
fmt.Println("K Largest Elements (Sorting Approach):", result)
88+
89+
// Max Heap Approach
90+
result = kLargestElementsMaxHeapApproach(nums, k)
91+
fmt.Println("K Largest Elements (Max Heap Approach):", result)
92+
93+
// Min Heap Approach
94+
result = kLargestElementsMinHeapApproach(nums, k)
95+
fmt.Println("K Largest Elements (Min Heap Approach):", result)
96+
}

0 commit comments

Comments
 (0)