Difficulty: Easy

Frequency: N/A

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n` versions `[1, 2, ..., n]` and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)` which will return whether `version` is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```// Forward declaration of isBadVersion API.

class Solution {
public:
int left = 1, right = n, mid;
while (left < right) {
mid = left + (right - left) / 2;
if (!isBadVersion(mid)) left = mid + 1;
else right = mid;
}
return left;
}
};
```

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

Things to learn:

# 042. Trapping Rain Water

Difficulty: Hard

Frequency: N/A

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given `[0,1,0,2,1,0,1,3,2,1,2,1]`, return `6`. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```class Solution {
public:
int trap(vector<int>& height) {
if (height.size() <= 2) return 0;
int sum = 0, n = height.size();
vector<int> leftMax(n, 0);
vector<int> rightMax(n, 0);
for (int i = 1; i < n; i++) leftMax[i] = max(leftMax[i - 1], height[i - 1]);
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = max(rightMax[i + 1], height[i + 1]);
int minHeight = min(leftMax[i], rightMax[i]);
if (minHeight > height[i]) sum += minHeight - height[i];
}
return sum;
}
};
```

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.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:

# 061. Rotate List

Difficulty: Medium

Frequency: N/A

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given `1->2->3->4->5->NULL` and k = `2`,
return `4->5->1->2->3->NULL`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int len = 1;
while (tail->next) {
len++;
tail = tail->next;
}
if (k = k % len) {
for (int i = 0; i < len - k; i++) tail = tail->next;
}
tail->next = NULL;