1060 missing elements in sorted array

https://leetcode.com/problems/missing-element-in-sorted-array/

class Solution {
    public int missingElement(int[] nums, int k) {
        int[] cnts = new int[nums.length];
        missingCount(nums, cnts);
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int cnt =cnts[mid];
            if (cnt < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        int cnt = cnts[lo];
        int num = nums[lo] - 1;
        if (cnt < k) {
            return nums[nums.length - 1] + (k - cnt);
        }
        while (cnt > k) {
            cnt--;
            num--;
        }
        return num;
    }
    private void missingCount(int[] nums, int[]cnts) {
        int cnt = 0;
        for (int i = 1; i < nums.length; i++) {
            cnt += nums[i] - nums[i - 1] - 1;
            cnts[i] = cnt;
        }
    }
}

off-by-one is killing me ๐Ÿ˜‘

Last updated