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