# 014. Longest Common Prefix

Difficulty: Easy

Frequency: N/A

Write a function to find the longest common prefix string amongst an array of strings.

My solution:
Data structure:
string, array
Steps:
Complexity:
Runtime: O(m)
Space: O(1)
Test cases:
Corner cases:
1. empty array
Code:
```class Solution {
public:
string longestCommonPrefix(vector&lt;string&gt;&amp; strs) {
string result = &quot;&quot;;
if (strs.size() == 0) return result;
for (int idx = 0; idx &lt; strs.size(); result += strs[idx], idx++) {
for (int v_sz = 1; v_sz &lt; strs.size(); v_sz++) {
if(idx &gt;= strs[v_sz].size() || strs[v_sz][idx] != strs[idx]) {
return result.substr(0, idx);
}
}
}
return result;
}
};
```

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

Things to learn:

# 237. Delete node in a linked list

Difficulty:

Frequency:

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is `1 -> 2 -> 3 -> 4` and you are given the third node with value `3`, the linked list should become `1 -> 2 -> 4` after calling your function.

My solution:
Data structure:
list
Steps:
1. Copy the next node to current node
2. Delete next node
Complexity:
Runtime: O(1)
Space: O(n)
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode *temp = node-&gt;next;
*node = *node-&gt;next;
delete temp;
temp = NULL;
}
};

```

Things to learn:
1. Remember to free the data

# 186. (Locked)Reverse Words in a String II

Difficulty: Medium

Frequency: N/A

Similar to Question [151. Reverse Words in a String], but with the following constraints:

“The input string does not contain leading or trailing spaces and the words are always separated by a single space.”

Could you do it in-place without allocating extra space?

Solution 1:

data structure:

string

steps:

1. reverse the whole string

2. reverse the single word

complexity:

Runtime: O(n)

Space: O(1)

Code:

Challenge:

Rotate an array to the right by k steps in-place without allocating extra space. For instance, with k = 3, the array [0, 1, 2, 3, 4, 5, 6] is rotated to [4, 5, 6, 0, 1, 2, 3].

Things to learn:

# 170. (Locked)Two Sum III – Data structure design

Difficulty: Easy

Frequency: N/A

Design and implement a TwoSum class. It should support the following operations: add and find.

find(value) – Find if there exists any pair of numbers which sum is equal to the value.

For example,

Solution 1:
Data structure:
unordered_map
Complexity:
Time:
find: O(n) worst case  —->not O(1) ? average
Space: O(n)
Code:
```
class two_sum {
unordered_map&lt;int, int&gt; num_count_map;

if (num_count_map[new_num]) {
num_count_map[new_num] = num_count_map[new_num] + 1;
} else {
num_count_map[new_num] = 1;
}
}

