410. Split Array Largest Sum

I don't have clue in the first place, so I followed the top rated solution.
The idea is the minimized maximum sum among the subarrays must between the largest number in the array and the sum of the total array. So we should think of the binary search.
Once we think about the binary search, we need to find the validation condition. Given the mid number, the condition is invalid if there are more than m subarrays that have sum larger than mid number.

1:  class Solution {  
2:  public:  
3:    int splitArray(vector<int>& nums, int m) {  
4:      long long left = 0, right = 0;  
5:      for (n : nums) {  
6:        left = max(left, (long long)n);  
7:        right += n;  
8:      }  
9:      while (left < right) {  
10:        long long mid = (left + right) / 2;  
11:        if (isValid(nums, m, mid)) right = mid;  
12:        else left = mid + 1;  
13:      }  
14:      return left;  
15:    }  
16:    bool isValid(vector<int> &nums, int m, int maxSum) {  
17:      long long cur = 0;  
18:      int count = 0;  
19:      for (n : nums) {  
20:        cur += n;  
21:        if (cur > maxSum) {  
22:          cur = n, count++;  
23:          // you've got m subarrays that have sum larger than maxSum,  
24:          // so maxSum isn't a minimized sum among these subarrays.  
25:          if (count == m) return false;  
26:        }  
27:      }  
28:      return true;  
29:    }  
30:  };  

154. Find Minimum in Rotated Sorted Array II

The key for this problem is still that the minimum number must fall into the rotated part. However, there are duplicates in the array, so for case nums[mid] == nums[hi] or nums[mid] == nums[lo] we only move upper bound one step backward. Why upper bound? Because we are turning lower bound as the result.

1:  class Solution {  
2:  public:  
3:    int findMin(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo < hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] > nums[hi]) lo = mid + 1;  
8:        else if (nums[mid] < nums[lo]) hi = mid;  
9:        else hi--;  
10:      }  
11:      return nums[lo];  
12:    }  
13:  };  

162. Find Peak Element

I tried naive way first which runs O(n) time.

1:  class Solution {  
2:  public:  
3:    int findPeakElement(vector<int>& nums) {  
4:      int peak = nums.size()-1;  
5:      for (int i = 0; i < nums.size()-1; i++) {  
6:        if (nums[i] > nums[i+1]) {  
7:          peak = i;  
8:          break;  
9:        }  
10:      }  
11:      return peak;  
12:    }  
13:  };  

Obviously, this naive way isn’t the best. We can do it by binary search. The idea is we keep looking for the two numbers in the middle. And if left middle number is less than the right middle number, we point left pointer to the right middle number, otherwise, we point right pointer to the left middle number. In this way, left and right pointers are always pointing to the larger one which will eventually help us find the peak.

1:  class Solution {  
2:  public:  
3:    int findPeakElement(vector<int>& nums) {  
4:      int l = 0, r = nums.size()-1;  
5:      while (l < r) {  
6:        int mid1 = l + (r - l) / 2;  
7:        int mid2 = mid1 + 1;  
8:        if (nums[mid1] < nums[mid2]) {  
9:          l = mid2;  
10:        } else {  
11:          r = mid1;  
12:        }  
13:      }  
14:      return l;  
15:    }  
16:  };  

374. Guess Number Higher or Lower

A typical binary search.

1:  // Forward declaration of guess API.  
2:  // @param num, your guess  
3:  // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0  
4:  int guess(int num);  
5:  class Solution {  
6:  public:  
7:    int guessNumber(int n) {  
8:      int l = 1, r = n, mid = 0, res = 0;  
9:      while (l <= r) {  
10:        mid = l + (r-l) /2;  
11:        res = guess(mid);  
12:        if (res == 0) return mid;  
13:        else if (res == 1) l = mid + 1;  
14:        else r = mid - 1;  
15:      }  
16:      return mid;  
17:    }  
18:  };  

272. Closest Binary Search Tree Value II

The O(n) solution will be straight forward. We can output all the nodes into an array, find the position where target is supposed in and move two pointers as predecessor and successor to output the closest k numbers. This also can be done by two stacks.

1:  class Solution {  
2:  public:  
3:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
4:      vector<int> nodes;  
5:      vector<int> res;  
6:      inorder(root, nodes);  
7:      if (nodes.size() == 0) return res;  
8:      int l = 0, r = nodes.size()-1;  
9:      if (target < nodes[l]) {  
10:        while (k--) res.push_back(nodes[l++]);  
11:        return res;  
12:      }  
13:      if (target > nodes[r]) {  
14:        while (k--) res.push_back(nodes[r--]);  
15:        return res;  
16:      }  
17:      while (l <= r) {  
18:        int mid = l + (r - l) / 2;  
19:        if (nodes[mid] == target) {r = mid; break;}  
20:        else if (nodes[mid] > target) r = mid - 1;  
21:        else l = mid+1;  
22:      }  
23:      l = r;  
24:      r = l+1;  
25:      while (k--) {  
26:        if (l < 0) res.push_back(nodes[r++]);  
27:        else if (r == nodes.size()) res.push_back(nodes[l--]);  
28:        else if (abs(nodes[l]-target) < abs(nodes[r]-target)) {  
29:          res.push_back(nodes[l--]);  
30:        } else {  
31:          res.push_back(nodes[r++]);  
32:        }  
33:      }  
34:      return res;  
35:    }  
36:    void inorder(TreeNode *root, vector<int> &nodes) {  
37:      if (root == NULL) return;  
38:      inorder(root->left, nodes);  
39:      nodes.push_back(root->val);  
40:      inorder(root->right, nodes);  
41:    }  
42:  };  

There is another way to maintain the predecessor and successor stack by traversing the tree in inorder and reverse-inorder.

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<int> closestKValues(TreeNode* root, double target, int k) {  
13:      stack<int> predecessor;  
14:      stack<int> successor;  
15:      inorder(root, false, predecessor, target);  
16:      inorder(root, true, successor, target);  
17:      vector<int> res;  
18:      while (k--) {  
19:        if (predecessor.empty()) {  
20:          res.push_back(successor.top());  
21:          successor.pop();  
22:        } else if (successor.empty()) {  
23:          res.push_back(predecessor.top());  
24:          predecessor.pop();  
25:        } else if (abs(predecessor.top()-target) < abs(successor.top()-target)) {  
26:          res.push_back(predecessor.top());  
27:          predecessor.pop();  
28:        } else {  
29:          res.push_back(successor.top());  
30:          successor.pop();  
31:        }  
32:      }  
33:      return res;  
34:    }  
35:    void inorder(TreeNode *root, bool reverse, stack<int> &stk, double target) {  
36:      if (root == NULL) return;  
37:      inorder(reverse ? root->right : root->left, reverse, stk, target);  
38:      if ((reverse && root->val <= target) || ((!reverse) && root->val > target)) return;  
39:      stk.push(root->val);  
40:      inorder(reverse ? root->left : root->right, reverse, stk, target);  
41:    }  
42:  };  

And this problem actually can be converted to a design problem with two methods getPredecessor() and getSuccessor(). We can stop searching the BST when we find the closest predecessor and successor to target. And we can update the predecessor stack and successor stack in these two methods respectively. So the running time will be O(klogn);

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:  private:  
12:    stack<treenode> pred;  
13:    stack<treenode> succ;  
14:  public:  
15:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
16:      vector<int> res;  
17:      initPredecessor(root, target);  
18:      initSuccessor(root, target);  
19:      if (!succ.empty() &amp;&amp; !pred.empty() &amp;&amp; succ.top()-&gt;val == pred.top()-&gt;val) {  
20:        getNextPredecessor();  
21:      }  
22:      while (k--) {  
23:        if (succ.empty()) res.push_back(getNextPredecessor());  
24:        else if (pred.empty()) res.push_back(getNextSuccessor());  
25:        else if (abs(succ.top()->val - target) < abs(pred.top()->val - target)) {  
26:          res.push_back(getNextSuccessor());  
27:        } else {  
28:          res.push_back(getNextPredecessor());  
29:        }  
30:      }  
31:      return res;  
32:    }  
33:    void initPredecessor(TreeNode *root, double target) {  
34:      while (root) {  
35:        if (root->val == target) {  
36:          pred.push(root);  
37:          break;  
38:        } else if (root->val < target) {  
39:          pred.push(root);  
40:          root = root->right;  
41:        } else {  
42:          root = root->left;  
43:        }  
44:      }  
45:    }  
46:    void initSuccessor(TreeNode *root, double target) {  
47:      while (root) {  
48:        if (root->val == target) {  
49:          succ.push(root);  
50:          break;  
51:        } else if (root->val > target) {  
52:          succ.push(root);  
53:          root = root->left;  
54:        } else {  
55:          root = root->right;  
56:        }  
57:      }  
58:    }  
59:    int getNextPredecessor() {  
60:      TreeNode *root = pred.top();  
61:      pred.pop();  
62:      int res = root->val;  
63:      root = root->left;  
64:      while (root) {  
65:        pred.push(root);  
66:        root = root-&gt;right;  
67:      }  
68:      return res;  
69:    }  
70:    int getNextSuccessor() {  
71:      TreeNode *root = succ.top();  
72:      succ.pop();  
73:      int res = root->val;  
74:      root = root->right;  
75:      while (root) {  
76:        succ.push(root);  
77:        root = root->left;  
78:      }  
79:      return res;  
80:    }  
81:  };  

The second time I revisited this problem, I found that initPredecessor() and initSuccessor() can be combined into one function.

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:  private:  
12:    stack<TreeNode *> pred;  
13:    stack<TreeNode *> succ;  
14:  public:  
15:    vector<int> closestKValues(TreeNode* root, double target, int k) {  
16:      vector<int> res;  
17:      if (root == NULL) return res;  
18:      initStacks(root, target);  
19:      while (k) {  
20:        if (pred.empty()) res.push_back(getNextPredecessor());  
21:        else if (succ.empty()) res.push_back(getNextSuccessor());  
22:        else if (abs(pred.top()->val-target) < abs(succ.top()->val-target)) {  
23:          res.push_back(getNextPredecessor());  
24:        } else {  
25:          res.push_back(getNextSuccessor());  
26:        }  
27:        k--;  
28:      }  
29:      return res;  
30:    }  
31:    void initStacks(TreeNode *root, double target) {  
32:      while (root != NULL) {  
33:        if (root->val <= target) {  
34:          pred.push(root);  
35:          root = root->right;  
36:        } else {  
37:          succ.push(root);  
38:          root = root->left;  
39:        }  
40:      }  
41:    }  
42:    int getNextPredecessor() {  
43:      TreeNode *t = pred.top();  
44:      int ret = t->val;  
45:      pred.pop();  
46:      t = t->left;  
47:      while (t) {  
48:        pred.push(t);  
49:        t = t->right;  
50:      }  
51:      return ret;  
52:    }  
53:    int getNextSuccessor() {  
54:      TreeNode *t = succ.top();  
55:      int ret = t->val;  
56:      succ.pop();  
57:      t = t->right;  
58:      while (t) {  
59:        succ.push(t);  
60:        t = t->left;  
61:      }  
62:      return ret;  
63:    }  
64:  };  

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

352. Data Stream as Disjoint Intervals

Well, I have to say the implementation of this problem depends. If there are many addNum() calls and only a few getIntervals() calls, we may want O(1) for addNum() and allows longer processing time for getIntervals(). The first implementation follows this idea.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class SummaryRanges {  
11:  private:  
12:    vector<Interval> intervals;  
13:  public:  
14:    /** Initialize your data structure here. */  
15:    SummaryRanges() {  
16:    }  
17:    void addNum(int val) {  
18:      intervals.push_back(Interval(val, val));  
19:    }  
20:    vector<Interval> getIntervals() {  
21:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start;});  
22:      for (int i = 1; i < intervals.size(); i++) {  
23:        if (intervals[i-1].end >= intervals[i].start-1) {  
24:          intervals[i-1].end = max(intervals[i-1].end, intervals[i].end);  
25:          intervals.erase(intervals.begin()+i);  
26:          i--;  
27:        }  
28:      }  
29:      return intervals;  
30:    }  
31:  };  
32:  /**  
33:   * Your SummaryRanges object will be instantiated and called as such:  
34:   * SummaryRanges obj = new SummaryRanges();  
35:   * obj.addNum(val);  
36:   * vector<Interval> param_2 = obj.getIntervals();  
37:   */    

On the other hand, if there are many getIntervals() calls but a few addNum() calls, we want O(1) for getIntervals() adn allows longer processing time for addNum(). The second implementation follows this way.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class SummaryRanges {   
11:  private:   
12:    vector<Interval> intervals;  
13:  public:   
14:    void addNum(int val) {  
15:      vector<Interval>::iterator it = lower_bound(intervals.begin(), intervals.end(), Interval(val, val),   
16:                            [](Interval a, Interval b){ return a.start < b.start; });   
17:      intervals.insert(it, Interval(val, val));   
18:      for (int i = 1; i < intervals.size(); i++) {   
19:        if (intervals[i-1].end >= intervals[i].start-1) {   
20:          intervals[i-1].end = max(intervals[i-1].end, intervals[i].end);   
21:          intervals.erase(intervals.begin()+i);   
22:          i--;  
23:        }  
24:      }  
25:    }  
26:    vector<Interval> getIntervals() {  
27:      return intervals;  
28:    }   
29:  };  
30:  /**  
31:   * Your SummaryRanges object will be instantiated and called as such:  
32:   * SummaryRanges obj = new SummaryRanges();  
33:   * obj.addNum(val);  
34:   * vector<Interval> param_2 = obj.getIntervals();  
35:   */  

287. Find the Duplicate Number

My intuition is to brute force finding the duplicated number. The running time will be O(n*n). However, the problem require us to solve it by less O(n*n). To solve the problem, we need to know Pigeonhole Principle, i.e., if m items are put into n containers with m > n, then at least one container must contain more than one items. This problem is a special case with m = n+1. Applying Pigeonhole Principle to this problem, if there are larger than k numbers in the array, then the duplicate must be in [0, k] and the value of duplicate number will be in [0, k] because the number of container is only one more than the maximum number. If we calculate k by binary search, we can solve this problem by O(n*logn).

1:  class Solution {  
2:  public:  
3:    int findDuplicate(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        int cnt = 0;  
8:        for (int n : nums) {  
9:          if (n <= mid) cnt++;  
10:        }  
11:        if (cnt > mid) hi = mid-1;  
12:        else lo = mid + 1;  
13:      }  
14:      return lo;  
15:    }  
16:  };  

220. Contains Duplicate III

The naive way is to check all pairs in the list. But this way gets TLE.

1:  class Solution {  
2:  public:  
3:    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {  
4:      for (int i = 0; i < nums.size(); i++) {  
5:        for (int j = i+1; j < nums.size(); j++)  
6:          if (abs((long long)nums[i]-nums[j]) <= t && abs(i-j) <= k) return true;  
7:      }  
8:      return false;  
9:    }  
10:  };  

The idea behind the top voted way is to scan from left to right and to keep a sorted window nums[j...i] that has size of k. This window ensures that all the numbers offsets is at most k. Since the numbers in the window are sorted, we only need to find the first number that is larger or equal than nums[i]-t. The reason is if a >= nums[i]-t, then we have a-nums[i] >= -t or nums[i]-a <= t. And if we can make sure that a-nums[i] <= t, then we have |a-nums[i]| <=t. We can use binary search to achieve this number.

1:  class Solution {  
2:  public:  
3:    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {  
4:      map<int, int> m;  
5:      int j = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        if (i - j > k) m.erase(nums[j++]);  
8:        auto it = m.lower_bound(nums[i]-t);  
9:        if (it != m.end() && abs(it->first - nums[i]) <= t) return true;  
10:        m[nums[i]] = i;  
11:      }  
12:      return false;  
13:    }  
14:  };  

69. Sqrt(x)

Typical binary search problem. The key is to find the right termination. Since sqrt(x) should return the bottom integer of the square root, we should use hi boundary because the hi boundary will be reduced 1 if mid square is larger than x.

1:  class Solution {  
2:  public:  
3:    int mySqrt(int x) {  
4:      if (x == 0 || x == 1) return x;  
5:      int lo = 0, hi = x/2;  
6:      while (lo <= hi) {  
7:        long long mid = lo + (hi - lo) / 2;  
8:        long long sqrt = mid * mid;  
9:        if (sqrt == x) return mid;  
10:        else if (sqrt > x) hi = mid-1;  
11:        else lo = mid+1;  
12:      }  
13:      return hi;  
14:    }  
15:  };  

When I revisited this problem, I had a bit more concise way. The idea behind is similar, but I observed that once r - l == 1 we've reached last two possible roots. l is moved to mid when mid*mid is less or equal to x, r is moved to mid when mid*mid is larger than x. So when r-l==1, l is the root that we'd like to find.

1:  class Solution {  
2:  public:  
3:    int mySqrt(int x) {  
4:      if (x == 0) return 0;  
5:      int l = 1, r = x;  
6:      while (l + 1< r) {  
7:        long long mid = l + (r-l)/2;  
8:        if (mid*mid > x) {  
9:          r = mid;  
10:        } else {  
11:          l = mid;  
12:        }  
13:      }  
14:      return l;  
15:    }  
16:  };  

222. Count Complete Tree Nodes

My intuition is level order traversal. The key is to find the leaf number in last level. However, it can be done by DFS. The idea is to find the complete tree in subtrees. The complete tree has an important property that the depth of left-most leaf is equal to the depth of right-most leaf. If the tree is complete simple return the total number. If not, search the complete tree in left and right child.

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:    int countNodes(TreeNode* root) {  
13:      if (root == NULL) return 0;  
14:      int lc = 0, rc = 0;  
15:      TreeNode *left = root, *right = root;  
16:      while (left) { lc++; left = left->left; }  
17:      while (right) { rc++; right = right->right; }  
18:      if (lc == rc) return (1 << lc)-1;  
19:      return 1 + countNodes(root->left) + countNodes(root->right);  
20:    }  
21:  };  

153. Find Minimum in Rotated Sorted Array

Modified binary search. Instead of checking nums[mid] == target, we check if nums[lo] < nums[hi]. If so, the minimum is nums[lo]. Otherwise, we just need to keep looking for the rotated pivot. There are two cases:

Case 1: nums[mid] < nums[lo]
[7,6,1,2,3,4,5], the pivot must be on the left of mid. Since pivot is on the left, the mid itself could be the minimum too, so the high boundary will be mid.

Case 2: nums[mid] >= nums[lo]
[4,5,6,7,0,1,2], the pivot must be on the right of mid. So the low boundary will be mid+1.

1:  class Solution {  
2:  public:  
3:    int findMin(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo < hi) {  
6:        if (nums[lo] < nums[hi]) {  
7:          return nums[lo];  
8:        }  
9:        int mid = lo + (hi - lo) / 2;  
10:        // [4,5,6,7,0,1,2]  
11:        if (nums[mid] >= nums[lo]) {  
12:          lo = mid + 1;  
13:        } else {  
14:          // [7,6,1,2,3,4,5]  
15:          hi = mid;  
16:        }  
17:      }  
18:      return nums[lo];  
19:    }  
20:  };  

50. Pow(x, n)

In first place, I'm thinking of calling the function twice with x and n/2 each. It is working but it gets TLE because of too many of recursions.

1:  class Solution {  
2:  public:  
3:    double myPow(double x, int n) {  
4:      if (n == 0) return 1.0;  
5:      x = n < 0 ? 1/x : x;  
6:      return helper(x, abs(n));  
7:    }  
8:    double helper(double x, int n) {  
9:      if (n == 1) return x;  
10:      if (n & 1) return x * helper(x, (n-1)/2) * helper(x, (n-1)/2);  
11:      else return helper(x, n/2) * helper(x, n/2);  
12:    }  
13:  };  

Another way is to call the function once as following. Need to deal with two cases where n is even or n is odd. Particularly, be careful about the case where n < 0.

1:  class Solution {  
2:  public:  
3:    double myPow(double x, int n) {  
4:      if (n == 0) return 1;  
5:      double res = myPow(x, n/2);  
6:      if (n % 2 == 0) {  
7:        return res*res;  
8:      } else {  
9:        return n < 0 ? 1/x*res*res : x*res*res;  
10:      }  
11:    }  
12:  };  

34. Search for a Range

Use binary search twice for left and right boundary respectively. Instead of checking nums[mid] == target, for left boundary, we only need to move the hi to mid. Note, we shouldn't move hi to mid-1 so that nums[hi] could be equal to target and hi will be the left boundary eventually. Then we can do the same thing to the right boundary but this time we move lo to mid. However, the mid needs to be computed as lo+(hi-lo)/2+1 such that the mid is biased to right. Otherwise, you'll get LTE if input is [2,2] as lo will stay at 0.

1:  class Solution {  
2:  public:  
3:    vector<int> searchRange(vector<int>& nums, int target) {  
4:      vector<int> res(2, -1);  
5:      int lo = 0, hi = nums.size()-1;  
6:      while (lo < hi) {  
7:        int mid = lo + (hi - lo) / 2;  
8:        if (nums[mid] < target) lo = mid + 1;  
9:        else hi = mid;  
10:      }  
11:      if (nums[hi] != target) return res;  
12:      res[0] = hi;  
13:      hi = nums.size()-1;  
14:      while (lo < hi) {  
15:        int mid = lo + (hi - lo) / 2+1;  
16:        if (nums[mid] > target) hi = mid - 1;  
17:        else lo = mid;  
18:      }  
19:      res[1] = lo;  
20:      return res;  
21:    }  
22:  };  

367. Valid Perfect Square

A classical binary search problem. I use integer for mid in first place but get LTE. The reason is mid*mid gets overflowed. So I have to declare mid as long long.

1:  class Solution {  
2:  public:  
3:    bool isPerfectSquare(int num) {  
4:      int lo = 1, hi = num;  
5:      while (lo <= hi) {  
6:        long long mid = lo + (hi - lo) / 2;  
7:        if (mid*mid == num) return true;  
8:        else if (mid*mid > num) hi = mid-1;  
9:        else lo = mid+1;  
10:      }  
11:      return false;  
12:    }  
13:  };  

81. Search in Rotated Sorted Array II

Same idea of "33. Search in Rotated Sorted Array" but with one more case since there are duplicates.

Case 1: nums[lo] > nums[mid]
In this case, the right part of nums[mid] must be sorted. If the target is in sorted part, we make the search interval to be the sorted part. Otherwise, we make the search interval to be the rotated part.

Case 2: nums[mid] > nums[hi]
In this case, the left part of nums[mid] must be sorted. Then do as Case 1.

Case 3: nums[lo] == num[hi]
After excluding case 1 and case 2, there remaining condition is:
nums[lo] <= nums[mid] && nums[mid] <= nums[hi]
Since there are duplicates, all we need to deal with is the special case where nums[lo] == nums[hi]. And in this case, we only need to move lo and hi one step toward each other.

1:  class Solution {  
2:  public:  
3:    bool search(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] == target) return true;  
8:        if (nums[lo] > nums[mid]) {  
9:          // there is rotation, the right part of mid is sorted  
10:          if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;  
11:          else hi = mid - 1;  
12:        } else if (nums[hi] < nums[mid]) {  
13:          // there is rotation, the left part of mid is sorted  
14:          if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;  
15:          else lo = mid + 1;  
16:        } else if (nums[lo] < nums[hi]) {  
17:          // there is no rotation  
18:          if (target > nums[mid]) lo = mid + 1;  
19:          else hi = mid - 1;  
20:        } else {  
21:          lo++;  
22:          hi--;  
23:        }  
24:      }  
25:      return false;  
26:    }  
27:  };  

33. Search in Rotated Sorted Array

The key here is to check is the interval [lo, hi] is rotated or not. If it is rotated, there are two cases:

Case 1: nums[lo] > nums[mid]
In this case, the right part of nums[mid] must be sorted. If the target is in sorted part, we make the search interval to be the sorted part. Otherwise, we make the search interval to be the rotated part.

Case 2: nums[mid] > nums[hi]
In this case, the left part of nums[mid] must be sorted. Then do as Case 1.

By dealing with case 1 and case 2 above, we'll eventually make the target into a sorted search interval. And in this interval, we just search as normal binary search.

1:  class Solution {  
2:  public:  
3:    int search(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] == target) return mid;  
8:        if (nums[lo] > nums[mid]) {  
9:          // there is rotation, the right part of mid is sorted  
10:          if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;  
11:          else hi = mid - 1;  
12:        } else if (nums[hi] < nums[mid]) {  
13:          // there is rotation, the left part of mid is sorted  
14:          if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;  
15:          else lo = mid + 1;  
16:        } else {  
17:          // there is no rotation  
18:          if (target > nums[mid]) lo = mid + 1;  
19:          else hi = mid - 1;  
20:        }  
21:      }  
22:      return -1;  
23:    }  
24:  };  

35. Search Insert Position

A typical binary search solution. But need to be careful about the boundary.

1:  class Solution {  
2:  public:  
3:    int searchInsert(vector<int>& nums, int target) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (target == nums[mid]) return mid;  
8:        else if (target > nums[mid]) lo = mid + 1;  
9:        else hi = mid-1;  
10:      }  
11:      return lo;  
12:    }  
13:  };  

74. Search a 2D Matrix

Binary search for candidate row first and binary search in that row.

1:  class Solution {  
2:  public:  
3:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
4:      int rows = matrix.size(), cols = matrix[0].size();  
5:      int row = 0, col = 0;  
6:      int lo = 0, hi = rows-1;  
7:      while (lo <= hi) {  
8:        int mid = lo + (hi - lo) / 2;  
9:        if (target == matrix[mid][0]) return true;  
10:        else if (target > matrix[mid][0]) {  
11:          lo = mid + 1;  
12:        } else {  
13:          hi = mid - 1;  
14:        }  
15:      }  
16:      if (lo == 0) return false;  
17:      row = lo-1;  
18:      lo = 0; hi = cols-1;  
19:      while (lo <= hi) {  
20:        int mid = lo + (hi - lo) / 2;  
21:        if (target == matrix[row][mid]) return true;  
22:        else if (target > matrix[row][mid]) {  
23:          lo = mid + 1;  
24:        } else {  
25:          hi = mid - 1;  
26:        }  
27:      }  
28:      return false;  
29:    }  
30:  };  

230. Kth Smallest Element in a BST

My original solution is to traverse the tree in preorder and save the result in an array. Return the k-th number in the array.

1:  class Solution {  
2:  public:  
3:    int kthSmallest(TreeNode* root, int k) {  
4:      vector<int> res;  
5:      helper(root, res);  
6:      return res[k-1];  
7:    }  
8:    void helper(TreeNode* root, vector<int> &res) {  
9:      if (root == NULL) return;  
10:      helper(root->left, res);  
11:      res.push_back(root->val);  
12:      helper(root->right, res);  
13:    }  
14:  };  

Another way is to count the left nodes and use binary search to get the k-th number. However, this is not an optimal solution whose running time is O(NlogN). If we can modify augment the TreeNode data structure and keep track its left child numbers when building the tree, we can achieve the search by O(logN).

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:    int kthSmallest(TreeNode* root, int k) {  
13:      int c = countNodes(root->left);  
14:      if (c == k-1) return root->val;   
15:      if (c < k-1) {  
16:        return kthSmallest(root->right, k-c-1);  
17:      } else {  
18:        return kthSmallest(root->left, k);  
19:      }  
20:    }  
21:    int countNodes(TreeNode *root) {  
22:      if (root == NULL) return 0;  
23:      return 1 + countNodes(root->left) + countNodes(root->right);  
24:    }  
25:  };