Binary Search

21. 704. Binary Search

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}

22. 278. First Bad Version

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        int ans;
        while(left <= right) {
            // note we need to prevent `signed integer overflow`
            long mid = left + (right - left)/2;
            if (isBadVersion(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};

23. Search in Rotated Sorted Array

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } if (nums[mid] >= nums[left]) {
                if (target <= nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target >= nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

24. 981. Time Based Key-Value Store

class TimeMap {
public:
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        map[key].emplace_back(timestamp, value);
    }
    
    string get(string key, int timestamp) {
        if (map.find(key) == map.end()) {
            return "";
        }
        int low = 0;
        int high = map[key].size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (map[key][mid].first < timestamp) {
                low = mid + 1;
            } else if (map[key][mid].first > timestamp) {
                high = mid - 1;
            } else {
                return map[key][mid].second;
            }
        }

        if (high >= 0) {
            return map[key][high].second;
        } else {
            return "";
        }
    }
private:
    unordered_map<string, vector<pair<int, string>>> map;
};

25. 1235. Maximum Profit in Job Scheduling

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs;
        for (int i = 0; i < n; ++i) {
            jobs.push_back({endTime[i], startTime[i], profit[i]});
        }
        sort(jobs.begin(), jobs.end());
        map<int, int> dp = {{0, 0}};
        for (auto& job : jobs) {
            int cur = prev(dp.upper_bound(job[1]))->second + job[2];
            if (cur > dp.rbegin()->second)
                dp[job[0]] = cur;
        }
        return dp.rbegin()->second;
    }
};

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        const auto n = startTime.size();
        if (n == 0) {
            return 0;
        }

        std::vector<std::tuple<int, int, int>> jobs;
        jobs.reserve(n);
        for (int i = 0; i < n; i++) {
            jobs.emplace_back(startTime[i], endTime[i], profit[i]);
        }

        std::sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b) {
            return std::get<0>(a) < std::get<0>(b);
        });

        std::vector<int> cache(n, -1);
        std::function<int(int)> dfs;
        dfs = [&](const int i) -> int {
            if (i >= n) {
                return 0;
            }
            if (cache[i] != -1) {
                return cache[i];
            }

            const auto job = jobs[i];
            const auto end_i = std::get<1>(job);
            const auto it = std::lower_bound(jobs.begin() + i + 1, jobs.end(), end_i, [](const auto& element, const auto target) {
                return std::get<0>(element) < target;
            });
            const auto j = it - jobs.begin();
            const auto take = get<2>(job) + dfs(j);
            const auto skip = dfs(i+1);
            return cache[i] = std::max(take, skip);
        };
        return dfs(0);
    }
};

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;

import static java.lang.Math.max;

class JobScheduling {
    // https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/409009/java-c-python-dp-solution/
    public int jobScheduling(final int[] startTime, final int[] endTime, final int[] profit) {
        final int n = profit.length;
        final int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, Comparator.comparingInt(e -> e[1]));
        // key is the end time, value is the maximum profit for the end time
        final TreeMap<Integer, Integer> dp = new TreeMap<>();
        dp.put(0, 0);
        for (final int[] job : jobs) {
            final int cur = dp.floorEntry(job[0]).getValue() + job[2];
            if (cur > dp.lastEntry().getValue()) {
                dp.put(job[1], cur);
            }
        }
        return dp.lastEntry().getValue();
    }

    // https://www.youtube.com/watch?v=0C7re8lam7M
    public int jobScheduling2(final int[] startTime, final int[] endTime, final int[] profit) {
        final int n = profit.length;
        final int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, Comparator.comparingInt(e -> e[1]));

        final List<int[]> dp = new ArrayList<>(); // {endTime, profit}
        int ret = 0;
        dp.add(new int[]{0, 0});
        for (final int[] job : jobs) {
            int cur = ret;
            //  mimic the upper_bound in cpp
            int ip = upperBound(dp, new int[]{job[0], Integer.MAX_VALUE});
            ip--;
            cur = max(cur, dp.get(ip)[1] + job[2]);
            dp.add(new int[]{job[1], cur});
            ret = max(ret, cur);
        }
        return ret;
    }

    // note it will exceed the time limit in leetcode
    private int upperBound(final List<int[]> dp, final int[] target) {
        for (int i = 0; i < dp.size(); i++) {
            if (dp.get(i)[0] > target[0]) {
                return i;
            }
        }
        return dp.size();
    }
}

26. 733. Flood Fill

