Leetcode 1059 Solution

This article provides solution to leetcode question 1059 (missing-element-in-sorted-array)
Categories:
Tags:
Access this page by simply typing in "lcs 1059" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        vector<int> a;
        a.push_back(0);

        int last_gap = 0;

        for (int i = 0; i < nums.size() - 1; i++)
        {
            int curr_gap = nums[i + 1] - nums[i] - 1;
            a.push_back(curr_gap + a[a.size() - 1]);
        }

        int l = 0;
        int r = a.size() - 1;
        k++;

        while (l < r)
        {
            int m = (l + r) / 2;
            if (a[m] >= k)
                r = m;
            else
                l = m + 1;
        }

        if (a[l] < k)
            l++;

        return nums[l - 1] + k - a[l - 1];
    }
};