252. (Locked) Meeting rooms

Difficulty: Easy

Frequency: N/A

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i - 1].end) return false;
        }
        return true;
    }
private:
    static bool compare(Interval& interval1, Interval& interval2) {
        return interval1.start < interval2.start;
    }
};

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:

147. Insertion Sort List

Difficulty: Medium

Frequency: N/A

Sort a linked list using insertion sort.

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* insertionSortList(ListNode* head) {
        ListNode *dummy = new ListNode(INT_MIN);
        while (head) {
            ListNode *cur = dummy, *curNext = cur->next, *headNext = head->next;
            while (cur) {
                if (!curNext) {
                    cur->next = head;
                    head->next = curNext;
                    break;
                } else if (head->val < curNext->val) {
                    cur->next = head;
                    head->next = curNext;
                    break;
                } else {
                    cur = cur->next;
                    curNext = curNext->next;
                }
            }
            head = headNext;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

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

Things to learn:

001. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


Questions:

1. whether there is only one solution if the question does not declare it.


Test Cases:

1. [2, 7, 11, 15] 9
2. [11, 2, 15, 7] 9
3. [2, 7] 9
4. [2, 4, 4, 3] 8

Solution 1:
Data structure:
array, unordered_map
Method:
hash table
Steps:
1. for each number, lookup target-number in the hash table
2. if it is in the hash table, return result, else insert it in the hash table.
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       unordered_map<int, int> my_map;
       vector<int> res;
       for (int i = 0; i < nums.size(); i++) {
           int numToFind = target - nums[i];
           if (my_map.find(numToFind) != my_map.end()) {
               res.push_back(my_map[numToFind]);
               res.push_back(i);
               return res;
           }
           my_map[nums[i]] = i;
       }
       return res;
    }
};

Solution 2:

Data structure:
array
Method:
two pointers
Steps:
1. copy out the array
2. sort the array
3. iterate from beginning and end, and find the two integers
4. iterate through the original array, and find the two indexes
Complexity:
runtime: O(NlogN)
space: O(N)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> cp(nums);
        sort(cp.begin(), cp.end());
        vector<int> results;
        int n = nums.size();
        if (!n) return results;
        int left = 0, right = n - 1;
        while (left < right) {
            if (cp[left] + cp[right] == target) break;
            else if (cp[left] + cp[right] < target) left++;
            else right--;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == cp[left]) results.push_back(i);
            else if (nums[i] == cp[right]) results.push_back(i);
            if (results.size() == 2) break;
        }
        return results;
    }
};

Solution 3:

Data structure:
array
Method:
brute force
Steps:
1. two nested loops to find the two nums.
Complexity:
runtime: O(N^2)
space: O(1)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> results;
        int n = nums.size();
        if (!n) return results;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    results.push_back(i);
                    results.push_back(j);
                    return results;
                }
            }
        }
        return results;
    }
};

Things to learn:
1. copy an array: vector cp(nums).
2. the element using iterator: iter = num.end() – 1
3. unordered_map.find() complexity: average constant, worst linear.