327. Count of Range Sum

The naive solution takes O(n*n) time.

1:  class Solution {  
2:  public:  
3:    int countRangeSum(vector<int>& nums, int lower, int upper) {  
4:      int res = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        long long sum = 0;  
7:        for (int j = i; j < nums.size(); j++) {  
8:          sum += nums[j];  
9:          if (sum >= lower && sum <= upper) res++;  
10:        }  
11:      }  
12:      return res;  
13:    }  
14:  };  

The other way is to try merge sort. However, instead of sorting numbers here, we sort the sums. So we need to preprocess the numbers first to get a sum array. For the sum array, the range sum between nums[i] and nums[j] is straightforward, i.e. sums[j] - sums[i]. So for the merge sort, we only need to find pairs (i, j) across two sorted partitions such that sums[j] - sum[i] is smaller than or equal to the given interval. Note, we need to be careful about overflow because when you compute the sum, INT_MAX - (-1) gets overflow. So the sums array should use long integer.

1:  class Solution {  
2:  public:  
3:    int countRangeSum(vector<int>& nums, int lower, int upper) {  
4:      vector<long long> sums(nums.size()+1, 0);  
5:      for (int i = 1; i <= nums.size(); i++) {  
6:        sums[i] = sums[i-1]+nums[i-1];  
7:      }  
8:      return mergeSort(sums, 1, nums.size(), lower, upper);  
9:    }  
10:    int mergeSort(vector<long long> &sums, int l, int r, int lower, int upper) {  
11:      if (l > r) return 0;  
12:      if (l == r) return sums[l] >= lower && sums[r] <= upper ? 1 : 0;  
13:      int mid = l + (r-l) / 2;  
14:      int res = mergeSort(sums, l, mid, lower, upper) + mergeSort(sums, mid+1, r, lower, upper);  
15:      int i = 0, j = 0, k = 0;  
16:      for (int i = l, j = k = mid+1; i <= mid; i++) {  
17:        while (j <= r && sums[j]-sums[i] < lower) j++;  
18:        while (k <= r && sums[k]-sums[i] <= upper) k++;  
19:        res += k-j;  
20:      }  
21:      vector<long long> tmp(r-l+1, 0);  
22:      i = l;  
23:      j = mid+1;  
24:      for (k = l; i <= mid && j <= r; k++) {  
25:        if (sums[i] < sums[j]) tmp[k-l] = sums[i++];  
26:        else tmp[k-l] = sums[j++];  
27:      }  
28:      while (i <= mid) tmp[k++-l] = sums[i++];  
29:      while (j <= r) tmp[k++-l] = sums[j++];  
30:      for (int k = l; k <= r; k++) {  
31:        sums[k] = tmp[k-l];  
32:      }  
33:      return res;  
34:    }  
35:  };  

23. Merge k Sorted Lists

A typical divide and conquer solution. We need to find the correct termination condition. I use "if (lo > hi) return NULL" as termination condition but got run time error. We should terminate at two conditions:
1. lo == hi, return lists[lo]
2. lo+1 == hi, merge lists[lo] and lists[hi] and return.

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* mergeKLists(vector<ListNode*>& lists) {  
12:      if (lists.size() == 0) return NULL;  
13:      if (lists.size() == 1) return lists[0];  
14:      return sortLists(lists, 0, (int)lists.size()-1);  
15:    }  
16:    ListNode *sortLists(vector<ListNode*> &lists, int lo, int hi) {  
17:      if (lo == hi) return lists[lo];  
18:      if (lo+1 == hi) return merge(lists[lo], lists[hi]);  
19:      int mid = lo + (hi - lo) / 2;  
20:      ListNode *l1 = sortLists(lists, lo, mid-1);  
21:      ListNode *l2 = sortLists(lists, mid, hi);  
22:      return merge(l1, l2);  
23:    }  
24:    ListNode *merge(ListNode *l1, ListNode *l2) {  
25:      ListNode *dummy = new ListNode(-1);  
26:      ListNode *cur = dummy;  
27:      while (l1 && l2) {  
28:        if (l1->val < l2->val) {  
29:          cur->next = l1;  
30:          l1 = l1->next;  
31:        } else {  
32:          cur->next = l2;  
33:          l2 = l2->next;  
34:        }  
35:        cur = cur->next;  
36:      }  
37:      if (l1) cur->next = l1;  
38:      if (l2) cur->next = l2;  
39:      cur = dummy->next;  
40:      delete dummy;  
41:      return cur;  
42:    }  
43:  };  

When I revisited this problem, the terminal condition can be simplified to:
1. s == e, return lists[s]; 2. s > e, return NULL.

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* mergeKLists(vector<ListNode*>& lists) {  
12:      return helper(lists, 0, lists.size()-1);  
13:    }  
14:    ListNode *helper(vector<ListNode*> &lists, int s, int e) {  
15:      if (s == e) return lists[s];  
16:      if (s > e) return NULL;  
17:      int mid = s + (e - s) / 2;  
18:      ListNode *l1 = helper(lists, s, mid);  
19:      ListNode *l2 = helper(lists, mid+1, e);  
20:      ListNode *dummy = new ListNode(-1);  
21:      ListNode *cur = dummy;  
22:      while (l1 && l2) {  
23:         if (l1->val < l2->val) {  
24:           cur->next = l1;  
25:           l1 = l1->next;  
26:         } else {  
27:           cur->next = l2;  
28:           l2 = l2->next;  
29:         }  
30:         cur = cur->next;  
31:      }  
32:      if (l1) cur->next = l1;  
33:      if (l2) cur->next = l2;  
34:      cur = dummy->next;  
35:      delete dummy;  
36:      return cur;  
37:    }  
38:  };  

4. Median of Two Sorted Arrays

This is a problem of kth number in two sorted arrays. Let’s look at two arrays, for m < n,
[nums1[0],nums1[1],…,nums1[m]]
[nums2[0],nums2[1],...,nums[n]]

Every time we take k numbers, i.e. we take k/2 numbers in nums1 and the rest in nums2. So we’ll have two cases:

Case 1: nums[k/2-1] <= nums[k-k/2-1] (The reason we have minus one here is when we are saying kth number in array, we count from 1 but the array index starts from 0).
we are sure that the first k/2 numbers in nums1 are smaller than the kth number and we can remove these numbers and shrink the search range. Since removing numbers in a vector take linear time, so we can use the index to present the search range in an array.

Case 2: nums[k/2-1] > nums[k-k/2-1]
We are sure that the first k-k/2-1 numbers in nums2 are smaller than the kth number and we can remove these numbers and shrink the search range.

The trick here is, the size of num1 could be smaller than k/2, so we should take i = min(k/2, e1-s1) numbers in num1 and the rest j = k -i in nums2. There are three terminations.
1. Size of num1 is larger than num2, we should swap them because the following logic assumes it.
2. Size of num1 is 0 which means we only need to find (k-1)th number in num2.
3. K is 1, which means we only need to find the smallest number in num1 and num2. We only need to return the smaller first number between num1 and num2.

When I revisited this problem, I made mistake in,
line 9-11: I was computing n1 for odd size and n2 for even side and return (n1+n2)/2.0. I should have noted that it isn’t right for odd size because in that case the result will be n1/2.0.
line 16: I missed this terminal case. Overall, I missed to add offset s1 and s2 to the i, j, and k.

1:  class Solution {  
2:  public:  
3:    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {  
4:      int n1 = nums1.size();  
5:      int n2 = nums2.size();  
6:      int k = (n1+n2) / 2;  
7:      double num1 = helper(nums1, 0, n1, nums2, 0, n2, k+1);  
8:      if ((n1+n2) % 2 == 0) {  
9:        return (num1 + helper(nums1, 0, n1, nums2, 0, n2, k))/2.0;  
10:      }  
11:      return num1;  
12:    }  
13:    int helper(vector<int> &nums1, int s1, int e1, vector<int> &nums2, int s2, int e2, int k) {  
14:      if (e1-s1 > e2-s2) return helper(nums2, s2, e2, nums1, s1, e1, k);  
15:      if (e1-s1 == 0) return nums2[s2+k-1];  
16:      if (k == 1) return min(nums1[s1], nums2[s2]);  
17:      int i = min(k/2, e1-s1);  
18:      int j = k - i;  
19:      if (nums1[s1+i-1] <= nums2[s2+j-1]) return helper(nums1, s1+i, e1, nums2, s2, e2, k-i);  
20:      else return helper(nums1, s1, e1, nums2, s2+j, e2, k-j);  
21:    }  
22:  };  

148. Sort List

A typical divide and conquer 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* sortList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      ListNode *slow = head, *fast = head, *prev = NULL;  
14:      while (fast && fast->next) {  
15:        prev = slow;  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:      }  
19:      prev->next = NULL;  
20:      ListNode *l1 = sortList(head);  
21:      ListNode *l2 = sortList(slow);  
22:      ListNode *dummy = new ListNode(-1);  
23:      ListNode *cur = dummy;  
24:      while (l1 && l2) {  
25:        if (l1->val < l2->val) {  
26:          cur->next = l1;  
27:          l1 = l1->next;  
28:        } else {  
29:          cur->next = l2;  
30:          l2 = l2->next;  
31:        }  
32:        cur = cur->next;  
33:      }  
34:      if (l1) cur->next = l1;  
35:      if (l2) cur->next = l2;  
36:      cur = dummy->next;  
37:      delete dummy;  
38:      return cur;  
39:    }  
40:  };  

241. Different Ways to Add Parentheses

The key is to treat each operator as the last one to process, divide the problem into two problems, i.e. get the left and right results around the operator, and then iterate the left and right results to conquer the final solution. Also, don't forget if there is no operator, we need to atoi the string. This is a very important step to make the divide and conquer method work.

1:  class Solution {  
2:  public:  
3:    vector<int> diffWaysToCompute(string input) {  
4:      vector<int> res;  
5:      for (int i = 0; i < input[i]; i++) {  
6:        if (input[i] < '0' || input[i] > '9') {  
7:          vector<int> left = diffWaysToCompute(input.substr(0, i));  
8:          vector<int> right = diffWaysToCompute(input.substr(i+1));  
9:          for (int l = 0; l < left.size(); l++) {  
10:            for (int r = 0; r < right.size(); r++) {  
11:              if (input[i] == '+') res.push_back(left[l] + right[r]);  
12:              else if (input[i] == '-') res.push_back(left[l] - right[r]);  
13:              else if (input[i] == '*') res.push_back(left[l] * right[r]);  
14:            }  
15:          }  
16:        }  
17:      }  
18:      if (res.empty()) {  
19:        res.push_back(atoi(input.c_str()));  
20:      }  
21:      return res;  
22:    }  
23:  };  

53. Maximum Subarray

This is classic kadane's algorithm. Let dp[i] be the maximum sum of a continuos subarray. So the state transition is shown as following:

dp[i] = max(dp[i-1]+nums[i], nums[i])

At the end, we get the maximum sum in the dp[i].

1:  class Solution {  
2:  public:  
3:    int maxSubArray(vector<int>& nums) {  
4:      int n = nums.size();  
5:      if (n == 0) return 0;  
6:      vector<int> dp(n, INT_MIN);  
7:      int maxSum = nums[0];  
8:      dp[0] = nums[0];  
9:      for (int i = 1; i < nums.size(); i++) {  
10:        dp[i] = max(dp[i-1]+nums[i], nums[i]);  
11:        maxSum = max(dp[i], maxSum);  
12:      }  
13:      return maxSum;  
14:    }  
15:  };  

95. Unique Binary Search Trees II

At root i with nodes [s, e] (s <= i <= e), we can divide this problem into two subproblems: 1. build left subtrees with nodes [s, i-1]; 2. build right subtrees with nodes[i+1, e]. After achieving these subtrees, we conquer the subtrees to form the solution at root i.

1:  class Solution {  
2:  public:  
3:    vector<TreeNode*> generateTrees(int n) {  
4:      if (n == 0) return vector<TreeNode*>(0, 0);  
5:      return helper(1, n);  
6:    }  
7:    vector<TreeNode*> helper(int s, int e) {  
8:      vector<TreeNode*> res;  
9:      if (s > e) {  
10:        res.push_back(NULL);  
11:        return res;  
12:      }  
13:      for (int i = s; i <= e; i++) {  
14:        vector<TreeNode*> left = helper(s, i-1);  
15:        vector<TreeNode*> right = helper(i+1, e);  
16:        for (int j = 0; j < left.size(); j++) {  
17:          for (int k = 0; k < right.size(); k++) {  
18:            TreeNode *tn = new TreeNode(i);  
19:            tn->left = left[j];  
20:            tn->right = right[k];  
21:            res.push_back(tn);  
22:          }  
23:        }  
24:      }  
25:      return res;  
26:    }  
27:  };  

There is DP solution in the top rated solution. Need to investigate later.

312. Burst Balloons

This is a similar problem to matrix chain multiplication. This can be solved by divide-and-conquer with memorization. The basic idea behind is:

Let dp[i][j] to record the maximum sum for interval nums[i, j]. So for subinterval nums[start, end], if we need to pop out nums[k] in nums[start, end], the maximum sum for poping out nums[k] is dp[start][i-1] + nums[k]*nums[start-1]*nums[end+1]+dp[i+1][end]. Note nums[k] is the last element that need to pop out from nums[start, end], so the product should be nums[k]*nums[start-1]*nums[end+1]. dp[i][j] can be calculated recursively.

1:  class Solution {  
2:  public:  
3:    int maxCoins(vector<int>& nums) {  
4:      // let nums to have nums[-1] = nums[n] = 1  
5:      nums.insert(nums.begin(), 1);  
6:      nums.push_back(1);  
7:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), INT_MIN));  
8:      return helper(dp, nums, 0, nums.size()-1);  
9:    }  
10:    // note start "s" and end "e" constructs an exclusive interval (s, e)  
11:    int helper(vector<vector<int>> &dp, vector<int> &nums, int s, int e) {  
12:      if (dp[s][e] != INT_MIN) return dp[s][e];  
13:      if (e - s == 1) { dp[s][e] = 0; return 0; }  
14:      int res = 0;  
15:      for (int i = s + 1; i < e; i++) {  
16:        res = max(res, helper(dp, nums, s, i) + helper(dp, nums, i, e) + nums[i]*nums[s]*nums[e]);  
17:      }  
18:      dp[s][e] = res;  
19:      return res;  
20:    }  
21:  };