162. Find Peak Element

Difficulty: Medium

Frequency: N/A

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.empty()) return -1;
        if (nums.size() == 1) return 0;
        int n = nums.size();
        int lo = 0, hi = n - 1, med;
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] < nums[med + 1]) lo = med + 1;
            else hi = med;
        }
        return lo;
    }
};

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[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]]++;
int head = start;
while (head 0) {
dict[tmp]–;
head += word_length;
} 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;
        ListNode *newHead = head, *tail = head;
        while (tail->next) {
            len++;
            tail = tail->next;
        }
        tail->next = head;
        if (k = k % len) {
            for (int i = 0; i < len - k; i++) tail = tail->next;
        }
        newHead = tail->next;
        tail->next = NULL;
        return newHead;
    }
};

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

Things to learn:

209. Minimum Size Subarray Sum

Difficulty: Medium

Frequency: N/A

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int start = 0, sum = 0, minLen = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            while (sum >= s) {
                minLen = min(minLen, i - start + 1);
                sum -= nums[start++];
            }
        }
        return (minLen == INT_MAX ? 0 : minLen);
    }
};

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

Things to learn:

075. Sort Colors

Difficulty: Medium

Frequency: N/A

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int sec = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] == 0) {
                        nums[j] = nums[i];
                        nums[i] = 0;
                        sec = i + 1;
                    }
                }
            }
        }
        for (int i = sec; i < nums.size(); i++) {
            if (nums[i] == 2) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] == 1) {
                        nums[j] = nums[i];
                        nums[i] = 1;
                    }
                }
            }
        }
    }
};

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

Things to learn:

259. (Locked)3Sum Smaller

Difficulty: Medium

Frequency: N/A

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n^2) runtime?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        if (nums.size() < 3) return 0;
        int cnt = 0;
        sort(nums.begin(), nums.end());
        for (int f = 0; f < nums.size() - 2; f++) {
            int s = f + 1, t = nums.size() - 1;
            while (s < t) {
                if (nums[f] + nums[s] + nums[t] < target) {
                   cnt += (t - s);
                   s++;
                } else t--;
            }
        }
        return cnt;
    }
};

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

Things to learn:

016. 3Sum Closest

Difficulty: Medium

Frequency: N/A

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3) return -1;
        sort(nums.begin(), nums.end());
        int closest = nums[0] + nums[1] + nums[2];
        for (int f = 0; f < nums.size() - 2; f++) {
            int s = f + 1, t = nums.size() - 1;
            while (s < t) {
                int tmp = nums[f] + nums[s] + nums[t];
                if (abs(target - closest) > (abs(target - tmp))) closest = tmp;
                if (tmp > target) t--;
                else if (tmp < target) s++;
                else return closest;
            }
        }
        return closest;
    }
};

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

Things to learn:

011. Container With Most Water

Difficulty: Medium

Frequency: N/A

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_water = 0, left = 0, right = height.size() - 1;
        while (left < right) {
            int tmp = min(height[left], height[right]) * (right - left);
            max_water = max(max_water, tmp);
            if (height[left] < height[right]) left++;
            else if (height[left] > height[right]) right--;
            else {
                left++;
                right--;
            }
        }
        return max_water;
    }
};

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

Things to learn:

080. Remove Duplicates from Sorted Array II

Difficulty: Medium

Frequency: N/A

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int n : nums) {
            if (i < 2 || n > nums[i - 2]) nums[i++] = n;
        }
        return i;
    }
};

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

Things to learn: