88. Merge Sorted Array

The tricky part is we need to start from the end of arrays such that the largest will be allocated in the end.

1:  class Solution {  
2:  public:  
3:    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {  
4:      int i = m-1;  
5:      int j = n-1;  
6:      int k = m+n-1;  
7:      while (i >= 0 && j >= 0) {  
8:        if (nums1[i] > nums2[j]) {  
9:          nums1[k--] = nums1[i--];  
10:        } else {  
11:          nums1[k--] = nums2[j--];  
12:        }  
13:      }  
14:      while (j >= 0) nums1[k--] = nums2[j--];  
15:    }  
16:  };  

167. Two Sum II - Input array is sorted

Not much to say. An easy two pointers solution with O(N) running time. Of course, it can be solved by binary search but it may cost NlogN running time.

1:  class Solution {  
2:  public:  
3:    vector<int> twoSum(vector<int>& numbers, int target) {  
4:      int l = 0, r = numbers.size()-1;  
5:      while (l < r) {  
6:        int sum = numbers[l] + numbers[r];  
7:        if (sum == target) break;  
8:        else if (sum < target) l++;  
9:        else r--;  
10:      }  
11:      return vector<int>{l+1, r+1};  
12:    }  
13:  };  

186. Reverse Words in a String II

This is similar to problem "151. Reverse Words in a String". The idea is the same, i.e. reverse all the string first and reverse each word in the string.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      reverse(s.begin(), s.end());  
5:      int i = 0, j = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && s[i] != ' ') i++;  
8:        reverse(s.begin()+j, s.begin()+i);  
9:        j = ++i;  
10:      }  
11:    }  
12:  };  

102. Binary Tree Level Order Traversal

Not much to say. BFS can be applied here. Here is the code.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> levelOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (root == NULL) return res;  
15:      queue<TreeNode*> q;  
16:      q.push(root);  
17:      while (!q.empty()) {  
18:        int sz = q.size();  
19:        vector<int> level;  
20:        for (int i = 0; i < sz; i++) {  
21:          TreeNode *node = q.front();  
22:          q.pop();  
23:          level.push_back(node->val);  
24:          if (node->left) q.push(node->left);  
25:          if (node->right) q.push(node->right);  
26:        }  
27:        res.push_back(level);  
28:      }  
29:      return res;  
30:    }  
31:  };  

204. Count Primes

This is a dynamic problem. The minimal prime is 2. So we can start from 2 and we know that any multiple of 2 is a prime. So we mark off all multiple of 2. Then we check 3. Similarly, and multiple of 3 is not a prime so we mark off them. Now we come to 4. Since 4 is a multiple of 2 and has been marked off, we just ignore and continue to 5. Note, we don't have to start from 5*2 because 5*2, 5*3, 5*4 have all been marked off before. So we can start from 5*5. Therefore, the algorithm is as following:

1:  class Solution {  
2:  public:  
3:    int countPrimes(int n) {  
4:      vector<bool> isPrime(n, true);  
5:      for (int i = 2; i*i < n; i++) {  
6:        if (!isPrime[i]) continue;  
7:        for (int j = i*i; j < n; j += i) {  
8:          isPrime[j] = false;  
9:        }  
10:      }  
11:      int count = 0;  
12:      for (int i = 2; i < n; i++) {  
13:        if (isPrime[i]) count++;  
14:      }  
15:      return count;  
16:    }  
17:  };  

8. String to Integer (atoi)

This is "easy" for programming if you are clear about all possible cases. Need to get the requirment clarified from the interviewer. Anyway, here are the cases that OJ thinks of (I've added comments for the cases in the code).

1:  class Solution {  
2:  public:  
3:    int myAtoi(string str) {  
4:      int i = 0, n = str.size();  
5:      long long res = 0;  
6:      int sign = 1;  
7:      // ignore leading spaces  
8:      while (str[i] == ' ') i++;  
9:      // process leading sign  
10:      if (str[i] == '-') { sign = -1; i++; }  
11:      else if (str[i] == '+') { sign = 1; i++; }  
12:      while (i < n && isNum(str[i])) {  
13:        res = res*10 + str[i]-'0';  
14:        // process overflow;  
15:        if (sign == 1 && res > INT_MAX) return INT_MAX;  
16:        if (sign == -1 && -res < INT_MIN) return INT_MIN;  
17:        i++;  
18:      }  
19:      return res * sign;  
20:    }  
21:    bool isNum(char c) {  
22:      return c >= '0' && c <= '9';  
23:    }  
24:  };  

160. Intersection of Two Linked Lists

I count the number of the two lists first. And then I compute the offset and move the head pointer of the longer list to the offset. And from there compare the two lists and check the intersection.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
12:      int a = countList(headA);  
13:      int b = countList(headB);  
14:      int diff = 0;  
15:      if (a > b) {  
16:        diff = a - b;  
17:        while (diff) { headA = headA->next; diff--; }  
18:      } else {  
19:        diff = b - a;  
20:        while (diff) { headB = headB->next; diff--; }  
21:      }  
22:      while (headA != headB) {  
23:        headA = headA->next;  
24:        headB = headB->next;  
25:      }  
26:      return headA;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while (head) {  
31:        head = head->next;  
32:        count++;  
33:      }  
34:      return count;  
35:    }  
36:  };  

234. Palindrome Linked List

I count the total nodes first and then find the middle node. To cover both cases of odd/even number, the middle node should be the ceiling of n / 2. And then reverse the sublist starting from the middle node. After that, compare the first half list with the reversed second half list to see if any discrepancy.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    bool isPalindrome(ListNode* head) {  
12:      int count = countList(head);  
13:      if (count < 2) return true;  
14:      int mid = (count+1)/2;  
15:      ListNode *l2 = head;  
16:      while (mid) {  
17:        l2 = l2->next;  
18:        mid--;  
19:      }  
20:      l2 = reverseList(l2);  
21:      while (l2) {  
22:        if (head->val != l2->val) return false;  
23:        head = head->next;  
24:        l2 = l2->next;  
25:      }  
26:      return true;  
27:    }  
28:    int countList(ListNode *head) {  
29:      int count = 0;  
30:      while(head) {  
31:        count++;  
32:        head = head->next;  
33:      }  
34:      return count;  
35:    }  
36:    ListNode *reverseList(ListNode *head) {  
37:      ListNode *pre = NULL;  
38:      while (head) {  
39:        ListNode *next = head->next;  
40:        head->next = pre;  
41:        pre = head;  
42:        head = next;  
43:      }  
44:      return pre;  
45:    }  
46:  };  

21. Merge Two Sorted Lists

Well, this is a real easy one.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      ListNode *cur = dummy;  
14:      while (l1 && l2) {  
15:        if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; }  
16:        else { cur->next = l2; l2 = l2->next; }  
17:        cur = cur->next;  
18:      }  
19:      if (l1) cur->next = l1;  
20:      if (l2) cur->next = l2;  
21:      cur = dummy->next;  
22:      delete dummy;  
23:      return cur;  
24:    }  
25:  };  

141. Linked List Cycle

To find a cycle in the linked list, we can have two pointers, one of which moves one steps once and the other moves two steps once. If the fast pointer reaches NULL, it means there is no cycle, otherwise, the fast pointer will capture the slow pointer again.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    bool hasCycle(ListNode *head) {  
12:      if (head == NULL || head->next == NULL) return false;  
13:      ListNode *slow = head;  
14:      ListNode *fast = head->next;  
15:      while (fast && fast->next) {  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:        if (slow == fast) return true;  
19:      }  
20:      return false;  
21:    }  
22:  };  

121. Best Time to Buy and Sell Stock

This is actually a maximum subarray sum problem which can be solved by Kadane’s Algorithm.
Here is a very good video explaining this algorithm:
https://www.youtube.com/watch?v=86CQq3pKSUw

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int maxGlobal = 0;  
5:      int maxCurrent = 0;  
6:      for (int i = 1; i < prices.size(); i++) {  
7:        maxCurrent = max(prices[i]-prices[i-1], maxCurrent + prices[i]-prices[i-1]);  
8:        if (maxCurrent > maxGlobal) maxGlobal = maxCurrent;  
9:      }  
10:      return maxGlobal;  
11:    }  
12:  };  

238. Product of Array Except Self

The idea is to compute the cumulative left products first and store them in the array. And then from the right side compute the cumulative right product and thus compute the final product of the array except self. The total running time is O(2n).

1:  class Solution {  
2:  public:  
3:    vector<int> productExceptSelf(vector<int>& nums) {  
4:      vector<int> res(nums.size(), 1);  
5:      res[0] = nums[0];  
6:      for (int i = 1; i < nums.size()-1; i++) {  
7:        res[i] = res[i-1]*nums[i];  
8:      }  
9:      int right = 1;  
10:      for (int i = nums.size()-1; i >= 1; i--) {  
11:        res[i] = res[i-1] * right;  
12:        right *= nums[i];  
13:      }  
14:      res[0] = right;  
15:      return res;  
16:    }  
17:  };  

49. Group Anagrams

The anagrams share the same pattern if they are sorted. So what I did is to create a hash table where key is the pattern and the value is the anagrams that have the same pattern. So the algorithm becomes obvious that compute the pattern for each anagram and save it into the hash table.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> groupAnagrams(vector<string>& strs) {  
4:      unordered_map<string, vector<string>> mp;  
5:      for (int i = 0; i < strs.size(); i++) {  
6:        string key = strs[i];  
7:        sort(key.begin(), key.end());  
8:        mp[key].push_back(strs[i]);  
9:      }  
10:      vector<vector<string>> res;  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        res.push_back(it->second);  
13:      }  
14:      return res;  
15:    }  
16:  };  

Note I use library sort here which I believe takes O(nlogn) time. Since the anagrams here consist of only 26 lower case letters, we can use bucket sort to compute the pattern which reduce the sorting time to O(n).

48. Rotate Image

The 90 degree rotation can be down by following two steps:
1. swap numbers along the diagonal.
2. swap numbers along the middle column.

1:  class Solution {  
2:  public:  
3:    void rotate(vector<vector<int>>& matrix) {  
4:      int n = matrix.size();  
5:      if (n == 0) return;  
6:      for (int i = 0; i < n; i++) {  
7:        for (int j = i+1; j < n; j++) {  
8:          swap(matrix[i][j], matrix[j][i]);  
9:        }  
10:      }  
11:      for (int i = 0; i < n; i++) {  
12:        int l = 0, r = n-1;  
13:        while (l < r) {  
14:          swap(matrix[i][l], matrix[i][r]);  
15:          l++, r--;  
16:        }  
17:      }  
18:    }  
19:  };  

3. Longest Substring Without Repeating Characters

This is very similar idea to problem "340. Longest Substring with At Most K Distinct Characters".
1. we keep moving one pointer and count each character until one character has been counted before, i.e. the count for the character is one already.
2. Then we move another pointer and decrease the counter for each character until the character pointed by the first pointer has count 0.
3. And then leave the second pointer there and move the first pointer again. Repeat step 1-2 until the first pointer reaches the end.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstring(string s) {  
4:      vector<int> chars(256, 0);  
5:      int i = 0, j = 0, maxLen = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && chars[s[i]] == 0) {++chars[s[i++]];};  
8:        maxLen = max(maxLen, i - j);  
9:        while (i < s.size() && chars[s[i]] == 1) --chars[s[j++]];  
10:      }  
11:      return maxLen;  
12:    }  
13:  };  

138. Copy List with Random Pointer

I used hash map to solve the problem with two rounds.
In first round, copy the list without regard with random pointer but make a map between the old node and new node.
In the second round, fix the random pointer by the hash mapping.

1:  /**  
2:   * Definition for singly-linked list with a random pointer.  
3:   * struct RandomListNode {  
4:   *   int label;  
5:   *   RandomListNode *next, *random;  
6:   *   RandomListNode(int x) : label(x), next(NULL), random(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    RandomListNode *copyRandomList(RandomListNode *head) {  
12:      unordered_map<RandomListNode*, RandomListNode*> mp;  
13:      RandomListNode *dummy = new RandomListNode(-1);  
14:      RandomListNode *cur = head, *res = dummy;  
15:      while (cur) {  
16:        RandomListNode *node = new RandomListNode(cur->label);  
17:        mp[cur] = node;  
18:        res->next = node;  
19:        res = res->next;  
20:        cur = cur->next;  
21:      }  
22:      cur = head;  
23:      res = dummy->next;  
24:      while (cur) {  
25:        if (cur->random != NULL) {  
26:          res->random = mp[cur->random];  
27:        }  
28:        res = res->next;  
29:        cur = cur->next;  
30:      }  
31:      res = dummy->next;  
32:      delete dummy;  
33:      return res;  
34:    }  
35:  };  

235. Lowest Common Ancestor of a Binary Search Tree

Well, a quite easy problem.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
13:      if (root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q);  
14:      if (root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q);  
15:      return root;  
16:    }  
17:  };  

126. Word Ladder II

I built my solution on top of problem 127 "Word Ladder". I use a hash map to store the prior string set of current string. The key is current string and the value is the prior string set. The reason I use unordered_set for prior strings is to avoid duplicates. The basic idea is to find the shortest transformation sequence first and then build the sequences by the hash map.

1:  class Solution {  
2:  private:  
3:    unordered_map<string, unordered_set<string>> mp;  
4:    queue<string> q;  
5:    vector<vector<string>> res;  
6:    vector<string> path;  
7:    int dist;  
8:  public:  
9:    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {  
10:      dist = helper(start, end, dict);  
11:      if (dist) output(start, end);  
12:      return res;   
13:    }  
14:    int helper(string &start, string &end, unordered_set<string> &dict) {  
15:      dict.insert(start);  
16:      q.push(start);  
17:      path.push_back(end);  
18:      dist = 1;  
19:      while (!q.empty()) {  
20:        int n = q.size();  
21:        for (int i = 0; i < n; i++) {  
22:          dict.erase(q.front());  
23:          q.push(q.front());  
24:          q.pop();  
25:        }  
26:        for (int i = 0; i < n; i++) {  
27:          string word = q.front();  
28:          q.pop();  
29:          if (word == end) return dist;  
30:          addNeighbors(word, dict);  
31:        }  
32:        dist++;  
33:      }  
34:      return 0;  
35:    }  
36:    void addNeighbors(string word, unordered_set<string> &dict) {  
37:      string tmp = word;  
38:      for (int i = 0; i < word.size(); i++) {  
39:        char c = tmp[i];  
40:        for (int j = 0; j < 26; j++) {  
41:          tmp[i] = 'a' + j;  
42:          if (dict.count(tmp)) {  
43:            q.push(tmp);  
44:            mp[tmp].insert(word);  
45:          }  
46:        }  
47:        tmp[i] = c;  
48:      }  
49:    }  
50:    void output(string &start, string end) {  
51:      if (path.size() == dist) {  
52:        if (start == end) {  
53:          reverse(path.begin(), path.end());  
54:          res.push_back(path);  
55:          reverse(path.begin(), path.end());  
56:        }  
57:        return;  
58:      }  
59:      int n = mp[end].size();  
60:      for (auto it = mp[end].begin(); it != mp[end].end(); it++) {  
61:        string s = *it;  
62:        path.push_back(s);  
63:        output(start, s);  
64:        path.pop_back();  
65:      }  
66:    }  
67:  };  

206. Reverse Linked List

I had following code in first place.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      ListNode *prev = head, *cur = head->next;  
14:      prev->next = NULL;  
15:      while (cur) {  
16:        ListNode *tmp = cur->next;  
17:        cur->next = prev;  
18:        prev = cur;  
19:        cur = tmp;  
20:      }  
21:      return prev;  
22:    }  
23:  };  

And here is the more concise one from top rated solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseList(ListNode* head) {  
12:      ListNode *prev = NULL;  
13:      while (head) {  
14:        ListNode *tmp = head->next;  
15:        head->next = prev;  
16:        prev = head;  
17:        head = tmp;  
18:      }  
19:      return prev;  
20:    }  
21:  };  

1. Two Sum

I was trying to sort the number and find the two sum index by binary search. However, this is completely wrong. Since we need to return the index, we shouldn't sort the array because by doing this the index is changed. So I used hash map to solve the problem.

1:  class Solution {  
2:  public:  
3:    vector<int> twoSum(vector<int>& nums, int target) {  
4:      unordered_map<int, int> hash;  
5:      vector<int> res;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        int t = target - nums[i];  
8:        if (hash.find(t) != hash.end()) {  
9:          res.push_back(i);  
10:          res.push_back(hash[t]);  
11:          break;  
12:        }  
13:        hash[nums[i]] = i;  
14:      }  
15:      return res;  
16:    }  
17:  };