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:  };  

315. Count of Smaller Numbers After Self

The problem can be restated in this way, find the inverse numbers (i.e. nums[i] > nums[j] but i < j) for each number in the array. There are two ways to solve this problem. First solution is to build a binary search tree from the end to beginning such that a new coming node must have index less than existing node. So the invert number for the new node will be nodes that have value less than it. To do so, we need to modify the tree node a little bit to include left node count and its own copy (for duplicate nodes). So for a new coming number, there are 3 cases:

Case 1: root value is equal to the new value, i.e. a duplicated node is found.
We just increase the root's copy and return the left count of root.

Case 2: root value is less than the new value.
We need to increase the left count of root and insert the new node to left and return the new node's left count.

Case 3: root value is larger than the new value.
We need to insert the new node to right and return root's left count plus root's own copy plus the new node's left count.

From the three cases above, we can see that we need to return the left count for insert operation.

1:  class Node {  
2:  public:  
3:    int val, copy, leftCount;  
4:    Node *left, *right;  
5:    Node(int x) { val = x; copy = 1; leftCount = 0; left = NULL; right = NULL; }  
6:  };  
7:  class Solution {  
8:  public:  
9:    vector<int> countSmaller(vector<int>& nums) {  
10:      int n = nums.size();  
11:      vector<int> res(n, 0);  
12:      if (nums.size() <= 1) return res;  
13:      Node *root = new Node(nums[nums.size()-1]);  
14:      for (int i = nums.size()-2; i >= 0; i--) {  
15:        res[i] = insert(root, nums[i]);  
16:      }  
17:      return res;  
18:    }  
19:    int insert(Node *root, int val) {  
20:      if (root->val == val) {  
21:        root->copy++;  
22:        return root->leftCount;  
23:      } else if (root->val > val) {  
24:        root->leftCount++;  
25:        if (root->left) {  
26:          return insert(root->left, val);  
27:        } else {  
28:          root->left = new Node(val);  
29:          return 0;  
30:        }  
31:      } else {  
32:        if (root->right) {  
33:          return root->leftCount+root->copy+insert(root->right, val);  
34:        } else {  
35:          root->right = new Node(val);  
36:          return root->leftCount+root->copy;  
37:        }  
38:      }  
39:    }  
40:  };  

When I revisited this problem, I made mistakes in:
line 16: I was returning 1 instead of 0.
line 27: I wasn't aware that there is no smaller number if the input array only contains one number.
line 29: I wasn't aware that I should have started from the end.

1:  class MyTreeNode {  
2:  public:  
3:    int val;  
4:    int copy;  
5:    int leftCounts;  
6:    MyTreeNode *left;  
7:    MyTreeNode *right;  
8:    MyTreeNode(int x): val(x), copy(1), leftCounts(0), left(NULL), right(NULL) {}  
9:  };  
10:  class Solution {  
11:  private:  
12:    int insert(MyTreeNode *root, int val) {  
13:      if (root->val == val) { root->copy++; return root->leftCounts; }  
14:      if (root->val > val) {   
15:        root->leftCounts++;  
16:        if (root->left == NULL) { root->left = new MyTreeNode(val); return 0;}  
17:        else return insert(root->left, val);  
18:      } else {  
19:        if (root->right == NULL) { root->right = new MyTreeNode(val); return root->leftCounts + root->copy; }  
20:        else return root->leftCounts + root->copy + insert(root->right, val);  
21:      }  
22:    }  
23:  public:  
24:    vector<int> countSmaller(vector<int>& nums) {  
25:      int n = nums.size();  
26:      vector<int> res = vector<int>(n, 0);  
27:      if (n < 2) return res;  
28:      MyTreeNode *root = new MyTreeNode(nums[n-1]);  
29:      for (int i = n-2; i >= 0; i--) {  
30:        res[i] = insert(root, nums[i]);  
31:      }  
32:      return res;  
33:    }  
34:  };  

Another way is to do merge sort.

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:  };