leetCodeArrayMedium.swift

// https://leetcode.com/problems/top-k-frequent-elements/
// O(n), O(n)
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
      var freqDict = [Int : Int]()
      var bucket = [Int : [Int]]()
      var result = [Int]()
      var topFreq = 0

      // O(n)
      for num in nums {
          let newFreq = freqDict[num, default: 0] + 1
          freqDict[num] = newFreq
          topFreq = max(topFreq, newFreq)
      }

      // O(n)
      for (num, freq) in freqDict {
          bucket[freq, default: []].append(num)
      }

      // O(topFreq)
      while result.count < k {
          if let nums = bucket[topFreq] {
              result.append(contentsOf: nums)
          }
          topFreq -= 1
      }

      return result
  }