package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * 692. Top K Frequent Words
 *
 * Given a non-empty list of words, return the k most frequent elements.
 * Your answer should be sorted by frequency from highest to lowest.
 * If two words have the same frequency, then the word with the lower alphabetical order comes first.

 Example 1:
 Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 Output: ["i", "love"]
 Explanation: "i" and "love" are the two most frequent words.
 Note that "i" comes before "love" due to a lower alphabetical order.

 Example 2:
 Input: ["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.

 Note:
 You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
 Input words contain only lowercase letters.

 Follow up:
 Try to solve it in O(n log k) time and O(n) extra space.
 Can you solve it in O(n) time with only O(k) extra space?

 */
public class _692 {

    public static class Solution1 {
        /**
         * O(n) extra space
         * O(nlogk) time
         * */
        public List<String> topKFrequent(String[] words, int k) {
            Map<String, Integer> map = new HashMap<>();
            for (String word : words) {
                map.put(word, map.getOrDefault(word, 0) + 1);
            }

            SortedSet<Map.Entry<String, Integer>> sortedset = new TreeSet<>(
                    (e1, e2) -> {
                        if (e1.getValue() != e2.getValue()) {
                            return e2.getValue() - e1.getValue();
                        } else {
                            return e1.getKey().compareToIgnoreCase(e2.getKey());
                        }
                    });
            sortedset.addAll(map.entrySet());

            List<String> result = new ArrayList<>();
            Iterator<Map.Entry<String, Integer>> iterator = sortedset.iterator();
            while (iterator.hasNext() && k-- > 0) {
                result.add(iterator.next().getKey());
            }
            return result;
        }
    }
}

@@ -214,1061 +214,8 @@
 t;%0A%0A
-/**%0A * 692. Top K Frequent Words%0A *%0A * Given a non-empty list of words, return the k most frequent elements.%0A * Your answer should be sorted by frequency from highest to lowest.%0A * If two words have the same frequency, then the word with the lower alphabetical order comes first.%0A%0A Example 1:%0A Input: %5B%22i%22, %22love%22, %22leetcode%22, %22i%22, %22love%22, %22coding%22%5D, k = 2%0A Output: %5B%22i%22, %22love%22%5D%0A Explanation: %22i%22 and %22love%22 are the two most frequent words.%0A Note that %22i%22 comes before %22love%22 due to a lower alphabetical order.%0A%0A Example 2:%0A Input: %5B%22the%22, %22day%22, %22is%22, %22sunny%22, %22the%22, %22the%22, %22the%22, %22sunny%22, %22is%22, %22is%22%5D, k = 4%0A Output: %5B%22the%22, %22is%22, %22sunny%22, %22day%22%5D%0A Explanation: %22the%22, %22is%22, %22sunny%22 and %22day%22 are the four most frequent words,%0A with the number of occurrence being 4, 3, 2 and 1 respectively.%0A%0A Note:%0A You may assume k is always valid, 1 %E2%89%A4 k %E2%89%A4 number of unique elements.%0A Input words contain only lowercase letters.%0A%0A Follow up:%0A Try to solve it in O(n log k) time and O(n) extra space.%0A Can you solve it in O(n) time with only O(k) extra space?%0A%0A */%0A
 publ
@@ -340,18 +340,16 @@
         
- *
  */%0A    

refactor 692