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) / 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

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

    @Test
    void givenInputs1_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe120() {
        final int[] startTime = new int[]{1, 2, 3, 3};
        final int[] endTime = new int[]{3, 4, 5, 6};
        final int[] profit = new int[]{50, 10, 40, 70};
        Assertions.assertEquals(120, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(120, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs2_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe150() {
        final int[] startTime = new int[]{1, 2, 3, 4, 6};
        final int[] endTime = new int[]{3, 5, 10, 6, 9};
        final int[] profit = new int[]{20, 20, 100, 70, 60};
        Assertions.assertEquals(150, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(150, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs3_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe6() {
        final int[] startTime = new int[]{1, 1, 1};
        final int[] endTime = new int[]{2, 3, 4};
        final int[] profit = new int[]{5, 6, 4};
        Assertions.assertEquals(6, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(6, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs4_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe6() {
        final int[] startTime = new int[]{4, 3, 1, 2, 4, 8, 3, 3, 3, 9};
        final int[] endTime = new int[]{5, 6, 3, 5, 9, 9, 8, 5, 7, 10};
        final int[] profit = new int[]{9, 9, 5, 12, 10, 11, 10, 4, 14, 7};
        Assertions.assertEquals(37, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(37, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs5_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe6() {
        final int[] startTime = new int[]{3, 5, 3, 7, 4};
        final int[] endTime = new int[]{10, 8, 8, 10, 9};
        final int[] profit = new int[]{10, 8, 10, 9, 9};
        Assertions.assertEquals(10, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(10, jobScheduling2(startTime, endTime, profit));
    }
}

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