Leetcode: First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
A binary search problem. 

Code (Java):

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int lo = 1;
        int hi = n;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (isBadVersion(lo)) {
            return lo;
        }
        
        if (isBadVersion(hi)) {
            return hi;
        }
        
        return 0;
    }
}

Update on 10/24/15:
We use long instead of int to avoid the integer overflow problem. 

Code (Java):

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return 0;
        }
        
        long lo = 1;
        long hi = n;
        
        while (lo + 1 < hi) {
            long mid = lo + (hi - lo) / 2;
            boolean bad = isBadVersion((int) mid);
            if (bad) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        
        if (isBadVersion((int) lo)) {
            return (int) lo;
        }
        
        if (isBadVersion((int) hi)) {
            return (int) hi;
        }
        
        return 0;
    }
}

Update on 1/26/15:

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return -1;
        }
        
        int lo = 1;
        int hi = n;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        
        if (isBadVersion(lo)) {
            return lo;
        }
        
        return -1;
    }
}

Leetcode: Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Understand the problem:
The problem is similar to the search in rotated array II. The key is to handle when the duplicates exist. The only case where we need to handle specially is when nums[lo] == nums[mid] == nums[hi]. Because in this case, we have no idea which half to move. In this case, we move lo ++ .

Code (Java):

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
                lo++;
            } else if (nums[lo] < nums[mid] && nums[mid] <= nums[hi]) {
                return nums[lo];
            } else if (nums[lo] <= nums[mid] && nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else if (nums[lo] >= nums[mid] && nums[mid] <= nums[hi]) {
                hi = mid;
            }
        }
        
        if (nums[lo] <= nums[hi]) {
            return nums[lo];
        } else {
            return nums[hi];
        }
    }
}

Update on 10/12/15:

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[lo] == nums[mid]) {
                lo++;
                continue;
            }
            
            if (nums[lo] < nums[hi]) {
                return nums[lo];
            } else if (nums[lo] < nums[mid]) {
                lo = mid;
            } else if (nums[mid] <= nums[hi]) {
                hi = mid;
            }
        }
        
        return Math.min(nums[lo], nums[hi]);
    }
}

Leetcode: Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Understand the problem:
The problem looks like the search in rotated sorted array. It is clearly that we need to use the binary search. The key is to decide which half we wanna go in each iteration. There are three cases to consider:
  -- Case 1: nums[lo] < nums[mid] && nums[mid] < nums[hi]. It indicates that the array is sorted. So the first element must be the minimum. So return nums[lo]. 
  -- Case 2: nums[lo] < nums[mid] && nums[mid] > nums[hi]. e.g.. 4 5 6 7 0 1 2. In this case the minimum number must be in the right half. So lo = mid + 1;
  -- Case 3: nums[lo] > nums[mid] && nums[mid] < nums[hi]. e..g. 5 6 7 0 1 2 4. In this case, the minimum must be in the left half, but including the mid. So hi = mid; 
  -- Case 4 (NOT EXISTED): nums[lo] > nums[mid] && nums[mid] > nums[hi]. 7 6 5 4 2 1 0. 
This case does not exist since there is no way to rotate the array like this. 

Code (Java):

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (nums[lo] < nums[mid] && nums[mid] < nums[hi]) {
                return nums[lo];
            }
            
            if (nums[lo] < nums[mid] && nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else if (nums[lo] > nums[mid] && nums[mid] < nums[hi]) {
                hi = mid;
            } 
        }
        
        if (nums[lo] <= nums[hi]) {
            return nums[lo];
        } else {
            return nums[hi];
        }
    }
}

Update on 10/12/15:

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (nums[lo] < nums[hi]) {
                return nums[lo];
            } else if (nums[mid] < nums[hi]) {
                hi = mid;
            } else if (nums[lo] < nums[mid]) {
                lo = mid;
            }
        }
        
        return Math.min(nums[lo], nums[hi]);
    }
}

Leetcode: Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