bool find(int target) {
unordered_map&lt;int, int&gt;::iterator map_iter;
for (map_iter = num_count_map.begin(); map_iter != num_count_map.end(); map_iter++) {
int num_to_find = target - map_iter-&gt;first;
if (num_count_map.find(num_to_find)) {
if (num_to_find != map_iter-&gt;first) {
return true;
} else {
if (map_iter-&gt;second &gt; 1) {
return true;
}
}
} else {
return false;
}
}
}
}
```

Things to learn:

# 167. (Locked)Two Sum II – Input array is sorted

Difficulty: Medium

Frequency: N/A

Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order.

solution 1:
For each element, do a binary search in the array

solution 2:
Two pointers. Same with 001.

Things to learn:

# 163. (Locked)Missing Ranges

Difficulty: Medium

Frequency: N/A

Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], return [“2”, “4->49”, “51->74”, “76->99”]

Q: What if the given array is empty?
A: Then you should return [“0->99”] as those ranges are missing.

Q: What if the given array contains all elements from the ranges? A: Return an empty list, which means no range is missing.

My solution:
Data structure:
array, list
Steps:
1. For each two adjacent ints in the array(including start – 1 and end + 1), calculate the range
2. how to calculate the range between a and b
2.1 If b – a == 1, nothing
2.2 If b – a == 2, return (b + a) /2
2.3 If b – a > 2, return (a + 1)->(b – 1)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
[0, 1, 3, 50, 75]
Corner cases:
[]
[0, 1, …, 99]
Code:
```
class Solution {
public:
vector&lt;string&gt; findMissingRanges(array&lt;int&gt; vals, int start, int end) {
vector&lt;string&gt; results;
int prev = start - 1;
for (int i = 0; i &lt;= vals.size(); i++) {
// handle the last element(end)
int curr = (i == vals.size()) ? end + 1 : vals[i];
if (curr - prev == 2) {
results.push_back(to_string(prev + 1));
} else if (curr - prev &gt; 2) {
string val = to_string(prev + 1) + &quot;-&gt;&quot; + to_string(curr - 1);
results.push_back(val);
}
prev = curr;
}
return results;
}
}
```

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

Things to learn:
1. It is very import to unify the problem, then do not need to handle special case
2. Need to know handy c++ functions

# 161. (Locked)One Edit Distance

Difficulty: Medium

Frequency: N/A

Given two strings S and T, determine if they are both one edit distance apart.

My solution:
Data structure:
string
Steps:
1. compare the size of S and T.
1.1 If s.size() == t.size(), there should be only one replace operation
1.2 If s.size() – t.size() == 1, or t.size() – s.size() == 1, one insertion or deletion
1.3. otherwise, return false.
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
“” “”
“a” “”
“a” “b”
Code:
```
class Solution {
public:
bool isOneEditDistance(string s, string t) {
if (s.size() &lt; t.size()) s.swap(t);
if (s.size() - t.size() &gt; 1)
return false;
int distance = 0;
for (int i = 0, j = 0; i &lt; s.size(); i++, j++) {
if (s[i] == t[j]) continue;
else if (distance &gt; 1) return false;
else {
distance++;
i = s.size() &gt; t.size() ? i++: i;
}
}
return true;
}
}
```

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

Things to learn:
1. By calling the function itself, you can swap the input parameters.

# 159. (Locked)Longest Substring with At Most Two Distinct Characters

Difficulty: Hard

Frequency: N/A

Given a string S, find the length of the longest substring T that contains at most two distinct characters.

For example,
Given S = “eceba”,
T is “ece” which its length is 3.

Solution 1:
Data structure:
string, unordered_map
Steps:
1. Loop through the string using head and tail index to keep a sliding window.
2. For each char in the string
2.1 If it is not in the map, insert it, num_distinct++
2.2 map[s[tail]]++
2.3 while (num_distinct > 2) map[s[head]]–
2.3.1 If map[s[head]] == 0, num_distince–
2.4 max_length = max(tail – head + 1, max_length)
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
Corner cases:
Code:
```class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int max_length = 0, head = 0, num_distinct = 0;
unordered_map&lt;char, int&gt; count_map;
for (int tail = 0; tail &lt; s.size(); tail++) {
if (!count_map.count(s[tail])) {
num_distinct++;
}
count_map[s[tail]]++;
while (distinct &gt; 2) {
num_distinct--;
i++;
}
max_length = max(max_length, tail - head + 1);
}
return max_length;
}
};
```

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

Things to learn:

# 013. Roman to Integer

Difficulty: Easy

Frequency: N/A

My solution:
Data structure:
unordered_map,string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
```class Solution {
public:
int romanToInt(string s) {
unordered_map&lt;char, int&gt; roman_map = {{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}};
int result = 0;
for (int i = 0; i &lt; s.size(); i++) {
if (i != s.size() &amp;&amp; roman_map[s[i]] &lt; roman_map[s[i + 1]]) {
result -= roman_map[s[i]];
} else {
result += roman_map[s[i]];
}
}
return result;
}
};
```
Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
Things to learn:

# 158. (Locked)Read N Characters Given Read4 II – Call multiple times

Difficulty: Hard

Frequency: N/A

Similar to Question [15. Read N Characters Given Read4], but the read function may be called multiple times.

My solution:
Data structure:
array
Steps:
1. Read from the internal buffer
3. Push the superfluous to the internal buffer
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
```
class Solution {
private:
queue&lt;char&gt; leftover;

public:
int read(char *buf, int n) {
int read_sz = 0, actual_sz = 0;

while (!leftover.empty()) {
if (actual_sz == n) return actual_sz;
buf[actual_sz++] = leftover.front();
leftover.pop();
}

while (actual_sz &lt; n) {
}

// Push the leftover the queue
if (actual_sz &lt; n) {
for (int i = n; i &lt; actual_sz; i++) {
leftover.push(buf[i]);
}
}

int end = min(actual_sz, n);
buf[end] = '\0';
return end;
}
}

```

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

Things to learn: