278. First Bad Version

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 firstBadVersion(int n) {
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]]++;
int head = start;
while (head 0) {
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:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return NULL;
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;