// https://leetcode.com/problems/flood-fill/solutions/4745988/easy-dfs-solution-c/
class Solution {
public:
    Solution() : directions{-1, 0, 1, 0, -1} {}

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        vector<vector<int>> ans = image; // equivalent to the visited marker
        dfs(sr, sc, color, image[sr][sc], ans, image);
        //dfs(sr, sc, color, image[sr][sc], ans, image, this->directions);
        return ans;
    }

    void dfs(int row, int col, int color, int initColor, vector<vector<int>>& ans, vector<vector<int>>& image) {
        ans[row][col] = color;
        int m = image.size();
        int n = image[0].size();
        for (int i=0; i<4; i++) {
            int nRow = row + this->directions[i]; 
            int nCol = col + this->directions[i+1];
            if (nRow >= 0 && nRow < m && nCol >= 0 && nCol < n && image[nRow][nCol] == initColor && ans[nRow][nCol] != color) {
                dfs(nRow, nCol, color, initColor, ans, image);
            }
        }
    }

    // just to demo the usage of reference to an array: 
    // https://stackoverflow.com/questions/32732957/syntax-for-returning-an-array-reference-in-c
    void dfs(int row, int col, int color, int initColor, vector<vector<int>>& ans, vector<vector<int>>& image, const int (&dirs)[5]) {
        ans[row][col] = color;
        int m = image.size();
        int n = image[0].size();
        for (int i=0; i<4; i++) {
            int nRow = row + dirs[i]; 
            int nCol = col + dirs[i+1];
            if (nRow >= 0 && nRow < m && nCol >= 0 && nCol < n && image[nRow][nCol] == initColor && ans[nRow][nCol] != color) {
                dfs(nRow, nCol, color, initColor, ans, image, dirs);
            }
        }
    }
    
    const int (&getDirections() const)[3] { // Getter function to return const reference to the array
        return directions;
    }
private: 
    const int directions[5];
};

Note that for the primitive array, e.g., int a[3],

1. the a is a const pointer to the first element in the array, which means a = b is not allow

2. it's allocated in the stack, as opposed to const int b[] = new int[3]

3. to free the memory of the array b, and the objects contained in b, delete [] b should be used

4. note that in char name[] = "hello", the name is an array of 6 chars, including the \0 as the null terminator

4. Median of Two Sorted Arrays

// time complexity: O(m+n), space complexity: O(1)
class Solution {
    int p1 = 0, p2 = 0;
public:
    int getMin(vector<int>& nums1, vector<int>& nums2) {
        if (p1 < nums1.size() && p2 < nums2.size()) {
            return nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
        } else if (p1 < nums1.size()) {
            return nums1[p1++];
        } else if (p2 < nums2.size()) {
            return nums2[p2++];
        } else {
            return -1;
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size();
        int size2 = nums2.size();
        if ((size1 + size2) % 2 == 0) {
            for (int i = 0; i < (size1 + size2)/2-1; i++) {
                int _ = getMin(nums1, nums2);
            }
            return (double)(getMin(nums1, nums2) + getMin(nums1, nums2)) / 2;
        } else {
            for (int i = 0; i < (size1 + size2)/2; i++) {
                int _ = getMin(nums1, nums2);
            }
            return (double)getMin(nums1, nums2);
        }
    }
};

// time complexity: O(logm + logn), space complexity: O(logm +logn)
class Solution {
public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int na = int(nums1.size());
        int nb = int(nums2.size());
        int n = na + nb;
        if (n % 2) {
            return solve(nums1, nums2, n/2, 0, na-1, 0, nb-1);
        } else {
            return 1.0 * (solve(nums1, nums2, n/2-1, 0, na-1, 0, nb-1) + solve(nums1, nums2, n/2, 0, na-1, 0, nb-1)) / 2;
        }
        
    }

    int solve(vector<int>& a, vector<int>& b, int k, int aStart, int aEnd, int bStart, int bEnd) {
        if (aEnd < aStart) {
            return b[k - aStart];
        }
        if (bEnd < bStart) {
            return a[k - bStart];
        }
        int aIndex = (aStart + aEnd) / 2, bIndex = (bStart + bEnd) / 2;
        int aValue = a[aIndex], bValue = b[bIndex];

        // if k is in the right half of a + b, remove the smaller left half
        if (aIndex + bIndex < k) {
            if (aValue < bValue) {
                return solve(a, b, k, aIndex + 1, aEnd, bStart, bEnd);
            } else {
                return solve(a, b, k, aStart, aEnd, bIndex + 1, bEnd);
            }
        } 
        // otherwise, remove the larger right half
        else {
            if (aValue < bValue) {
                return solve(a, b, k, aStart, aEnd, bStart, bIndex - 1);
            } else {
                return solve(a, b, k, aStart, aIndex - 1, bStart, bEnd);
            }
        }
    }
};

// time complexity: O(log(min(m, n))), space complexity: O(1)
class Solution {
public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.size(), n = nums2.size();
        int left = 0, right = m;

        while (left <= right) {
            int partitionA = (left + right) / 2;
            int partitionB = (m + n + 1) / 2 - partitionA;

            int maxLeftA = (partitionA == 0) ? INT_MIN : nums1[partitionA - 1];
            int minRightA = (partitionA == m) ? INT_MAX : nums1[partitionA];
            int maxLeftB = (partitionB == 0) ? INT_MIN : nums2[partitionB - 1];
            int minRightB = (partitionB == n) ? INT_MAX : nums2[partitionB];

            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
                if ((m + n) % 2) {
                    return max(maxLeftA, maxLeftB);
                } else {
                    return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2.0;
                }
            } else if (maxLeftA > minRightB) {
                right = partitionA - 1;
            } else {
                left = partitionA + 1;
            }
        }

        return 0.0;
    }
};