Understand the problem:
The neighbor of an element A[i] is defined as A[i - 1] and A[i + 1]. Therefore, the peak element is iff A[i] > A[i - 1] && A[i] > A[i + 1]. 

The brute-force solution is quite easy. Just scan and compare. So the time complexity would be O(N). 

However, as is required by the question, the solution should be in O(logn) time. We therefore must think of binary search. 

The idea is: 
  -- If the middle of the array is the peak element, then just return the index. 
  -- If the left neighbor is greater than the middle, move to the left. The peak element must exist in the left half. That is because the num[-1] = num[n] = -inf. 
  -- The same, if the right neighbor is greater than the middle, move to the right. 

Be careful to handle the boundary. Use the binary search template. 

Code (Java):

public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if (nums[mid - 1] > nums[mid]) {
                hi = mid;
            } else if (nums[mid + 1] > nums[mid]) {
                lo = mid;
            }
        }
        
        if (nums[hi] >= nums[lo]) {
            return hi;
        } else {
            return lo;
        }
    }
}

Update on 10/13:15:

public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            } else if (nums[mid] < nums[mid - 1]) {
                hi = mid - 1;
            } else if (nums[mid] < nums[mid + 1]) {
                lo = mid + 1;
            }
        }
        
        if (nums[lo] > nums[hi]) {
            return lo;
        } else {
            return hi;
        }
    }
} 

Leetcode: Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Understand the problem:
The problem gives two sorted array, A and B. Find out the median of the two sorted arrays. 
Note that the time complexity is required to be O(log(m+n)).

An initial thought was firstly merge the two arrays, then median is  the number on A.length + B.length - 1 / 2. However, merging will take O(m + n) time, which however the algorithm asks for a solution in log time. So it is naturally to think about the binary search.

One thing must take note is the definition of the median of a sorted array. Note that the return number is double in the problem. So if the array length is even, e.g. 1, 2, 3, 4. The median is the average of 2 and 3, i.e., 2 + 3 / 2 = 2.5

Solution:
http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/

The problem is equivalent to find the kth element in the two sorted array. The key is to decide how to eliminate part of the array each recursion. 

Code (Java):

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0.f;
        }
        
        int n1 = nums1.length;
        int n2 = nums2.length;
        
        if ((n1 + n2) % 2 == 1) {
            return findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1);
        } else {
            return (findMedianHelper(nums1, nums2, (n1 + n2) / 2) + 
                    findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1)) / 2;
        }
    }
    
    private double findMedianHelper(int[] nums1, int[] nums2, int k) {
        if (nums1 == null || nums1.length == 0) {
            return nums2[k - 1];
        }
        
        if (nums2 == null || nums2.length == 0) {
            return nums1[k - 1];
        }
        
        if (k == 1) {
            return Math.min(nums1[0], nums2[0]);
        }
        
        int n1 = nums1.length;
        int n2 = nums2.length;
        
        if (nums1[n1 / 2] > nums2[n2 / 2]) {
            if ((n1 / 2 + n2 / 2 + 1) >= k) {
                return findMedianHelper(Arrays.copyOfRange(nums1, 0, n1 / 2), nums2, k);
            } else {
                return findMedianHelper(nums1, Arrays.copyOfRange(nums2, n2 / 2 + 1, n2), 
                                        k - (n2 / 2 + 1));
            }
        } else {
            if ((n1 / 2 + n2 / 2 + 1) >= k) {
                return findMedianHelper(nums1, Arrays.copyOfRange(nums2, 0, n2 / 2), k);
            } else {
                return findMedianHelper(Arrays.copyOfRange(nums1, n1 / 2 + 1, n1), 
                                        nums2, k - (n1 / 2 + 1));
            }
        }
    }
}
Edit on 4/27/20:

public class Solution {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
        int n = A.length + B.length;
        
