Leet Code 1060. Missing Element in Sorted Array — Explained Python3 Solution
Problem Description Given a sorted array A of unique numbers, find the K -th missing number starting from the leftmost number of the array. Example 1: Input: A = [4,7,9,10] , K = 1 Output: 5 Explanation: The first missing number is 5. Example 2: Input: A = [4,7,9,10] , K = 3 Output: 8 Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8. Solution Seeing the word " sorted " reminds me that there must be some trick to play with. One common thought of mine is binary lookup , which is used for quickly, in O(logN), to locate a specific element. And it turns out similar thoughts applies to this problem as well. Before getting to that, let me explain the brute force way a little bit. First I need to set a counter to count missing number I find as of now, in the beginning, it will be 0 for sure. Then I can certainly iterate the numbers one by one, the moment I get to index i, I will check if A[i] is the last elemen...