yitonghe00

// Binary search solution
// Time: O(logn) where n is the quotient, 1ms
// Space: O(1), 33,7mb
class Solution {
    public int divide(int dividend, int divisor) {
        int sign = 1;
        if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
            sign = -1;
        }
        long ldividend = Math.abs((long) dividend);

yitonghe00

class Solution {
    public int mySqrt(int x) {
        //Solution #1: Cast to long type to avoid overflow
        //Corner case: x == 0
        if(x == 0) {
            return 0;
        }
        long begin = 1, end = (long)x - 1, mid;
        
        while(begin < end - 1) {

yitonghe00

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean sign = (dividend > 0) ^ (divisor > 0);
        long dvd = Math.abs((long) dividend);
        long dvs = Math.abs((long) divisor);
        int res = 0;
        while (dvd >= dvs) {

yitonghe00

// Binary search solution: min always lies in the rotated half
// Time: O(logn), 0ms
// Space: O(1), 38.2mb
class Solution {
    public int findMin(int[] nums) {
        // Corner case: 1 element
        if(nums.length == 1) {
            return nums[0];
        }
        

yitonghe00

// Binary search solution: min always lies in the rotated half
// Modified from 153: To deal with duplicates, scan through when begin == mid == end
// Note: take care of equal when comparing
// Time: O(n), 0ms
// Space: O(1), 38.2mb
class Solution {
    public int findMin(int[] nums) {
        // Corner case: 1 element
        if(nums.length == 1) {
            return nums[0];

yitonghe00

//Find the h in the range of [0, citations.length], not in the array
//Runtime: O(logn) 14ms
class Solution {//[0,3,3]  [3,3,3] [] [0] [0,0] [2] [0,0,4,4] [0,1,1,2]
    public int hIndex(int[] citations) {
        int begin = 0, end = citations.length, mid, h = 0;
        if(citations.length > 0) {
            h = Math.min(citations.length, citations[0]);
        }
        
        while(begin <= end) {

yitonghe00

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int begin = 0, end = n, mid;
        
        while(begin < end) {
            mid = begin + (end - begin) / 2;
            

yitonghe00

// Binary Sort + HashTable solution: do binary search for each interval with the help of helper map and array (sort)
// Time: O(nlogn), 15ms
// Space: O(n), 46.5mb
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int len = intervals.length;
        int[] array = new int[len];
        Map<Integer, Integer> map = new HashMap<> ();
        int[] ans = new int[len];
        

yitonghe00

// Two pointer solution: min/max substring templete
// Time: O(n), 2ms
// Space: O(1), 37.4mb
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // char table that keeps track of characters we have met
        int[] table = new int[128];
        int count = 0; // Count of unique char
        
        int begin = 0, end = 0, maxLen = 0; // Window is [begin, end)

yitonghe00

// Two pointer: begin/end pointers and move inward
// Time: O(n), 2ms
// Space: O(1), 39.9mb
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int max = 0;
        
        while(left < right) {
            max = Math.max(max, Math.min(height[left], height[right]) * (right - left));