        if (n % 2 == 1) {
            return findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1);
        } else {
            return ((double) findMedianSortedArraysHelper(A, 0, B, 0, n / 2) + 
                findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1)) / 2;
        }
    }
    
    private int findMedianSortedArraysHelper(int[] A, int startOfA, int[] B, int startOfB, int k) {
        if (startOfA >= A.length) {
            return B[startOfB + k - 1];
        }
        
        if (startOfB >= B.length) {
            return A[startOfA + k - 1];
        }
        
        if (k == 1) {
            return Math.min(A[startOfA], B[startOfB]);
        }
        
        int halfOfA = startOfA + k / 2 - 1 >= A.length ? 
            Integer.MAX_VALUE : A[startOfA + k / 2 - 1];
        int halfOfB = startOfB + k / 2 - 1 >= B.length ?
            Integer.MAX_VALUE : B[startOfB + k / 2 - 1];
            
        if (halfOfA < halfOfB) {
            return findMedianSortedArraysHelper(A, startOfA + k / 2, B, startOfB, k - k / 2);
        } else {
            return findMedianSortedArraysHelper(A, startOfA, B, startOfB + k / 2, k - k / 2);
        }
    }
}

The complexity is log(k), where k is the kth elements after merged of the two arrays. For this particular problem, the k = (n + m) / 2. 

So why the complexity is logk? It's because for each time we can eliminate k/2 data in O(1) time. So overall the complexity is logk.

Leetcode: Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Understand the problem:
The problem gives a sorted array of integers, find the starting and ending position of a given target value. It requires the time complexity as O(logn), which indicates to use binary search. If not found, return [-1, -1]. 

Solution:
Since the problem asks for O(logn) solution, we can solve this problem by using the binary search for the first and last index of the target.

Code (Java):

public class Solution {
    public int[] searchRange(int[] A, int target) {
        if (A == null || A.length == 0) {
            int[] result = {-1, -1};
            return result;
        }
        int[] result = new int[2];
        // Find the first index of the target value
        result[0] = binarySearchFirstIndex(A, target);
        
        if (result[0] == -1) {
            result[1] = -1;
            return result;
        }
        
        // Find the last index of the target value
        result[1] = binarySearchLastIndex(A, target);
        
        return result;
    }
    
    private int binarySearchFirstIndex(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                hi = mid;
            } else if (A[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (A[lo] == target) {
            return lo;
        }
        
        if (A[hi] == target) {
            return hi;
        }
        
        return -1;
    }
    
    private int binarySearchLastIndex(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                lo = mid;
            } else if (A[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (A[hi] == target) {
            return hi;
        }
        
        if (A[lo] == target) {
            return lo;
        }
        
        return -1;
    }
}

Leetcode: Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Understand the problem:
The problem gives a sorted array which is rotated at some pivot, search for a target value. This problem clearly indicates that we do find the number in O(logn) time, just as binary search. 

One naive idea is to find the pivot and rotate the array back, then we can apply the binary search. But rotating the array would take on average O(n) time, which is not allowed in this problem. 

Solution:
The solution is very similar to binary search. Note that no matter how we rotated the array, there must be at least one part which is sorted. If the target is at the sorted part, we just search that part until we found; else we go the unsorted part. 

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

Discussion:
Now let's analyze the complexity. If the target just falls into the sorted part, the complexity could be O(logn). How about the worst case, where target is always not in the sorted part, then we have to iterate all the data of the array, then the complexity becomes O(n). So on average, we can see that the complexity is O(logn).

Summary:
This is an extension of the binary search. So it is very important that you got familiar with the binary search. 

Update on 9/29/14:

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else {
                if (A[mid] < target && target <= A[hi] ) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
        }
        
        if (target == A[lo]) {
            return lo;
        }
        
        if (target == A[hi]) {
            return hi;
        }
        
        return -1;
        
    }
}

Update on 7/13/18:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int ans = -1;
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else {
                // case 1: left half is sorted
                //
                if (nums[lo] < nums[mid]) {
                    if (target >= nums[lo] && target < nums[mid]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else if (nums[mid] < nums[hi]) {
                    if (target > nums[mid] && target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
        }
        
        if (nums[lo] == target) {
            return lo;
        }
        
        if (nums[hi] == target) {
            return hi;
        }
        
        return -1;
    }
}

Leetcode: Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Analysis:
From the properties of the array, we can see that the array is actually well sorted, from left to right, top to bottom. 

Naive Solution:
Since the array is well sorted, we may use the binary search to search the target element. The only trick is to treat the 2D array as 1D and flatten the index. 

Code (Java):

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length; // row
        int n = matrix[0].length; // column
        
        return binaryMatrixSearch(matrix, target, 0, m * n - 1, n);
    }
    
    private boolean binaryMatrixSearch(int[][] matrix, int target, int lo, int hi, int n) {
        if (lo > hi) return false;
        
        int mid = (lo + hi) / 2;
        int i = getRowIndex(mid, n);
        int j = getColIndex(mid, n);
        
        if (matrix[i][j] == target) return true;
        else if (matrix[i][j] > target) return binaryMatrixSearch(matrix, target, lo, mid - 1, n);
        else return binaryMatrixSearch(matrix, target, mid + 1, hi, n);
    }
    
    // Calculate the row index
    private int getRowIndex(int mid, int n) {
        return mid / n;
    }
    
    // Calculate the column index
    private int getColIndex(int mid, int n) {
        return mid % n;
    }
}

Discussion:
This solution is very straight forward and almost similar to the 1D binary search. The major difference is after calculating the mid index, and how to calculate the 2D row and column indices. The time complexity is O(log m*n) since it is a m * n array. The space complexity is O(1).  

Note that above code is recursive binary search. The binary search can also be implemented as iterative way:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return false;
        
        int m = matrix.length; // row
        int n = matrix[0].length; // col
        
        int lo = 0;
        int hi = m * n - 1;
        int mid;
        
        while (lo <= hi) {
            mid = (lo + hi) / 2;
            
            int i = getRowIndex(mid, n);
            int j = getColIndex(mid, n);
            
            if (matrix[i][j] == target) return true;
            else if (target < matrix[i][j]) hi = mid - 1;
            else lo = mid + 1;
        }
        return false;
    }
    private int getRowIndex(int mid, int n) {
        return mid / n;
    }
    
    private int getColIndex(int mid, int n) {
        return mid % n;
    }
}

Update on 9/29/14:
Another idea to solve this problem is to first find out which row the target value will reside in, then find out the value in the specific row.

Code (Java):

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        
        // Find the row
        int row = findRow(matrix, target);
        if (row == -1) {
            return false;
        }
        
        // Find the column
        int col = findCol(matrix[row], target);
        if (col == -1) {
            return false;
        }
        
        return true;
    }
    
    private int findRow(int[][] matrix, int target) {
        int lo = 0;
        int hi = matrix.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[mid][0] == target) {
                return mid;
            }
            
            if (matrix[mid][0] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (matrix[lo][0] == target) {
            return lo;
        } else if (matrix[hi][0] == target) {
            return hi;
        } else if (matrix[lo][0] < target && target < matrix[hi][0]) {
            return lo;
        } else if (matrix[hi][0] < target) {
            return hi;
        } else {
            return -1;
        }
    }
    
    private int findCol(int[] cols, int target) {
        int lo = 0;
        int hi = cols.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (cols[mid] == target) {
                return mid;
            }
            
            if (cols[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (cols[lo] == target) {
            return lo;
        }
        
        if (cols[hi] == target) {
            return hi;
        }
        
        return -1;
    }
}

Update on 10/7/15:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Step 1: find the rowId of the target number
        int lo = 0;
        int hi = m - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        
        if (matrix[hi][0] == target || matrix[lo][0] == target) {
            return true;
        }
        
        int rowId;
        if (target > matrix[lo][0] && target <= matrix[lo][n - 1]) {
            rowId = lo;
        } else {
            rowId = hi;
        }
        
        // Step 2: find the target number in the rowId
        lo = 0;
        hi = n - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (matrix[rowId][mid] == target) {
                return true;
            } else if (matrix[rowId][mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        if (matrix[rowId][hi] == target || matrix[rowId][lo] == target) {
            return true;
        }
        
        return false;
    }
}