Daily Coding Challenge #43

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - 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.
Try to solve it in O(n log k) time and O(n) extra space.
*/

class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> m;
// store the frequency per each word
for(string w:words) m[w]++;
// copy to vector for sorting
vector<pair<string,int>> vv(m.begin(),m.end());
sort(vv.begin(),vv.end(),[](pair<string,int>& a, pair<string,int>& b){
// if two words have the same frequency,
// then the word with the lower alphabetical order comes first.
// x.first holds the word
// x.second holds the frequency
return a.second > b.second || a.second == b.second && a.first < b.first;
});
vector<string> ans;
// print first k items
for(int i=0;i<k;i++) ans.push_back(vv[i].first);
return ans;
}
};
``````

``````/*
LeetCode - Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

1
/
3
\
2

Output: [3,1,null,null,2]

3
/
1
\
2
Example 2:

Input: [3,1,4,null,null,2]

3
/ \
1   4
/
2

Output: [2,1,4,null,null,3]

2
/ \
1   4
/
3

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?
*/

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* first=NULL;
TreeNode* second=NULL;
TreeNode* prev=NULL;
void solve(TreeNode* node){
// in-order traversal to search two swapped nodes
if(!node) return;
solve(node->left);
if(prev&&node->val<prev->val){
if(first==NULL) first=prev;
second=node;
}
prev=node;
solve(node->right);
}
void recoverTree(TreeNode* root) {
solve(root);
// swap them back
swap(first->val, second->val);
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!