Solutions

Easy

Medium

  1. Longest Substring with At Least K Repeating Characters

    Solution
     1class Solution:
 2	def longest(self, s, max_distinct, min_repeat):
 3		""" 
 4		returns longest substring with 
 5		- at most 'max_distinct' distinct characterrs
 6		- each repeating >= min_repeat times
 7		"""
 8		n = len(s)
 9		counts = defaultdict(lambda:0)
10		max_len = 0
11		# distinct_key_count: stores the number of distinct keys
12		# valid_key_count: stores the number of keys repeating >= k times
13		distinct_key_count, valid_key_count = 0, 0
14		l = 0
15		for r in range(n):
16			counts[s[r]] += 1
17			if counts[s[r]] == 1:
18				distinct_key_count += 1
19			if counts[s[r]] == min_repeat:
20				valid_key_count += 1
21			while distinct_key_count > max_distinct and l <= r:
22				counts[s[l]] -= 1
23				if counts[s[l]] == 0:
24					distinct_key_count -= 1
25				if counts[s[l]] == min_repeat-1:
26					valid_key_count -= 1
27				l += 1
28			if distinct_key_count == valid_key_count:
29				max_len = max(max_len, r-l+1)
30		return max_len
31	def longestSubstring(self, s: str, k: int) -> int:		
32		total_distinct = len(set(s))
33		max_len = 0
34		for max_distinct in range(1, total_distinct + 1):
35			max_len = max(max_len, self.longest(s, max_distinct, k))
36		return max_len

  2. Surrounded Regions

  3. Clone Graph

    Solution
     1/*
 2// Definition for a Node.
 3class Node {
 4public:
 5	int val;
 6	vector<Node*> neighbors;
 7	Node() {
 8		val = 0;
 9		neighbors = vector<Node*>();
10	}
11	Node(int _val) {
12		val = _val;
13		neighbors = vector<Node*>();
14	}
15	Node(int _val, vector<Node*> _neighbors) {
16		val = _val;
17		neighbors = _neighbors;
18	}
19};
20*/
21
22Node* cloneGraph(Node* node) {
23	unordered_map<Node*,Node*> map;
24	Node* clone = dfs(node, map);
25	return clone;
26}
27
28Node* dfs(Node* node, unordered_map<Node*,Node*>& map)
29{
30	Node* cloneNode = nullptr;
31	if (node == nullptr) 
32		return cloneNode;
33	
34	if (map.find(node) == map.end())
35		map.insert({node, new Node(node->val)});
36	
37	cloneNode = map[node];
38	cloneNode->neighbors.resize(node->neighbors.size());
39	
40	for (int i = 0; i < node->neighbors.size(); ++i)
41	{
42		if (map.find(node->neighbors[i]) == map.end())
43			cloneNode->neighbors[i] = dfs(node->neighbors[i], map);
44		else
45			cloneNode->neighbors[i] = map[node->neighbors[i]];
46	}
47	
48	return cloneNode;
49}

  4. Number of Islands

    Solution
     1int numIslands(vector<vector<char>>& grid) {
 2	int count = 0;
 3	for (int i = 0; i < grid.size(); ++i)
 4	{
 5		for (int j = 0; j < grid[i].size(); ++j)
 6		{
 7			if (grid[i][j] == '1')
 8			{
 9				dfs(grid, i, j);
10				++count;
11			}
12		}
13	}
14	return count;
15}
16
17void dfs(vector<vector<char>>& grid, int i, int j)
18{
19	if (i < 0 || j < 0 || i >= grid.size() || j >= grid[i].size())
20		return;
21	
22	if (grid[i][j] != '1')
23		return;
24	
25	grid[i][j] = '2';
26	dfs(grid, i+1, j);
27	dfs(grid, i-1, j);
28	dfs(grid, i, j+1);
29	dfs(grid, i, j-1);
30}

  5. Course Schedule

  6. Lowest Common Ancestor

  7. Binary Tree Level Order Traversal

    Solution
     1vector<vector<int>> levelOrder(TreeNode* root) {
 2	vector<vector<int>> res;
 3	if (root == nullptr)
 4		return res;
 5	
 6	queue<TreeNode*> q;
 7	q.push(root);
 8	
 9	while (!q.empty())
10	{
11		int size = q.size();
12		vector<int> currentLevel(size);
13		for (int i = 0; i < size; ++i)
14		{
15			TreeNode* curr = q.front();
16			q.pop();
17			currentLevel[i] = curr->val;
18			if (curr->left != nullptr)
19				q.push(curr->left);
20			if (curr->right != nullptr)
21				q.push(curr->right);
22		}
23		res.push_back(currentLevel);
24	}
25	
26	return res;
27}

  8. Binary Tree Zigzag Level Order Traversal

  9. Binary Tree Level Order Traversal II

    Solution
     1vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
 2	vector<vector<int>> res;
 3	if (root == nullptr)
 4		return res;
 5	
 6	queue<TreeNode*> q;
 7	q.push(root);
 8	bool flag = false;
 9	
