# 128. Longest Consecutive Sequence

Difficulty: Medium

Frequency: N/A

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given `[100, 4, 200, 1, 3, 2]`,
The longest consecutive elements sequence is `[1, 2, 3, 4]`. Return its length: `4`.

Your algorithm should run in O(n) complexity.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int longestConsecutive(vector<int> nums) {
unordered_set<int> s;
for (int n : nums) s.insert(n);
int maxLen = 1;
for (int n : nums) {
if (s.empty()) break;
int curNum = n;
int curLen = 0;
while (s.count(curNum)) {
s.erase(curNum);
curLen++;
curNum++;
}
curNum = n - 1;
while (s.count(curNum)) {
s.erase(curNum);
curLen++;
curNum--;
}
maxLen = max(maxLen, curLen);
}
return maxLen;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 325. (Locked)Maximum Size Subarray Sum Equals k

Difficulty: Easy

Frequency: N/A

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Example 1:

Given nums = `[1, -1, 5, -2, 3]`, k = `3`,
return `4`. (because the subarray `[1, -1, 5, -2]` sums to 3 and is the longest)

Example 2:

Given nums = `[-2, -1, 2, 1]`, k = `1`,
return `2`. (because the subarray `[-1, 2]` sums to 1 and is the longest)

Can you do it in O(n) time?

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> m;
int result = 0, cur_sum = 0;
for (int i = 0; i < nums.size(); i++) {
cur_sum += nums[i];
if (cur_sum == k) result = i + 1;
else if (m.find(k - cur_sum) != m.end()) {
result = max(result, i - m[k - cur_sum]);
}
if (m.find(cur_sum) == m.end()) m[cur_sum] = i;
}
return result;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 146. LRU Cache

Difficulty: Hard

Frequency: N/A

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `set`.

`get(key)` – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`set(key, value)` – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class LRUCache{
public:
LRUCache(int capacity) : cap(capacity) { }

int get(int key) {
auto iter = map.find(key);
if (iter == map.end()) return -1;
touch(iter);
return iter->second.first;
}

void set(int key, int value) {
auto iter = map.find(key);
if (iter != map.end()) touch(iter);
else {
if (map.size() == cap) {
map.erase(lru.back());
lru.pop_back();
}
lru.push_front(key);
}
map[key] = {value, lru.begin()};
}
private:

typedef list<int> IntList;
typedef pair<int, IntList::iterator> IntIntList;
typedef unordered_map<int, IntIntList> Map;

int cap;
IntList lru;
Map map;
void touch(Map::iterator iter) {
int key = iter->first;
lru.erase(iter->second.second);
lru.push_front(key);
iter->second.second = lru.begin();
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 244. (Locked)Shortest Word Distance II

Difficulty: Medium

Frequency: N/A

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `"coding”`word2 = `"practice”`, return 3.
Given word1 = `"makes"`word2 = `"coding"`, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
```class WordDistance {
unordered_map<string, vector<int>> dict;
public:
WordDistance(vector<string> words) {
int n = words.size();
for (int i = 0; i < n; i++) {
dict[words[i]].push_back(i);
}
}
int shortest(string word1, string word2) {
vector<int> pos1 = hash[word1];
vector<int> pos2 = hash[word2];
int dist = INT_MAX;
for(auto p1:pos1){
for(auto p2:pos2){
dist = min(dist, abs(p1-p2));
}
}
return dist;
}
};
```

Things to learn:

# 288. (Locked)Unique Word Abbreviation

Difficulty: Easy

Frequency: N/A

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

```a) it                      --> it    (no abbreviation)

1
b) d|o|g                   --> d1g

1    1  1
1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

1
1---5----0
d) l|ocalizatio|n          --> l10n
```

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:

```Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> `false`
isUnique("cart") -> `true`
isUnique("cane") -> `false`
isUnique("make") -> `true````

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
private:
unordered_map<string, vector<string>> dict;
public:
ValidWordAbbr(vector<string> &dictionary) {
for (string s : dictionary) {
int n = s.size();
string key = s[0] + to_string(n - 2) + s[n - 1];
if (dict.find(key) == dict.end()) {
vector<string> val;
val.push_back(s);
dict.insert(make_pair<string, vector<string>>(key, val));
} else dict[key].push_back(s);
}
}
bool isUnique(string word) {
int n = word.size();
string key = word[0] + to_string(n - 2) + word[n - 1];
if (dict.find(key) == dict.end()) return true;
else if (dict[key].size() == 1 && word == dict[key][0]) return true;
return false;
}
}
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 030. Substring with Concatenation of All Words

Difficulty: Hard

Frequency: N/A

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: `"barfoothefoobarman"`
words: `["foo", "bar"]`

You should return the indices: `[0,9]`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

class Solution {
public:
vector findSubstring(string s, vector& words) {
vector results;
if (s.empty() || words.empty()) return results;
int count = words.size(), word_length = words[0].size();
if (s.size() < count * word_length) return results;
int start = 0;
while (start <= s.size() – count * word_length) {
unordered_map dict;
for (int i = 0; i < words.size(); i++) dict[words[i]]++;
dict[tmp]–;
} else break;
}
if (head == start + count * word_length) results.push_back(start);
start++;
}
return results;
}
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree `{1,#,2,3}`,

```   1
\
2
/
3
```

return `[1,3,2]`.

Note: Recursive solution is trivial, could you do it iteratively?

Questions:
1. Recursive or iteratively

Test Cases:

1. [#] empty
2. [1] root only
3. [1, 2, #, 3, #, 4] all left
4. [1, #, 2, #, #, #, 3] all right
5. [1, #, 2, 3] normal

Solution 1:
Data structure:
vector, tree
Method:
Recursive:
1. helper(node->left)
2. push(node->val)
3. helper(node->right)
Complexity:
Runtime:
worst case: o(n^2)
average: o(nlogn)
Space:
o(n)
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorderTraverse(root, result);
return result;
}
void inorderTraverse(TreeNode *node, vector<int>& result) {
if (!node) return;
inorderTraverse(node->left, result);
result.push_back(node->val);
inorderTraverse(node->right, result);
}
};
```

Solution 2:
Data structure:
Method:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Tree Traversals:

# 149. Max Points on a Line

Difficulty: Hard

Frequency: N/A

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
int maxCount = 0;
for (int i = 0; i < points.size(); i++) {
int maxTmp = 0, inf = 0, same = 0;
unordered_map<float, int> myMap;
for (int j = i + 1; j < points.size(); j++) {
if (points[j].x == points[i].x) {
if (points[j].y == points[i].y) same++;
else inf++;
}
float slope = (float) (points[j].y - points[i].y) / (float) (points[j].x - points[i].x);
myMap[slope]++;
maxTmp = max(myMap[slope], maxTmp);
}
maxTmp = max(maxTmp, inf) + same + 1;
maxCount = max(maxCount, maxTmp);
}
return maxCount;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 076. Minimum Window Substring

Difficulty: Hard

Frequency: N/A

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = `"ADOBECODEBANC"`
T = `"ABC"`

Minimum window is `"BANC"`.

Note:
If there is no such window in S that covers all characters in T, return the empty string `""`.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> myMap;
for (int i = 0; i < t.size(); i++) {
myMap[t[i]]++;
}
int counter = t.size(), begin = 0, end = 0, head = 0, d = INT_MAX;
while (end < s.size()) {
if (myMap.find(s[end]) != myMap.end() && myMap[s[end]] > 0) counter--;
myMap[s[end]]--;
end++;
while (counter == 0) {
if (end - begin < d) {
}
if (myMap.find(s[begin]) != myMap.end() && myMap[s[begin]] == 0) counter++;
myMap[s[begin]]++;
begin++;
}
}
return d == INT_MAX ? "" : s.substr(head, d);
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Check the discussion template.

# 204. Count Primes

Difficulty: Easy

Frequency: N/A

Count the number of prime numbers less than a non-negative number, n.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int countPrimes(int n) {
vector<bool> prime(n, true);
prime[0] = false, prime[1] = false;
for (int i = 0; i < sqrt(n); i++) {
if (prime[i]) {
for (int j = i*i; j < n; j+=i) prime[j] = false;
}
}
return count(prime.begin(), prime.end(), true);
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: