Sorting: Bubble Sort

https://www.hackerrank.com/challenges/ctci-bubble-sort/problem

static void countSwaps(int[] a) {
        int count = 0;
        boolean isSorted = false;
        int lastUnsorted = a.length - 1;
        // Every time the last element is sorted
        while (!isSorted) {
            isSorted = true;
            for (int i = 0; i < lastUnsorted; i++) {
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    isSorted = false;
                    count++;
                }
            }
            lastUnsorted--;
        }

        System.out.printf("Array is sorted in %d swaps.%n", count);
        System.out.printf("First Element: %d%n", a[0]);
        System.out.printf("Last Element: %d%n", a[a.length - 1]);
    }
    static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

410. Split Array Largest Sum

[TODO] Implement prefixSum + binary search in canSplit() method

二刷 07/2022

Version #1 二分答案

注意一个地方就是start不能小于nums里面最大的那个数

Time O(NlogSum) - N is the length of the nums array

Space O(1)

Runtime: 1 ms, faster than 86.51% of Java online submissions for Split Array Largest Sum.

Memory Usage: 42.3 MB, less than 18.28% of Java online submissions for Split Array Largest Sum.

class Solution {

    public int splitArray(int[] nums, int m) {

        int start = 0, end = 0;

        for (int num : nums) {

            end += num;

            start = Math.max(start, num);

        }

        // find the smallest number that can split

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (canSplit(nums, m, mid)) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return start;

    }

    private boolean canSplit(int[] nums, int m, int target) {

        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            if (sum + nums[i] > target) {

                m--;

                sum = nums[i];

            } else {

                sum += nums[i];

            }

            if (m <= 0) {

                return false;

            }

        }

        return true;

    }

}

一刷
Version #1 二分答案
https://leetcode.com/problems/split-array-largest-sum/discuss/89819/C++-Fast-Very-clear-explanation-Clean-Code-Solution-with-Greedy-Algorithm-and-Binary-Search
Time O(m log(2^31  - 1))
Space O(1)
99.89 %

[1,2147483647] 2


class Solution {
    public int splitArray(int[] nums, int m) {
        // Binary Search Answer
        // Given a max sum x, check if we ensure that every subarray sum is less than x, how many splits do we need
        // If number of split is less than m, then it is an valid answer
        // We want to find the minimum x
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int end = (1 << 31) - 1;
        int start = 0;
        // F F F T
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (canSplit(nums, mid, m)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    // x = 7, m = 2
    // [7,2,5,10,8]
    // O(m)
    private boolean canSplit(int[] nums, int x, int m) {
        m--;
        // Each subarray sum can't exceed x
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > x) {
                return false;
            }
            if (sum + nums[i] > x) {
                m--;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            if (m < 0) {
                return false;
            }
        }
        return true;
    }
}

354. Russian Doll Envelopes

Version #2
牛逼。。。 和dp一样先sort
然后对Height找longest increasing subsequence
看下面的神讲解

Time O(nlogn)
Space O(n)

1. Sort the array. Ascend on width and descend on height if width are same.
2. Find the longest increasing subsequence based on height.

---

• Since the width is increasing, we only need to consider height.
• [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]
• 
  

二刷
55.74 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // a[0]->w, a[1]->h
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        int len = envelopes.length;
        // dp[i] -> the lowest height to form a Russian Doll with size i - 1
        int[] dp = new int[len + 1];
        // find the first height larger than curr, if not found, curr is i + 1
        int count = 0;
        for (int[] envelope : envelopes) {
            int curr = envelope[1];
            int start = 1;
            int end = count;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (dp[mid] < curr) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            if (dp[start] >= curr) {
                dp[start] = curr;
            } else {
                count++;
                dp[count] = curr;
            }
        }
        return count;
    }
}

一刷
55.17 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        // Sort with width, if width equals, sort with height
        Arrays.sort(envelopes, (e1, e2) -> {
            if (e1[0] == e2[0]) {
                return e2[1] - e1[1]; // height
            } else {
                return e1[0] - e2[0];
            }
        });
        // Find longest increasing sequence for height
        int[] minEnd = new int[envelopes.length];
        int max = 0;
        minEnd[0] = envelopes[0][1];
        for (int i = 1; i < envelopes.length; i++) {
            // Given envelopes[i] with its height envelopes[i][1] find the first element that is larger or equal to current height, replace is
            // If not found, increate max
            int start = 0;
            int end = max;
            int currHeight = envelopes[i][1];
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (minEnd[mid] < currHeight) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            if (minEnd[start] >= currHeight) {
                minEnd[start] = currHeight;
            } else {
                max++;
                minEnd[max] = currHeight;
            }
        }
        return max + 1;
    }
}



Version #1 Straight Forward DP

O(nlogn) for sorting and O(n^2) for dp, so Time O(n^2)
Space O(n)

二刷
32.44 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // a[0]->w, a[1]->h
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        int result = 0;
        int len = envelopes.length;
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = 1 + max;
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}


一刷
3.93 %
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        // Sort with width, if width equals, sort with height
        Arrays.sort(envelopes, (e1, e2) -> {
            if (e1[0] == e2[0]) {
                return e1[1] - e2[1];
            } else {
                return e1[0] - e2[0];
            }
        });
        int result = 0;
        int len = envelopes.length;
        // dp[i] -> max number of envelopes that current envelop can contain
        int[] dp = new int[len];
        dp[0] = 1;
        for (int curr = 0; curr < len; curr++) {
            int max = 0;
            for (int prev = 0; prev < curr; prev++) {
                if (envelopes[curr][0] > envelopes[prev][0] && envelopes[curr][1] > envelopes[prev][1]) {
                    max = Math.max(dp[prev], max);
                }
            }
            dp[curr] = max + 1;
            result = Math.max(result, dp[curr]);
        }
        return result;
    }
}

275. H-Index II

The idea is to search for the first index from the sorted array so that :

citations[index] >= length(citations) - index. 

And return (length - index) as the result.


99.93 %
class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        // [1, 2, 3, 3]
        int start = 0;
        int end = citations.length - 1;
        int len = citations.length;
        while (start < end) {
            int mid = start + (end - start) / 2;
            // [mid, end] -> all have at least citations[mid] citations each
            if (citations[mid] >= len - mid) {
                end = mid;
            } else if (citations[mid] < len - mid + 1) {
                start = mid + 1;
            }
        }
        return citations[start] >= len - start ? len - start : 0;
    }

}

154. Find Minimum in Rotated Sorted Array II

二刷

Runtime: 1 ms, faster than 67.57% of Java online submissions for Find Minimum in Rotated Sorted Array II.

Memory Usage: 43.3 MB, less than 61.79% of Java online submissions for Find Minimum in Rotated Sorted Array II.

class Solution {

    public int findMin(int[] nums) {

        if (nums == null) {

            throw new IllegalArgumentException();

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] < nums[end]) {

                end = mid;

            } else if (nums[mid] == nums[end]) {

                end--;

            } else {

                start = mid + 1;

            }

        }

        return Math.min(nums[start], nums[end]);

    }

}

一刷

Version #2 Better
只考虑是否舍弃后半段
若mid, end 相等有可能
1.[3, 3, 3, 3, 3, 3] All sorted
2.[3, 3, 3, 1, 3, 3] Left half sorted
3.[1, 2, 3, 3, 3, 3] Right half sorted
So the only thing we can do is reduce end pointer by 1
100.00 %
class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < end) { // [start, end]
            int mid = start + (end - start) / 2;
            if (nums[mid] == nums[end]) {
                end--;
            } else if (nums[mid] < nums[end]) {
                end = mid;
            } else { // nums[mid] > nums[end]
                start = mid + 1;
            }
        }
        return nums[start];
    }
}


Version #1
把 start, mid, end相等作为edge case
17.04 %
class Solution {
    public int findMin(int[] nums) {
        // [3, 3, 3, 1, 3, 3]
        // [1, 1, 1, 3, 3, 3]
       
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < end) { // [start, end]
            int mid = start + (end - start) / 2;
            if (nums[mid] == nums[end] && nums[start] == nums[mid]) {
                start++;
                end--;
            } else if (nums[mid] <= nums[end]) {
                end = mid;
            } else { // nums[mid] > nums[end]
                start = mid + 1;
            }
        }
        return nums[start];
    }
}

153. Find Minimum in Rotated Sorted Array

二刷

把所有情况都讨论了一下然后straight forward地写了一遍

没有一刷的答案好

Runtime: 1 ms, faster than 32.60% of Java online submissions for Find Minimum in Rotated Sorted Array.

Memory Usage: 42.6 MB, less than 44.28% of Java online submissions for Find Minimum in Rotated Sorted Array.

class Solution {

    public int findMin(int[] nums) {

        if (nums == null) {

            throw new IllegalArgumentException();

        }

        int start = 0, end = nums.length - 1;

        

        

        //  0 1 2 3 4 5 6

        // [4,5,6,7,0,1,2]

        //  s           e   mid = 3, nums[mid] = 7

        //          s   e   mid = 5, nums[mid] = 1

        // 

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] > nums[start]) {

                if (nums[mid] < nums[end]) {

                    return nums[start];

                }

                start = mid + 1;

            } else {

                if (nums[mid] > nums[end]) {

                    return nums[end];

                }

                end = mid;

            }

        }

        return Math.min(nums[start], nums[end]);

    }

}

Version checking if mid to end is sorted

Runtime: 1 ms, faster than 32.60% of Java online submissions for Find Minimum in Rotated Sorted Array.

Memory Usage: 42.8 MB, less than 31.17% of Java online submissions for Find Minimum in Rotated Sorted Array.

class Solution {

    public int findMin(int[] nums) {

        // we should check if mid to end is sorted

        // If mid to end is sorted, then the answer is between [start, mid]

        // Otherwise the answer is between [mid + 1, end]

        if (nums == null) {

            throw new IllegalArgumentException();

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] < nums[end]) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return Math.min(nums[start], nums[end]);

    }

}

一刷

Version #3
如果start和end之间是rotated的，那么start就是end的下一个element，应该有start > end
此时的mid 如果大于等于start的话，证明mid落在了start和rotate点之间，此时应该有start=mid+1
如果mid小于start，证明mid落在了rotate点和end之间，此时应该end= mid

反之如果start<end，证明start和end区间是sorted的， 则start就是最小的
100.00 %
class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0, end = nums.length - 1;
        while (start < end) {
            if (nums[start] <= nums[end]) {
                return nums[start];
            }
            int mid = start + (end - start) / 2;
            if (nums[mid] >= nums[start]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return nums[start];
    }
}

Version #2 Better version
检查后半段是否是sorted
如果后半段是sorted, 则结果在[start, mid]
Time O(logn)
100.00 %
class Solution {
    public int findMin(int[] nums) {
        // Always discard the sorted half
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int start = 0;
        int end = nums.length - 1;
        // start, end
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < nums[end]) { // [mid, end] is sorted
                end = mid;
            } else { // nums[mid] > nums[end]
                start = mid + 1;
            }
        }
        return nums[start];
    }
}



Version #1
检查前半段是否是sorted
这个方法的问题在于如果前半段是sorted, 不能直接舍弃前半段，因为有可能后半段也是sorted, 此时舍弃前半段就是不对的


100.00 %

class Solution {
    public int findMin(int[] nums) {
        // Always discard the sorted half
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int start = 0;
        int end = nums.length - 1;
        // We need at least 3 elements to check
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[start] < nums[mid] && nums[mid] < nums[end]) {
                return nums[start];
            } else if (nums[start] < nums[mid]) { // [start, mid] is sorted
                start = mid + 1;
            } else { // [mid, end] is sorted, nums[mid] < nums[start]
                end = mid;
            }
        }
        return Math.min(nums[start], nums[end]);
    }
}

162. Find Peak Element

二刷

写了一个bug

一开始没有包括start==end的情况，导致[1]return-1

也可以写成

        if (nums[start] > nums[end]) {

            return start;

        }

        return end;

   

因为保证一定有peak

class Solution {

    public int findPeakElement(int[] nums) {

        if (nums == null) {

            return -1;

        }

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if ((mid == 0 || nums[mid] > nums[mid - 1]) && nums[mid] > nums[mid + 1]) {

                return mid;

            }

            if (nums[mid] < nums[mid + 1]) {

                start = mid + 1;

            } else {

                end = mid;

            }

        }

        if (start == end) {

            return start;

        }

        if (nums[start] > nums[end]) {

            return start;

        }

        if (nums[start] < nums[end]) {

            return end;

        }

        return -1;

    }

}

一刷

Binary Search
mid will never be nums.length - 1

100.00 %
class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if ((mid == 0 || nums[mid] > nums[mid - 1])  // start = 0, end = 1
                && (nums[mid] > nums[mid + 1])) {
                return mid;
            } else if (nums[mid] > nums[mid + 1]) { // mid will never be nums.length - 1
                end = mid;
            } else {
                // nums[mid] < nums[mid + 1]
                start = mid + 1;
            }
        }
        return start;
    }
}

35. Search Insert Position

二刷 06/2022

Version #1 Binary Search

看答案终止条件是 start <= end, 这样start会直接变成比target大的第一个，所以可以直接return start而不需要讨论出界情况

Time O(logN)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search Insert Position.

Memory Usage: 43.7 MB, less than 35.11% of Java online submissions for Search Insert Position.

class Solution {

    public int searchInsert(int[] nums, int target) {

        // Find the first number that larger than or equal to target

        int start = 0, end = nums.length - 1;

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {

                return mid;

            }

            if (nums[mid] < target) {

                start = mid + 1;

            } else {

                end = mid;

            }

        }

        return nums[start] >= target ? start : nums.length;

    }

}

一刷

找第一个比target大的index
如果所有的number都比target小，则要加在最后

100.00 %
class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        // first index larger than target
        // If not exist, return 0
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            // [1,3,5,6]
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start + (nums[start] < target ? 1 : 0);
    }
}

34. Find First and Last Position of Element in Sorted Array

二刷 05/2022

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.

Memory Usage: 47.6 MB, less than 15.92% of Java online submissions for Find First and Last Position of Element in Sorted Array.

class Solution {

    public int[] searchRange(int[] nums, int target) {

        // Do binary search twice

        // 1st time find the starting position of target

        // 2nd time find the ending position of target

        int[] res = new int[]{-1, -1};

        if (nums == null || nums.length == 0) {

            return res;

        }

        res[0] = binarySearch(nums, target, true);

        if (res[0] != -1) {

            res[1] = binarySearch(nums, target, false);

        }

        return res;

    } 

    

    private int binarySearch(int[] nums, int target, boolean isFirst) {

        // Assuming is First is true

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {

                if (isFirst) {

                    end = mid;

                } else {

                    start = mid;

                }

            } else if (nums[mid] < target) {

                start = mid + 1;

            } else {

                end = mid - 1;

            }

        }

        if (nums[start] != target && nums[end] != target) {

            return -1;

        }

        if (isFirst && nums[start] == target || !isFirst && nums[end] != target) {

            return start;

        } else {

            return end;

        }

    }

}

一刷

如果终止条件是 start < end 且 无法 start = mid + 1 (找最后一个符合条件的index时)， 就会infinite loop
所以这里条件必须是start + 1 < end
Stop when they are next to each other

100.00 %

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int[] result = new int[]{-1, -1};
        // Binary Search For 2 times
        // 1-> find first occurance, 2-> find last occurance
        int left = binarySearch(nums, target, true);
        if (nums[left] == target) { // exist
            result[0] = left;
            result[1] = binarySearch(nums, target, false);
        }
        return result;
    }
   
    private int binarySearch(int[] nums, int target, boolean isStart) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            // 5, 7, 7, 8, 8
            int mid = start + (end - start) / 2;
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else { // nums[mid] == target
                if (isStart) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
        }
        int result = start;
        if (isStart && nums[start] == target || !isStart && nums[end] != target) {
            return start;
        } else {
            return end;
        }
    }
}

374. Guess Number Higher or Lower

Binary Search

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1;
        int end = n;
        // start  end
        while (start < end) {
            int mid = start + (end - start) / 2;
            int result = guess(mid);
            if (result == -1) {
                end = mid - 1;
            } else if (result == 1) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return start;
    }
}

278. First Bad Version

二刷 06/2022

Time O(logN)

Space O(1)

Runtime: 14 ms, faster than 97.88% of Java online submissions for First Bad Version.

Memory Usage: 40.3 MB, less than 77.89% of Java online submissions for First Bad Version.

/* 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 start = 1, end = n;

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (super.isBadVersion(mid)) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return start;

    }

}

一刷
Binary Search
O(logn)
99.77 %
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // f  f  t  t  t
        int start = 1;
        int end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

122. Best Time to Buy and Sell Stock II

You may complete as many transactions as you like
So the result is the sum of all profitable transactions.
99.90 %
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int sum = 0;
        int diff = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            diff = prices[i + 1] - prices[i];
            if (diff > 0) {
                sum += diff;
            }
        }
        return sum;
    }
}