10	while (!q.empty())
11	{
12		int size = q.size();
13		vector<int> currentLevel(size);
14		
15		for (int i = 0; i < size; ++i)
16		{
17			TreeNode* curr = q.front();
18			q.pop();
19			currentLevel[i] = curr->val;
20			if (curr->left != nullptr)
21				q.push(curr->left);
22			if (curr->right != nullptr)
23				q.push(curr->right);
24		}
25		
26		if (flag)
27		{
28			reverse(currentLevel.begin(), currentLevel.end());
29		}
30		res.push_back(currentLevel);
31		flag = !flag;
32	}
33	
34	return res;
35}

  10. Search in Rotated Sorted Array

    Identify the pivot element (index at which the rotation happens) using binary search. After that, use normal binary search but with index manipulation.

    Solution
     1int findPivotElement(vector<int>& nums)
 2{
 3	int l = 0;
 4	int r = nums.size() - 1;
 5	while (nums[l] > nums[r])
 6	{
 7		int m = l + (r - l) / 2;
 8		if (nums[l] > nums[m])
 9			r = m;
10		else if (nums[m] > nums[r])
11			l = m + 1;
12	}
13	return l;
14}
15
16int search(vector<int>& nums, int target) {
17	int offset = findPivotElement(nums);
18	int l = 0;
19	int r = nums.size()-1;
20	while (l <= r)
21	{
22		int m = l + (r - l) / 2;
23		int real_m = (m + offset) % nums.size();
24		if (nums[real_m] == target)
25			return real_m;
26		else if (nums[real_m] < target)
27			l = m + 1;
28		else
29			r = m - 1;
30	}
31	return -1;
32}

  11. Find First and Last Position of Element in Sorted Array

  12. Search a 2D Matrix

  13. Contains Duplicate

  14. Valid Anagram

  15. Sort an Array

  16. 3Sum

  17. H-Index

  18. Longest Common Subsequence

    Solution
     1int longestCommonSubsequence(string text1, string text2) {
 2	vector<vector<int>> t(text1.size() + 1);
 3	for (int i = 0; i < t.size(); ++i)
 4	{
 5		t[i].resize(text2.size() + 1);
 6		fill(t[i].begin(), t[i].end(), 0);
 7	}
 8	
 9	for (int i = 0; i < text1.size(); ++i)
10	{
11		for (int j = 0; j < text2.size(); ++j)
12		{
13			if (text1[i] == text2[j])
14			{
15				t[i+1][j+1] = 1+t[i][j];
16			}
17			else
18			{
19				t[i+1][j+1] = max(t[i][j+1], t[i+1][j]);
20			}
21		}
22	}
23	
24	return t[text1.size()][text2.size()];
25}

  19. Longest Palindromic Subsequence

  20. Longest Increasing Subsequence

    Solution
     1int lengthOfLIS(vector<int>& nums) {
 2	vector<int> t(nums.size(), 1);
 3	int res = 1;
 4	for (int i = 1; i < nums.size(); ++i)
 5	{
 6		for (int j = 0; j < i; ++j)
 7		{
 8			if (nums[j] < nums[i])
 9			{
10				t[i] = max(t[j] + 1, t[i]);
11			}
12		}
13		res = max(res, t[i]);
14	}
15	return res;
16}

  21. Unique Paths

  22. Unique Paths II

  23. Jump Game

  24. Gas Station

  25. Jump Game II

  26. Letter Combinations of a Phone Number

    Solution
     1class Solution {
 2public:
 3	Solution()
 4	{
 5		map.insert({'2',vector<char>({'a','b','c'})});
 6		map.insert({'3',vector<char>({'d','e','f'})});
 7		map.insert({'4',vector<char>({'g','h','i'})});
 8		map.insert({'5',vector<char>({'j','k','l'})});
 9		map.insert({'6',vector<char>({'m','n','o'})});
10		map.insert({'7',vector<char>({'p','q','r','s'})});
11		map.insert({'8',vector<char>({'t','u','v'})});
12		map.insert({'9',vector<char>({'w','x','y','z'})});
13	}
14
15	vector<string> letterCombinations(string digits) {
16		vector<string> solution;
17		string s;
18		if (digits.size() > 0)
19			backtrack(digits, s, solution, 0);
20		return solution;
21	}
22
23	void backtrack(string& digits, string s, vector<string>& solution, int k)
24	{
25		if (k == digits.size())
26			solution.push_back(s);
27		else
28		{
29			const vector<char>& candidates = map[digits[k]];
30			for (char candidate : candidates)
31			{
32				backtrack(digits, s + candidate, solution, k + 1);
33			}
34		}
35	}
36
37	unordered_map<char,vector<char>> map;
38};

  27. Permutations

    Solution
     1void backtrack(vector<int>& nums, int k, vector<vector<int>>& solution)
 2{
 3	if (k == nums.size())
 4		solution.push_back(nums);
 5	else
 6	{
 7		for (int i = k; i < nums.size(); ++i)
 8		{
 9			swap(nums[k], nums[i]);
10			backtrack(nums, k+1, solution);
11			swap(nums[k], nums[i]);
12		}
13	}
14}

  28. Subsets

    Solution
     1// vector<bool> flag(nums.size(), false);
 2// vector<vector<int>> solution;
 3// call: backtrack(nums, flag, solution, 0);
 4void backtrack(vector<int>& nums,vector<bool>& flag,vector<vector<int>>& solution,int k)
 5{
 6	if (k == nums.size())
 7		processSolution(nums, flag, solution);
 8	else
 9	{
10		// every element can either be in the solution set (true) or not (false)
11		flag[k] = false;
12		backtrack(nums, flag, solution, k+1);
13		flag[k] = true;
14		backtrack(nums, flag, solution, k+1);
15		flag[k] = false;
16	}
17}
18
19void processSolution(vector<int>& nums, vector<bool>& flag, vector<vector<int>>& solution)
20{
21	vector<int> s;
22	for (int i = 0; i < flag.size(); ++i)
23	{
24		if (flag[i])
25			s.push_back(nums[i]);
26	}
27	solution.push_back(s);
28}

  29. Generate Parentheses

    Solution
     1vector<string> generateParenthesis(int n) {
 2	vector<string> res;
 3	if (n == 0)
 4		return res;
 5	
 6	backtrack(res, n, 0, 0, "");
 7	return res;
 8}
 9
