1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/**
 * Brute Force Approach
 * Time Complexity: O(n log n) - Dominated by the sorting operation
 * Space Complexity: O(n) - For storing the frequency map and result array
 * 
 * @param {string[]} words - Array of words
 * @param {number} k - Number of top frequent words to return
 * @return {string[]} - Top k frequent words
 */
function topKFrequent(words, k) {
  // Count frequency of each word
  const freq = new Map();
  for (const word of words) {
    freq.set(word, (freq.get(word) || 0) + 1);
  }
  
  // Create list of all unique words
  const uniqueWords = Array.from(freq.keys());
  
  // Sort words by frequency (descending) and alphabetically (ascending)
  uniqueWords.sort((a, b) => {
    const freqA = freq.get(a);
    const freqB = freq.get(b);
    if (freqA !== freqB) {
      return freqB - freqA; // Sort by frequency in descending order
    }
    return a.localeCompare(b); // Sort alphabetically if frequencies are equal
  });
  
  // Return top k words
  return uniqueWords.slice(0, k);
}
 
/**
 * Heap (Priority Queue) Approach
 * Note: JavaScript doesn't have a built-in heap, so we'll implement a simple min heap
 * Time Complexity: O(n log k) - Where n is the number of unique words
 * Space Complexity: O(n) - For storing the frequency map and heap
 * 
 * @param {string[]} words - Array of words
 * @param {number} k - Number of top frequent words to return
 * @return {string[]} - Top k frequent words
 */
function topKFrequentHeap(words, k) {
  // Count frequency of each word
  const freq = new Map();
  for (const word of words) {
    freq.set(word, (freq.get(word) || 0) + 1);
  }
  
  // Create a min heap of size k
  // In JavaScript, we'll simulate a heap using an array and manual operations
  const heap = [];
  
  // Helper function to compare two words
  const compare = (a, b) => {
    const freqA = freq.get(a);
    const freqB = freq.get(b);
    if (freqA !== freqB) {
      return freqA - freqB; // Min heap by frequency
    }
    return b.localeCompare(a); // Reverse alphabetical order for min heap
  };
  
  // Helper function to maintain heap property
  const heapify = (i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let smallest = i;
    
    if (left < heap.length && compare(heap[left], heap[smallest]) < 0) {
      smallest = left;
    }
    
    if (right < heap.length && compare(heap[right], heap[smallest]) < 0) {
      smallest = right;
    }
    
    if (smallest !== i) {
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      heapify(smallest);
    }
  };
  
  // Add word to heap
  const addToHeap = (word) => {
    heap.push(word);
    let i = heap.length - 1;
    let parent = Math.floor((i - 1) / 2);
    
    while (i > 0 && compare(heap[i], heap[parent]) < 0) {
      [heap[i], heap[parent]] = [heap[parent], heap[i]];
      i = parent;
      parent = Math.floor((i - 1) / 2);
    }
  };
  
  // Remove top element from heap
  const pollFromHeap = () => {
    const top = heap[0];
    heap[0] = heap[heap.length - 1];
    heap.pop();
    heapify(0);
    return top;
  };
  
  // Add words to heap
  for (const word of freq.keys()) {
    addToHeap(word);
    if (heap.length > k) {
      pollFromHeap();
    }
  }
  
  // Extract words from heap in reverse order
  const result = [];
  while (heap.length > 0) {
    result.unshift(pollFromHeap());
  }
  
  return result;
}
 
/**
 * Bucket Sort Approach
 * Time Complexity: O(m) - Where m is the length of the input array
 * Space Complexity: O(m) - For storing the frequency map and buckets
 * 
 * @param {string[]} words - Array of words
 * @param {number} k - Number of top frequent words to return
 * @return {string[]} - Top k frequent words
 */
function topKFrequentBucket(words, k) {
  // Count frequency of each word
  const freq = new Map();
  for (const word of words) {
    freq.set(word, (freq.get(word) || 0) + 1);
  }
  
  // Create buckets
  const buckets = Array(words.length + 1).fill().map(() => []);
  for (const word of freq.keys()) {
    const count = freq.get(word);
    buckets[count].push(word);
  }
  
  // Sort words in each bucket alphabetically
  for (const bucket of buckets) {
    bucket.sort();
  }
  
  // Collect top k words
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    for (const word of buckets[i]) {
      result.push(word);
      if (result.length === k) {
        break;
      }
    }
  }
  
  return result;
}
 
// Test cases
console.log(topKFrequent(["i", "love", "leetcode", "i", "love", "coding"], 2)); // ["i", "love"]
console.log(topKFrequent(["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], 4)); // ["the", "is", "sunny", "day"]