283. Move Zeroes

Simple two pointers problem. We can have two pointers i and j. i is pointing to the next element in the array to check and j is pointing to the first 0 position. So for example [0, 0, 0, 1, 2]
1st round, i = 0, j = 0: 0, 0, 0, 1, 2
2nd round, i = 1, j = 0: 0, 0, 0, 1, 2
3rd round, i = 2, j = 0: 0, 0, 0, 1, 2
4th round, i = 3, j = 0: 1, 0, 0, 0, 2
5th round, i = 4, j = 1, 1, 2, 0, 0, 0

Another example, [1, 0, 3]
1st round, i = 0, j = 0: 1, 0, 3
2nd round, i = 1, j = 1: 1, 0, 3
3rd round, i = 2, j = 1: 1, 3, 0

1:  class Solution {  
2:  public:  
3:    void moveZeroes(vector<int>& nums) {  
4:      int i = 0, j = 0;  
5:      while (i < nums.size()) {  
6:        if (nums[i] == 0) {  
7:          i++;  
8:        } else {  
9:          swap(nums[i++], nums[j++]);  
10:        }  
11:      }  
12:    }  
13:  };  

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

11. Container With Most Water

The idea is to compute the container from the widest to highest. Starting from two ends, we get the widest container's area. Then question is how we can get a container that has larger area? Since we are going to shrink the container's width, the only chance we can get a larger area is to have taller container such that height offsets the width. So we move the shorter end toward to the taller end with hoping to find a even taller end.

1:  class Solution {  
2:  public:  
3:    int maxArea(vector<int>& height) {  
4:      if (height.size() == 0) return 0;  
5:      int l = 0, r = height.size()-1, area = INT_MIN;  
6:      while (l < r) {  
7:        if (height[l] < height[r]) {  
8:          area = max(area, height[l] * (r-l));  
9:          l++;  
10:        } else {  
11:          area = max(area, height[r] * (r-l));  
12:          r--;  
13:        }  
14:      }  
15:      return area;  
16:    }  
17:  };  

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

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

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

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

360. Sort Transformed Array

If a >=0, the minimum value is at the array's vertex. So we need to move the two end pointers toward the vertex and output from right to left.
If a <0, the maximum value is at the array's vertex. So we need to move the two end pointers toward the vertex but output from left to right.

1:  class Solution {  
2:  public:  
3:    vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {  
4:      int start = 0, end = nums.size()-1;  
5:      int i = a >= 0 ? nums.size()-1 : 0;  
6:      vector<int> res(nums.size(), 0);  
7:      while (start <= end) {  
8:        int startNum = computeNumber(nums[start], a, b, c);  
9:        int endNum = computeNumber(nums[end], a, b, c);  
10:        if (a >= 0) {  
11:          if (startNum >= endNum) { res[i--] = startNum; start++; }  
12:          else { res[i--] = endNum; end--; }  
13:        } else {  
14:          if (startNum <= endNum) { res[i++] = startNum; start++; }  
15:          else { res[i++] = endNum; end--; }  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:    int computeNumber(int n, int a, int b, int c) {  
21:      return a*n*n+b*n+c;  
22:    }  
23:  };  

340. Longest Substring with At Most K Distinct Characters

I implemented a naive code first. And of course, it doesn’t pass large test set.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringKDistinct(string s, int k) {  
4:      if (s.size() < k) return s.size();  
5:      int res = 0;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        vector<int> letters(256, 0);  
8:        int count = 0;  
9:        int j = i;  
10:        while (j < s.size()) {  
11:          if (letters[s[j]] == 0) {  
12:            letters[s[j]] = 1;  
13:            count++;  
14:            if (count > k) break;  
15:          }  
16:          j++;  
17:        }  
18:        res = max(res, j-i);  
19:      }  
20:      return res;  
21:    }  
22:  };  

The top rated solution uses sliding window. Keep two pointers as the starting of the window and the end of the window. First of all, keep moving the right end of the window until the distinct characters are more than K. Then move the left end of the window until the distinct characters are equal to K. Then move right end again.

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

159. Longest Substring with At Most Two Distinct Characters

Same as problem “340. Longest Substring with At Most K Distinct Characters”.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstringTwoDistinct(string s) {  
4:      int i = 0, j = -1;  
5:      vector<int> dict(256, 0);  
6:      int len = 0;  
7:      int k = 0;  
8:      while (i < s.size()) {  
9:        k += dict[s[i]]++ == 0;  
10:        while (k > 2) k -= --dict[s[++j]] == 0;  
11:        len = max(len, i-j);  
12:        i++;  
13:      }  
14:      return len;  
15:    }  
16:  };  

361. Bomb Enemy

Let count[i][j] be the maximum enemies that a bomb can kill in row i, col j. The naive solution will run O(m*n*(m+n)) time. The trick here to make it O(mn) is to keep a head and a tail variables. The head variable keeps the maximum enemies from left to grid[i][j] and the tail variable keeps the maximum enemies from the right to grid[i][j]. So for count[i][j], we want to add head if grid[i][j] is empty, i.e. grid[i][j] == 0 and for count[i][col-1-j], we want to add tail if grid[i][col-1-j] is empty. So when we traverse the row from 0 to col, we actually computes the maximum enemies for every position. Same for scanning columns. head is incremented by 1 if it finds an enemy or becomes 0 if it finds a wall. Same for tail.

1:  class Solution {  
2:  public:  
3:    int maxKilledEnemies(vector<vector<char>>& grid) {  
4:      int row = grid.size();  
5:      if (row == 0) return 0;  
6:      int col = grid[0].size();  
7:      vector<vector<int>> count(row, vector<int>(col, 0));  
8:      int i = 0, j = 0, head = 0, tail = 0;  
9:      for (i = 0; i < row; i++) {  
10:        for (j = head = tail = 0; j < col; j++) {  
11:          count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);  
12:          count[i][col-1-j] = grid[i][col-1-j] != '0' ? 0 : (count[i][col-1-j] + tail);  
13:          head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));  
14:          tail = grid[i][col-1-j] == 'W' ? 0 : (tail + (grid[i][col-1-j] == 'E' ? 1 : 0));  
15:        }  
16:      }  
17:      for (j = 0; j < col; j++) {  
18:        for (i = head = tail = 0; i < row; i++) {  
19:          count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);  
20:          count[row-1-i][j] = grid[row-1-i][j] != '0' ? 0 : (count[row-1-i][j] + tail);  
21:          head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));  
22:          tail = grid[row-1-i][j] == 'W' ? 0 : (tail + (grid[row-1-i][j] == 'E' ? 1 : 0));  
23:        }  
24:      }  
25:      int res = 0;  
26:      for (i = 0; i < row; i++) {  
27:        for (j = 0; j < col; j++) {  
28:          res = max(res, count[i][j]);  
29:        }  
30:      }  
31:      return res;  
32:    }  
33:  };  

259. 3Sum Smaller

For a sorted array, if we fixed a number nums[i], and search from two ends of the rest array, i.e. nums[left], nums[right] where left and right is initialized by i+1 and nums.size()-1 respectively, we’ll see that if nums[left] + nums[right] >= target - nums[i], we want to move the right end to left. Once nums[left] + nums[right] < target - nums[i], we know that all numbers in [left, right] will there will be (right - left) triples that satisfy their sum less than target.

1:  class Solution {  
2:  public:  
3:    int threeSumSmaller(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      int count = 0, left = 0, right = nums.size()-1;  
6:      sort(nums.begin(), nums.end());  
7:      for (int i = 0; i < right && i < nums.size()-2; i++) {  
8:        if (nums[i] + nums[i+1] + nums[i+2] >= target) break;  
9:        int left = i+1, right = nums.size()-1;  
10:        int t = target - nums[i];  
11:        while (left < right) {  
12:          while (left < right && nums[left] + nums[right] >= t) right--;  
13:          count += right - left;  
14:          left++;  
15:        }  
16:      }  
17:      return count;  
18:    }  
19:  };  

When I revisited this problem, I found a more concise way though the idea behind is still the same.

1:  class Solution {  
2:  public:  
3:    int threeSumSmaller(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int count = 0;  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        int j = i+1, k = nums.size()-1, t = target - nums[i];  
9:        while (j < k) {  
10:          if (nums[j] + nums[k] >= t) k--;  
11:          else count += k - j++;  
12:        }  
13:      }  
14:      return count;  
15:    }  
16:  };  

42. Trapping Rain Water

I don't have idea to solve this problem in first place. I followed the top voted solution. The idea is instead of computing the area by height * width we can do it in a cumulative way. We scan inner ward from the left and right ends. We alway focus on the lower height. If current left rectangle is higher than the right rectangle, then we can guarantee trapped water by the left rectangle and the maximum rectangle so far on right.

Case 1: left height is lower than the right height.
We focus on the left side. In the left side, we keep the highest height so far. If current height is less than the highest one, so the water trap for current position is (highest height - current height) (you can image two bars with one higher than the other). Otherwise, we update the highest height to current height and no water trap for current position.

Case 2: left height is higher than the right height.
We focus on the right side. Same idea with Case 1.

1:  class Solution {  
2:  public:  
3:    int trap(vector<int>& height) {  
4:      int maxLeftHeight = 0, maxRightHeight = 0;  
5:      int left = 0, right = height.size()-1;  
6:      int area = 0;  
7:      while (left <= right) {  
8:        if (height[left] <= height[right]) {  
9:          if (maxLeftHeight <= height[left]) maxLeftHeight = height[left];  
10:          else area += maxLeftHeight - height[left];  
11:          left++;  
12:        } else {  
13:          if (maxRightHeight <= height[right]) maxRightHeight = height[right];  
14:          else area += maxRightHeight - height[right];  
15:          right--;  
16:        }  
17:      }  
18:      return area;  
19:    }  
20:  };  

5. Longest Palindromic Substring

My intuition is to use DP. The dp[i] saves the longest valid palindrome and dp[i] = dp[i-1] + 2 if s[i-dp[i-1]-1] == s[i]. However, this state transition formula doesn't cover all cases because palindrome can be odd or even long. The right DP way is to have dp[i][j] true if s[i...j] is a palindrome. So the state transition formula is dp[i][j] = true if s[i] == s[j] && dp[i+1][j-1]. The running time is O(n*n).

1:  class Solution {  
2:  public:  
3:    string longestPalindrome(string s) {  
4:      int n = s.size();  
5:      int maxLen = 1, start = 0;  
6:      //vector<vector<bool>> dp(1000, vector<bool>(1000, false));  
7:      bool dp[1000][1000] = {false};  
8:      for (int i = 0; i < n; i++) dp[i][i] = true;  
9:      for (int i = 0; i < n-1; i++) {  
10:        if (s[i] == s[i+1]) {  
11:          dp[i][i+1] = true;  
12:          start = i;  
13:          maxLen = 2;  
14:        }  
15:      }  
16:      for (int l = 3; l <= n; l++) {  
17:        for (int i = 0; i < n-l+1; i++) {  
18:          int j = i+l-1;  
19:          if (s[i] == s[j] && dp[i+1][j-1]) {  
20:            dp[i][j] = true;  
21:            start = i;  
22:            maxLen = l;  
23:          }  
24:        }  
25:      }  
26:      return s.substr(start, maxLen);  
27:    }  
28:  };  

Another way is scan the string and for each position scan toward two ends and check if any palindrome exists. Particularly, we need to deal with even and odd long palindromes (note they are not exclusive).

1:  class Solution {  
2:  private:  
3:    int maxLen;  
4:    int start;  
5:  public:  
6:    string longestPalindrome(string s) {  
7:      start = 0;  
8:      maxLen = 1;  
9:      for (int i = 0; i < s.size()-1; i++) {  
10:        if (s[i] == s[i+1]) {  
11:          search(s, i, i+1);  
12:        }  
13:        search(s, i, i);  
14:      }  
15:      return s.substr(start, maxLen);  
16:    }  
17:    void search(string s, int i, int j) {  
18:      int l = 1;  
19:      while ((i-l) >= 0 && (j+l) < s.size()) {  
20:        if (s[i-l] != s[j+l]) break;  
21:        l++;  
22:      }  
23:      int len = j-i+2*l-1;  
24:      if (len > maxLen) {  
25:        maxLen = len;  
26:        start = i-l+1;  
27:      }  
28:    }  
29:  };  

4Sum

My intuition is derive the solution from 3Sum. Basically, the same idea.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> fourSum(vector<int>& nums, int target) {  
4:      vector<vector<int>> res;  
5:      bool flag = false;  
6:      if (nums.empty()) return res;  
7:      sort(nums.begin(), nums.end());  
8:      for (int i = 0; i < (int)nums.size()-3; i++) {  
9:        if (i > 0 && nums[i] == nums[i-1]) continue;  
10:        int sum3 = target-nums[i];  
11:        flag = false;  
12:        for (int j = i+1; j < (int)nums.size()-2; j++) {  
13:          if (flag && nums[j] == nums[j-1]) continue;  
14:          flag = true;  
15:          int sum2 = sum3-nums[j];  
16:          int start = j+1, end = nums.size()-1;  
17:          while (start < end) {  
18:            if (nums[start]+nums[end]==sum2) {  
19:              vector<int> sol;  
20:              sol.push_back(nums[i]);  
21:              sol.push_back(nums[j]);  
22:              sol.push_back(nums[start++]);  
23:              sol.push_back(nums[end--]);  
24:              res.push_back(sol);  
25:              while (start < end && nums[start] == nums[start-1]) start++;  
26:              while (start < end && nums[end] == nums[end+1]) end--;  
27:            } else if (nums[start]+nums[end]<sum2) {  
28:              start++;  
29:            } else {  
30:              end--;  
31:            }  
32:          }  
33:        }  
34:      }  
35:      return res;  
36:    }  
37:  };  

15. 3Sum

The idea is to sort the array first and scan the array from left to right. When scanning the array, we fix the current element and start check its right subarray by two pointers. Since the array is sorted, for the two pointers, we know that:
1. Sum of nums[i], nums[l], nums[r] is less than target, move the left pointer.
2. Sum of nums[i], nums[l], nums[r] is larger than target, move the right pointer.
3. Target is found, save the triple elements.

Since the problem requires the result to exclude dups, I first tried to use set to store the triples but got TLE. Then I have to add line 8, 13-14 to achieve the requirement.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> threeSum(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      if (nums.size() < 3) return res;  
6:      sort(nums.begin(), nums.end());  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        if (i == 0 || nums[i-1] != nums[i]) {  
9:          int l = i+1, r = nums.size()-1, t = -nums[i];  
10:          while (l < r) {  
11:            if (nums[l]+nums[r]==t) {  
12:              res.push_back(vector<int>{nums[i],nums[l],nums[r]});   
13:              while ((l < r) && (nums[l] == nums[l+1])) l++;  
14:              while ((l < r) && (nums[r] == nums[r-1])) r--;  
15:              l++, r--;  
16:            }  
17:            else if (nums[l]+nums[r]<t) l++;  
18:            else r--;  
19:          }  
20:        }  
21:      }  
22:      return res;  
23:    }  
24:  };  

209. Minimum Size Subarray Sum

We can have two pointers. One scans the array and the other keeps the start position of a subarray that is supposed to have sum larger or equal to the target. One the subarray's sum is larger or equal to the target, we save the length of subarray and move the start point forward until we reach the position that the sum of the subarray is less than the target. After that, we continue scanning the array again. The total running time will be O(2n).

1:  class Solution {  
2:  public:  
3:    int minSubArrayLen(int s, vector<int>& nums) {  
4:      int start = 0, minLen = INT_MAX, sum = 0;  
5:      for (int i = 0; i < nums.size(); i++) {  
6:        sum += nums[i];  
7:        while (s <= sum) {  
8:          minLen = min(minLen, i-start+1);  
9:          sum -= nums[start++];  
10:        }  
11:      }  
12:      return minLen == INT_MAX ? 0 : minLen;  
13:    }  
14:  };  

16. 3Sum Closest

First of all, sort the array. If you don't sort the array, the running time will be n!, i.e. approximately O(n^3). After sort, you can have one pointer scan from 0 to n-2 and inside the scanning loop, create two pointers j and k starting from i+1 and n-1 respectively. And then there will be three cases:
Case 1: nums[i] +  nums[j] + nums[k] == target. Then return immediately
Case 2: nums[i] + nums[j] + nums[k] < target. Since array is sorted, we just need to move j to right.
Case 3: nums[i] + nums[j] + nums[k] > target. Same idea as Case 2, we just need to move k to left.

1:  class Solution {  
2:  public:  
3:    int threeSumClosest(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int closest = nums[0] + nums[1] + nums[2];  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        if (i > 0 && nums[i] == nums[i-1]) continue;  
9:        int j = i+1;  
10:        int k = nums.size()-1;  
11:        while (j < k) {  
12:          int sum = nums[i] + nums[j] + nums[k];  
13:          if (sum == target) return sum;  
14:          if (abs(target-sum) < abs(target-closest)) {  
15:            closest = sum;  
16:          }  
17:          if (sum < target) j++;  
18:          else k--;  
19:        }  
20:      }  
21:      return closest;  
22:    }  
23:  };  

When I revisited this problem, I had a bit more concise solution.

1:  class Solution {  
2:  public:  
3:    int threeSumClosest(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int minSum = nums[0]+nums[1]+nums[2];  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        int l = i+1, r = nums.size()-1, t = target-nums[i];  
9:        while (l < r) {  
10:          if (abs(t-nums[l]-nums[r]) < abs(minSum-target)) minSum = nums[l]+nums[r]+nums[i];   
11:          if (nums[l]+nums[r] == t) return target;  
12:          else if (nums[l]+nums[r] > t) r--;  
13:          else l++;  
14:        }  
15:      }  
16:      return minSum;  
17:    }  
18:  };  

80. Remove Duplicates from Sorted Array II

Maintain two pointers. One is to scan every elements from position 2 and the other keeps the end position for the valid array.

1:  class Solution {  
2:  public:  
3:    int removeDuplicates(vector<int>& nums) {  
4:      if (nums.size() < 3) return nums.size();  
5:      int end = 2;  
6:      for (int i = 2; i < nums.size(); i++) {  
7:        if (nums[i] != nums[end-1] || nums[i] != nums[end-2]) {  
8:          swap(nums[i], nums[end]);  
9:          end++;  
10:        }  
11:      }  
12:      return end;  
13:    }  
14:  };  

When I revisited this problem, I had a bit more concise way.

1:  class Solution {  
2:  public:  
3:    int removeDuplicates(vector<int>& nums) {  
4:      if (nums.size() < 3) return nums.size();  
5:      int i, j;  
6:      for (i = 2, j = 2; j < nums.size(); i++, j++) {  
7:        if (nums[i-2] != nums[j]) swap(nums[i], nums[j]);  
8:        else i--;   
9:      }  
10:      return i;  
11:    }  
12:  };  

240. Search a 2D Matrix II

Let i be the row index starting from 0 and j be the column index starting from matrix[0].size()-1.
The invariant is if target is less than matrix[i][j], then it won't be in column j (because elements in column j following row i is larger than the target), so we can move j one backward. Similarly, if target is larger than matrix[i][j], then it won't be in row i, so we can move i one forward.

1:  class Solution {  
2:  public:  
3:    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
4:      int i = 0, j = matrix[0].size() - 1;  
5:      while (i < matrix.size() && j >= 0) {  
6:        if (matrix[i][j] == target) return true;  
7:        else if (matrix[i][j] > target) j--;  
8:        else i++;  
9:      }  
10:      return false;  
11:    }  
12:  };