10void backtrack(vector<string>& res, int n, int leftCount, int rightCount, string str)
11{
12	if (leftCount == n && rightCount == n)
13		res.push_back(str);
14	else
15	{
16		// the key idea is to prune the backtrack tree for impossible moves
17		// left move is possible when leftCount < n
18		// right move is possible when leftCount > rightCount
19		if (leftCount < n)
20			backtrack(res, n, leftCount + 1, rightCount, str + "(");
21		if (leftCount > rightCount)
22			backtrack(res, n, leftCount, rightCount + 1, str + ")");
23	}
24}

  30. Kth Largest Element in an Array

  31. Search a 2D Matrix II

  32. Longest Substring with At Least K Repeating Characters

  33. Count Good Nodes in a Binary Tree

    Solution
     1int goodNodes(TreeNode* root) {
 2	if (root == nullptr)
 3		return 0;
 4	int count = 0;
 5	helper(root, root->val, count);
 6	return count;
 7}
 8
 9void helper(TreeNode* root, int maxSoFar, int& count)
10{
11	if (root == nullptr)
12		return;
13	
14	if (root->val >= maxSoFar)
15	{
16		++count;
17		maxSoFar = root->val;
18	}
19	
20	helper(root->left, maxSoFar, count);
21	helper(root->right, maxSoFar, count);
22}

  34. Path Sum II

    Solution
     1vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
 2	vector<vector<int>> solution;
 3	if (root == nullptr)
 4		return solution;
 5	
 6	vector<int> path;
 7	path.resize(5000);
 8	path[0] = root->val;
 9	
10	backtrack(root, targetSum, root->val, solution, path, 0);
11	
12	return solution;
13}
14
15void backtrack(TreeNode* root,int targetSum,int runningSum,vector<vector<int>>& solution,vector<int>& path,int lastIndex)
16{
17	if (is_leaf(root) && targetSum == runningSum)
18	{
19		vector<int> copy = path;
20		copy.resize(lastIndex+1);
21		solution.push_back(copy);
22	}
23	
24	if (root->left != nullptr)
25	{
26		path[lastIndex+1] = root->left->val;
27		backtrack(root->left, targetSum, runningSum+root->left->val, solution, path, lastIndex+1);
28	}
29	
30	if (root->right != nullptr)
31	{
32		path[lastIndex+1] = root->right->val;
33		backtrack(root->right, targetSum, runningSum+root->right->val, solution, path, lastIndex+1);
34	}
35}
36
37bool is_leaf(TreeNode* root)
38{
39	return root->left == nullptr && root->right == nullptr;
40}

  35. Numbers with Same Consecutive Differences

    Solution
     1vector<int> numsSameConsecDiff(int n, int k) {
 2	vector<int> ret;
 3	vector<int> digits(n,0);
 4	
 5	for (int i = 1; i < 10; ++i)
 6	{
 7		digits[0] = i;
 8		backtrack(ret, digits, n, k, 0);
 9	}
10	
11	return ret;
12}
13
14void backtrack(vector<int>& ret, vector<int>& digits, int n, int k, int currIndex)
15{
16	if (currIndex == n-1)
17	{
18		ret.push_back(vectorToInt(digits));
19		return;
20	}
21	
22	if (digits[currIndex]-k >= 0)
23	{
24		digits[currIndex+1] = digits[currIndex]-k;
25		backtrack(ret, digits, n, k, currIndex+1);
26	}
27	
28	if (k != 0 && digits[currIndex]+k < 10)
29	{
30		digits[currIndex+1] = digits[currIndex]+k;
31		backtrack(ret, digits, n, k, currIndex+1);
32	}
33}
34
35int vectorToInt(vector<int>& digits)
36{
37	int ret = 0;
38	for (int i = 0; i < digits.size(); ++i)
39	{
40		ret *= 10;
41		ret += digits[i];
42	}
43	return ret;
44}

  36. Satisfiability of Equlity Equations

    Solution
     1bool equationsPossible(vector<string>& equations) {
 2	vector<int> parents(26);
 3	iota(parents.begin(), parents.end(), 0);
 4	
 5	for (string eqn : equations)
 6	{
 7		int a = eqn[0]-'a';
 8		int b = eqn[3]-'a';
 9		
10		if (eqn[1] == '=')
11		{
12			parents[find(parents, a)] = find(parents, b);
13		}
14	}
15	
16	for (string eqn : equations)
17	{
18		int a = eqn[0]-'a';
19		int b = eqn[3]-'a';
20		
21		if (eqn[1] == '!')
22		{
23			if (find(parents, a) == find(parents, b))
24				return false;
25		}
26	}
27	
28	return true;
29}
30
31int find(const vector<int>& parents, int x)
32{
33	if (parents[x] == x)
34		return x;
35	return find(parents, parents[x]);
36}

  37. Push dominoes

    Solution
     1string pushDominoes(string dominoes) {
 2	vector<int> distL(dominoes.size(), dominoes.size());
 3	vector<int> distR(dominoes.size(), dominoes.size());
 4	
 5	// distance to the closest 'L' on the right, until reset by a counter-balancing 'R'
 6	int pos = -1;
 7	for (int i = dominoes.size()-1; i >= 0; --i)
 8	{
 9		if (dominoes[i] == 'L')
10			pos = i;
11		else if (dominoes[i] == 'R')
12			pos = -1;            
13		if (pos != -1)
14			distL[i] = pos - i;
15	}
16	
17	// distance to the closest 'R' on the left, until reset by a counter-balancing 'L'
18	pos = -1;
19	for (int i = 0; i < dominoes.size(); ++i)
20	{
21		if (dominoes[i] == 'R')
22			pos = i;
23		else if (dominoes[i] == 'L')
24			pos = -1;
25		if (pos != -1)
26			distR[i] = i - pos;
27	}
28	
29	string s;
30	s.resize(dominoes.size());
31	
32	for (int i = 0; i < dominoes.size(); ++i)
33	{
34		if (distL[i] < distR[i])
35			s[i] = 'L';
36		else if (distL[i] > distR[i])
37			s[i] = 'R';
38		else s[i] = dominoes[i];
39	}
40	
41	return s;
42}

  38. Word Search

    Solution
     1bool exist(vector<vector<char>>& board, string word) {
 2	for (int i = 0; i < board.size(); ++i)
 3	{
 4		for (int j = 0; j < board[i].size(); ++j)
 5		{
 6			// the key here is to not store the current forming word but use index to refer 
 7			// to the original word. this way we can prune early when characters mismatch			
 8			int idx = 0;
 9			if (backtrack(board, word, i, j, idx))
10			{
11				return true;
12			}
13		}
14	}
15	
16	return false;
17}
18
19bool backtrack(vector<vector<char>>& board, const string& word, int i, int j, int idx)
20{
21	if (idx == word.size())
22	{
23		return true;
24	}
25	if (i < 0 || i >= board.size() || j < 0 || j >= board[i].size() || board[i][j] == 0 || board[i][j] != word[idx])
26	{
27		return false;
28	}
29	
30	char c = board[i][j];
31	board[i][j] = 0; // mark as visited
32	
33	bool ret =	backtrack(board, word, i-1, j, idx+1) || 
34				backtrack(board, word, i+1, j, idx+1) || 
35				backtrack(board, word, i, j-1, idx+1) || 
36				backtrack(board, word, i, j+1, idx+1);
37	
38	board[i][j] = c; // restore the visited node
39	return ret;
40}

  39. Implement Trie (Prefix Tree)

    Solution
     1class TrieNode
 2{
 3public:
 4	TrieNode() : end(false),children(vector<TrieNode*>(26,nullptr) {}
 5	TrieNode* get(char c) const
 6	{
 7		return children[c-'a'];
 8	}
 9	void set(char c)
10	{
11		children[c-'a'] = new TrieNode();
12	}
13	void setEnd()
14	{
15		end = true;
16	}
17	bool isEnd() const
18	{
19		return end;
20	}
21private:
22	vector<TrieNode*> children;
23	bool end;
24};
25
26class Trie 
27{
28public:
29	Trie() 
30	{
31		root = new TrieNode();
32	}
33
34	void insert(string word) 
35	{
36		TrieNode* node = root;
37		for (char c : word)
38		{
39			if (node->get(c) == nullptr)
40				node->set(c);
41			node = node->get(c);
42		}
43		node->setEnd(true);
44	}
45
46	bool search(string word) 
47	{
48		TrieNode* node = getNode(word);
49		if (node != nullptr && node->isEnd())
50			return true;
51		return false;
52	}
53
54	bool startsWith(string prefix) 
55	{
56		TrieNode* node = getNode(prefix);
57		if (node != nullptr)
58			return true;
59		return false;
60	}
61private:
62	TrieNode* root;
63
64	TrieNode* getNode(const string& word) const
65	{
66		TrieNode* node = root;
67		for (char c : word)
68		{
69			node = node->get(c);
70			if (node == nullptr)
71				break;
72		}
73		return node;
74	}
75};
76
77/**
78* Your Trie object will be instantiated and called as such:
79* Trie* obj = new Trie();
80* obj->insert(word);
81* bool param_2 = obj->search(word);
82* bool param_3 = obj->startsWith(prefix);
83*/

  40. Lexicographical Numbers

    Solution
     1vector<int> lexicalOrder(int n) 
 2{
 3	vector<int> ret;
 4	backtrack(1, n, ret);
 5	return ret;
 6}
 7
 8// for 13
 9// 1->10->(100)->11->(110)->12->(120)->13->(130)->(14)->2->(20)->3->(30)->4->(40)
10void backtrack(int curr, int n, vector<int>& ret)
11{
12	if (curr > n)
13		return;
14
15	ret.push_back(curr);
16	backtrack(curr * 10, n, ret);
17
18	if (curr % 10 != 9)
19		backtrack(curr + 1, n, ret);
20}

  41. Construct Smallest Number From DI String

    Solution
     1string smallestNumber(string pattern) 
 2{
 3	string ret(pattern.size()+1, 0);
 4	vector<bool> used(10, false);
 5
 6	// instead of simulating all possible cases, here we systematically explore only those paths
 7	// that would lead to the solution when the flow reaches the leaf for the first time.
 8	// so need a flag to indicate early return as soon as a leaf node in the recursion tree is found
 9	bool found = false;
10	// since pattern starts from 2nd digit, it's a better idea to pull out the iteration
11	// for the first digit into a separate part instead of making it part of the backtrack method
12	for (int n = 1; n < 10 && !found; ++n)
13	{
14		ret[0] = n;
15		used[n] = true;
16		found = backtrack(0, pattern, ret, used);
17		used[n] = false;
18	}
19
20	for (int n = 0; n < ret.size(); ++n)
21		ret[n] += '0';
22
23	return ret;
24}
25    
26bool backtrack(int k, const string& pattern, string& ret, vector<bool>& used)
27{
28	if (k == pattern.size())
29		return true;
30
31	bool found = false;
32	if (pattern[k] == 'I')
33	{
34		for (int n = ret[k]+1; n < 10 && !found; ++n)
35		{
36			if (!used[n])
37			{
38				ret[k+1] = n;
39				used[n] = true;
40				found = backtrack(k+1, pattern, ret, used);
41				used[n] = false;
42			}
43		}
44	}
45	else
46	{
47		for (int n = ret[k]-1; n > 0 && !found; --n)
48		{
49			if (!used[n])
50			{
51				ret[k+1] = n;
52				used[n] = true;
53				found = backtrack(k+1, pattern, ret, used);
54				used[n] = false;
55			}
56		}
57	}
58	return found;
59}

  42. Letter Case Permutation

    Solution
     1vector<string> letterCasePermutation(string s) 
 2{
 3	vector<string> ret;
 4	backtrack(ret, s, 0);
 5	return ret;
 6}
 7
 8void backtrack(vector<string>& ret, string& s, int k)
 9{
10	if (k == s.size())
11	{
12		ret.push_back(s);
13		return;
14	}
15
16	// recurse once - applies to both letters and digit
17	backtrack(ret, s, k+1);
18	
19	// if it's a letter, then change case and recurse once more
20	if (isLowercase(s[k]) || isUppercase(s[k]))
21	{
22		s[k] = changeCase(s[k]);
23		backtrack(ret, s, k+1);
24		s[k] = changeCase(s[k]);
25	}
26}
27
28bool isLowercase(char c)
29{
30	if (c >= 'a' && c <= 'z')
31		return true;
32	return false;
33}
34
35bool isUppercase(char c)
36{
37	if (c >= 'A' && c <= 'Z')
38		return true;
39	return false;
40}
41
42char changeCase(char c)
43{
44	if (isLowercase(c))
45		return c - ('a'-'A');
46	else if (isUppercase(c))
47		return c + ('a'-'A');
48	return c;
49}

  43. Iterator for Combination

    Solution
     1class CombinationIterator {
 2public:
 3	CombinationIterator(string characters, int combinationLength) {
 4		curr = 0;
 5		length = combinationLength;
 6		string buf(combinationLength, 0);
 7		backtrack(characters, buf, 0, 0);
 8	}
 9
10	string next() {
11		return combinations[curr++];
12	}
13
14	bool hasNext() {
15		return curr < combinations.size();
16	}
17private:
18	// k: index of the result string
19	// j: index of the letter in the sorted characters string to pick from
20	void backtrack(const string& characters, string& buf, int k, int j)
21	{
22		if (k == length)
23		{
24			combinations.push_back(buf);
25			return;
26		}
27
28		// we've already used all the letters in sorted order before 'j'
29		// therefore, to form the result, we loop through all the possible options from 'j'
30		for (int i = j; i < characters.size(); ++i)
31		{
32			buf[k] = characters[i];
33			// !!IMPORTANT!!
34			// since we just used 'i'-th letter, make sure to pass that info correctly
35			// in the next call, the first letter to pick from would be i+1, NOT j+1
36			backtrack(characters, buf, k+1, i+1);
37		}
38	}
39	vector<string> combinations;
40	size_t curr;
41	int length;
42};
43
44/**
45* Your CombinationIterator object will be instantiated and called as such:
46* CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
47* string param_1 = obj->next();
48* bool param_2 = obj->hasNext();
49*/

  44. Implement Rand10() Using Rand7()

    Solution
     1// The rand7() API is already defined for you.
 2// int rand7();
 3// @return a random integer in the range 1 to 7
 4int rand10() 
 5{
 6	int num = 40;
 7	while (num >= 40)
 8		num = (rand7()-1)+(rand7()-1)*7;
 9	return num % 10 + 1;
10}

  45. Most Stones Removed with Same Row or Column

    Solution
     1int removeStones(vector<vector<int>>& stones)
 2{
 3	vector<vector<int>> graph(stones.size());
 4	for (int i = 0; i < stones.size(); ++i)
 5	{
 6		// no self-loop by design
 7		for (int j = i+1; j < stones.size(); ++j)
 8		{
 9			if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
10			{
11				// undirected by design
12				graph[i].push_back(j);
13				graph[j].push_back(i);
14			}
15		}
16	}
17
18	int components = 0;
19	vector<bool> visited(graph.size(), false);
20	for (int i = 0; i < graph.size(); ++i)
21	{
22		if (!visited[i])
23		{
24			dfs(graph, visited, i);
25			++components;
26		}
27	}
28
29	return stones.size() - components;
30}
31
32void dfs(const vector<vector<int>>& graph, vector<bool>& visited, int i)
33{
34	if (visited[i])
35		return;
36
37	visited[i] = true;
38	for (int j = 0; j < graph[i].size(); ++j)
39	{
40		dfs(graph, visited, graph[i][j]);
41	}
42}

  46. Minimum Genetic Mutation

    Solution
     1int minMutation(string startGene, string endGene, vector<string>& bank) 
 2{
 3	// maps string to index in the bank
 4	// would save memory for intermediate nodes if we can refer by index in bank
 5	unordered_map<string, int> dict = populateDict(bank);
 6	
 7	vector<char> choices({'A','C','G','T'});
 8
 9	// we can store indices from bank just by index
10	unordered_set<int> visited;
11
12	queue<int> q;
13	q.push(-1); // -1 for the start gene as that doesn't exist in bank
14	int path = 0;
15
16	while (!q.empty())
17	{
18		// need level order traversal here because we need the path length
19		int size = q.size();
20		for (int i = 0; i < size; ++i)
21		{
22			int u = q.front();
23			q.pop();
24
25			visited.insert(u);
26
27			string& curr = startGene;
28			if (u != -1)
29			{
30				curr = bank[u];
31			}
32
33			if (curr == endGene)
34			{
35				return path;
36			}
37
38			// ensure to change one character at a time at any position of the gene
39			for (int j = 0; j < curr.size(); ++j)
40			{
41				for (char c : choices)
42				{
43					char orig = curr[j];
44					curr[j] = c;
45					if (dict.find(curr) != dict.end() && visited.find(dict[curr]) == visited.end())
46					{
47						q.push(dict[curr]);
48					}
49					curr[j] = orig;
50				}
51			}
52		}
53		++path;
54	}
55
56	return -1;
57}
58
59unordered_map<string, int> populateDict(const vector<string>& bank)
60{
61	unordered_map<string, int> dict;
62	for (int i = 0; i < bank.size(); ++i)
63	{
64		dict.insert({bank[i], i});
65	}
66	return dict;
67}

  47. Minimum Number of Arrows to Burst Balloons

    Solution
     1int findMinArrowShots(vector<vector<int>>& points) 
 2{
 3	auto cmp = [](const vector<int>& a, const vector<int>& b)
 4	{
 5		return (a[1] < b[1]);
 6	};
 7
 8	sort(points.data(), points.data()+points.size(), cmp);
 9	pair<int,int> top = {points[0][0], points[0][1]};
10	int count = 1;
11
12	for (size_t i = 1; i < points.size(); ++i)
13	{
14		pair<int,int> curr({points[i][0], points[i][1]});
15		
16		if (top.second >= curr.first)
17		{
18			if (top.second > curr.second)
19			{
20				top = {curr.first, curr.second};
21			}
22			else
23			{
24				top = {curr.first, top.second};
25			}
26		}
27		else
28		{
29			++count;
30			top = {curr.first, curr.second};
31		}
32	}
33
34	return count;
35}

  48. Sort Characters By Frequency

    Solution
     1string frequencySort(string s) 
 2{
 3    unordered_map<char,int> counts;
 4    for (char c : s)
 5    {
 6        if (counts.find(c) != counts.end())
 7        {
 8            counts.insert({c,0});
 9        }
10        counts[c]++;
11    }
12
13    auto cmp = [&counts](char a, char b)
14    {
15        return counts[a] < counts[b];
16    };
17
18    priority_queue<char,vector<char>,decltype(cmp)> heap(cmp);
19    for (auto kv : counts)
20    {
21        heap.push(kv.first);
22    }
23
24    int i = 0;
25    while (!heap.empty())
26    {
27        char c = heap.top();
28        heap.pop();
29        for (int j = 0; j < counts[c]; ++j)
30        {
31            s[i++] = c;
32        }
33    }
34
35    return s;
36}

  49. Odd Even Linked List

    Solution
     1ListNode* oddEvenList(ListNode* head) 
 2{
 3    if (head == nullptr || head->next == nullptr)
 4        return head;
 5
 6    ListNode* evenHead = head->next;
 7    ListNode* odd = head;
 8    ListNode* even = head->next;
 9
10    while (even != nullptr && even->next != nullptr)
11    {
12        ListNode* oddNext = even->next;
13        ListNode* evenNext = oddNext->next;
14        odd->next = oddNext;
15        even->next = evenNext;
16        odd = odd->next;
17        even = even->next;
18    }
19
20    odd->next = evenHead;
21    return head;
22}

  50. Insert Delete GetRandom O(1)

    Solution
     1class RandomizedSet {
 2public:
 3    RandomizedSet() {
 4        
 5    }
 6    
 7    bool insert(int val) {
 8        if (map.find(val) != map.end())
 9        {
10            return false;
11        }
12        map.insert({val,nums.size()});
13        nums.push_back(val);
14        return true;
15    }
16    
17    bool remove(int val) {
18        if (map.find(val) == map.end())
19        {
20            return false;
21        }
22        // swap the deleted val with the last val in num
23        int lastval = nums[nums.size()-1];
24        nums[map[val]] = lastval;
25        map[lastval] = map[val];
26        map.erase(val);
27        nums.pop_back();
28        return true;
29    }
30    
31    int getRandom() {
32        return nums[rand() % nums.size()];
33    }
34private:
35    vector<int> nums;
36    unordered_map<int,int> map;
37};
38
39/**
40 * Your RandomizedSet object will be instantiated and called as such:
41 * RandomizedSet* obj = new RandomizedSet();
42 * bool param_1 = obj->insert(val);
43 * bool param_2 = obj->remove(val);
44 * int param_3 = obj->getRandom();
45 */

  51. Find Players With Zero or One Losses

    Solution
     1class RandomizedSet {
 2public:
 3    RandomizedSet() {
 4        
 5    }
 6    
 7    bool insert(int val) {
 8        if (map.find(val) != map.end())
 9        {
10            return false;
11        }
12        map.insert({val,nums.size()});
13        nums.push_back(val);
14        return true;
15    }
16    
17    bool remove(int val) {
18        if (map.find(val) == map.end())
19        {
20            return false;
21        }
22        // swap the deleted val with the last val in num
23        int lastval = nums[nums.size()-1];
24        nums[map[val]] = lastval;
25        map[lastval] = map[val];
26        map.erase(val);
27        nums.pop_back();
28        return true;
29    }
30    
31    int getRandom() {
32        return nums[rand() % nums.size()];
33    }
34private:
35    vector<int> nums;
36    unordered_map<int,int> map;
37};
38
39/**
40 * Your RandomizedSet object will be instantiated and called as such:
41 * RandomizedSet* obj = new RandomizedSet();
42 * bool param_1 = obj->insert(val);
43 * bool param_2 = obj->remove(val);
44 * int param_3 = obj->getRandom();
45 */

  52. Valid Sudoku

    Solution
     1class RandomizedSet {
 2public:
 3    RandomizedSet() {
 4        
 5    }
 6    
 7    bool insert(int val) {
 8        if (map.find(val) != map.end())
 9        {
10            return false;
11        }
12        map.insert({val,nums.size()});
13        nums.push_back(val);
14        return true;
15    }
16    
17    bool remove(int val) {
18        if (map.find(val) == map.end())
19        {
20            return false;
21        }
22        // swap the deleted val with the last val in num
23        int lastval = nums[nums.size()-1];
24        nums[map[val]] = lastval;
25        map[lastval] = map[val];
26        map.erase(val);
27        nums.pop_back();
28        return true;
29    }
30    
31    int getRandom() {
32        return nums[rand() % nums.size()];
33    }
34private:
35    vector<int> nums;
36    unordered_map<int,int> map;
37};
38
39/**
40 * Your RandomizedSet object will be instantiated and called as such:
41 * RandomizedSet* obj = new RandomizedSet();
42 * bool param_1 = obj->insert(val);
43 * bool param_2 = obj->remove(val);
44 * int param_3 = obj->getRandom();
45 */

Hard

  1. Binary Tree Maximum Path Sum

  2. Serialize and Deserialize Binary Tree

  3. Alien Dictionary

  4. Word Ladder

  5. Word Ladder II

  6. Cut Off Trees for Golf Event

  7. Median of Two Sorted Arrays

  8. Count of Smaller Numbers After Self

  9. Find Minimum in Rotated Sorted Array II

  10. Maximum Gap

  11. Merge k Sorted Lists

    Solution
     1ListNode* mergeKLists(vector<ListNode*>& lists) {
 2	auto cmp = [](ListNode* n1, ListNode* n2)
 3	{
 4		return n1->val > n2->val;
 5	};
 6	priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> q(cmp);
 7	for (int i = 0; i < lists.size(); ++i)
 8	{
 9		if (lists[i] != nullptr)
10			q.push(lists[i]);
11	}
12	ListNode* head = nullptr;
13	ListNode* last = nullptr;
14	while (!q.empty())
15	{
16		ListNode* node = q.top();
17		q.pop();
18		if (node->next != nullptr)
19			q.push(node->next);
20		if (head == nullptr)
21		{
22			head = node;
23			last = node;
24		}
25		else
26		{
27			last->next = node;
28			last = node;
29		}
30	}
31	return head;
32}

  12. Count of Smaller Numbers After Self

  13. Regular Expression Matching

  14. Maximal Rectangle

  15. Edit Distance

  16. Candy

  17. Create Maximum Number

  18. Patching Array

  19. Word Break II

    Solution
     1vector<string> wordBreak(string s, vector<string>& wordDict) {
 2	vector<string> solution;
 3	unordered_set<string> dict(wordDict.size());
 4	for (const auto& word : wordDict)
 5	{
 6		dict.insert(word);
 7	}
 8	string partial;
 9	backtrack(s, partial, dict, solution, 0);
10	return solution;
11}
12
13void backtrack(string& s, string partial, unordered_set<string>& dict, vector<string>& solution, int k)
14{
15	if (k == s.size())
16	{
17		partial = partial.substr(0, partial.size()-1);
18		solution.push_back(partial);
19	}
20	else
21	{
22		string word;
23		for (int i = k; i < s.size(); ++i)
24		{
25			word += s[i];
26			if (dict.find(word) != dict.end()) 
27			{
28				backtrack(s, partial + word + " ", dict, solution, i+1);
29			}
30		}
31	}
32}

  20. Sudoku Solver

  21. Stickers to Spell Word

  22. Median of Two Sorted Arrays

  23. Reverse Pairs

  24. Count of Smaller Numbers After Self

  25. Word Search II

    Solution
      1class Solution {
  2public:
  3    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
  4        TrieNode* root = populate(words);
  5        vector<string> res;
  6        string buf(10, 0);
  7        
  8        for (int i = 0; i < board.size(); ++i)
  9        {
 10            for (int j = 0; j < board[i].size(); ++j)
 11            {
 12                backtrack(res, board, root, buf, 0, i, j, words.size());
 13            }
 14        }
 15        
 16        return res;
 17    }
 18private:    
 19    void backtrack(vector<string>& res, vector<vector<char>>& board, TrieNode* node, string buf, int k, int i, int j, size_t max)
 20    {
 21        if (i < 0 || i >= board.size() || j < 0 || j >= board[i].size() || !node->contains(board[i][j]) || board[i][j] == 0 || res.size() == max)
 22        {
 23            return;
 24        }
 25        
 26        char orig = board[i][j];
 27        board[i][j] = 0;
 28        buf[k] = orig;
 29
 30        // !!IMPORTANT!! add the word before calling
 31        TrieNode* child = node->get(orig);
 32        if (child->isEnd())
 33        {
 34            child->setEnd(false);
 35            string curr = buf.substr(0,k+1);
 36            res.push_back(curr);
 37        }
 38
 39        backtrack(res, board, child, buf, k+1, i+1, j, max);
 40        backtrack(res, board, child, buf, k+1, i-1, j, max);
 41        backtrack(res, board, child, buf, k+1, i, j+1, max);
 42        backtrack(res, board, child, buf, k+1, i, j-1, max);
 43
 44        board[i][j] = orig;
 45    }
 46
 47    TrieNode* populate(const vector<string>& words)
 48    {
 49        TrieNode* root = new TrieNode();
 50        for (const auto& word : words)
 51        {
 52            TrieNode* node = root;
 53            for (const auto& c : word)
 54            {
 55                if (!node->contains(c))
 56                {
 57                    node->set(c);
 58                }
 59                node = node->get(c);
 60            }
 61            node->setEnd(true);
 62        }
 63        return root;
 64    }
 65};
 66
 67class TrieNode
 68{
 69public:
 70    TrieNode() : children(vector<TrieNode*>(26,nullptr)), end(false) {}
 71    ~TrieNode()
 72    {
 73        for (int i = 0; i < children.size(); ++i)
 74        {
 75            delete children[i];
 76        }
 77    }
 78    void set(char c)
 79    {
 80        if (c >= 'a' && c <= 'z' && children[c-'a'] == nullptr)
 81        {
 82            children[c-'a'] = new TrieNode();
 83        }
 84    }
 85    bool contains(char c) const
 86    {
 87        return get(c) != nullptr;
 88    }
 89    TrieNode* get(char c) const
 90    {
 91        if (c >= 'a' && c <= 'z')
 92        {
 93            return children[c-'a'];
 94        }
 95        return nullptr;
 96    }
 97    void setEnd(bool value)
 98    {
 99        end = value;
100    }
101    bool isEnd() const
102    {
103        return end;
104    }
105private:
106    vector<TrieNode*> children;
107    bool end;
108};

  26. Find Median from Data Stream

    Solution
     1class MedianFinder {
 2public:
 3	MedianFinder() {
 4
 5	}
 6
 7	void addNum(int num) {
 8		// special case when max_heap is empty
 9		if (max_heap.empty())
10		{
11			max_heap.push(num);
12			return;
13		}
14
15		// size maintanining
16		if (max_heap.size() > min_heap.size())
17		{
18			min_heap.push(num);
19		}
20		else
21		{
22			max_heap.push(num);
23		}
24
25		// left_max and right_min invariance maintaining
26		if (max_heap.top() > min_heap.top())
27		{
28			int left_max = max_heap.top();
29			int right_min = min_heap.top();
30			max_heap.pop();
31			min_heap.pop();
32			max_heap.push(right_min);
33			min_heap.push(left_max);
34		}
35	}
36
37	double findMedian() {
38		if (max_heap.size() > min_heap.size())
39			return max_heap.top();
40		return (max_heap.top() + min_heap.top()) / 2.0;
41	}
42private:
43	priority_queue<int,vector<int>,greater<int>> min_heap;
44	priority_queue<int,vector<int>,less<int>> max_heap;
45};
46
47/**
48* Your MedianFinder object will be instantiated and called as such:
49* MedianFinder* obj = new MedianFinder();
50* obj->addNum(num);
51* double param_2 = obj->findMedian();
52*/