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 element, if yes, then the missing number is A[i] + (K-counter); if there is a A[i+1], then A[i+1] - A[i] - 1 is the number of missing numbers, for example,  between 4 and 5, there is 5-4-1=0 missing numbers while between 4 and 7, there is 7-4-1=2 missing (which is 5,6). Note that there is actually a clarification to make if [1,2] and K=3, should I return 5 or None. Here I just follow what Leetcode's submission check says.

Now let me roll my sleeves to binary lookup solution. In first iteration of binary lookup, I will get the missing numbers for the first and second half of the input. For example [5,7,9,10,13],  I want to know how many numbers are missing from the first half ([5,7,9]) and second ([9,10,13]). The way to get it is using the right boundry - the left  + 1, for [5,7,9], the expected numbers = 9-5+1=5, that's very true since a complete list  should be [5,6,7,8,9], the atual length is 3, so the missing number is 5-3=2. Now if I'm asked to find the 3rd missing element, I should drop the first half [5,7,9] because in that part there is only 2 missing. And the next step will be looking into the second half [9,10,13] for the first missing element since I need to find the 3rd and the first half already contain the first 2 (which I don't really need to know what are the exact missing elements). Hmm, now I turn the search for the 3rd missing in [5,7,9,10,13] into the search for the 1st missing in [9,10,13].

Repeat the process, I will know there should be 10-9+1=2 elements in [9,10] (which is the actual case so 0 missing in first half) and 13-10+1=4 elements in [10,13] (which is false). So I need to look into  [10,13] for the 1st (1-0 =1) missing element.

Now since there are only 2 elements in [10,13], I will just use the left element plus the missing number to get the missing number which is 10+1=11. This will be the answer!

Before I go ahead to actual code, there are still 2 tricks to mention:

  1. There is a case that the missing number is beyond the provided array. In that condition, there is no need to perform binary look. It's coverd in the brute force way and the same logic should be there in the beginning in the binary lookup solution.  
  2. In above example, I split the input array by using the middle index. In example of [5,7,9,10,13], the middle index is 2 ( (4-0)/2 ). However what if the size of the array is even? Like [5,7,9,10,13,14]? Since (5-0)/2 = 2.5, one may be sure what index should be used to split the array. Actually it doesn't matter. The middle index could be 2 or 3 since I'm just looking for a valid index to split the array. Left half array is slightly larger than right half or vice versa doesn't make an essential difference as long as the index does not cross the border. And the key here is to ruduce the to-be-checked element set from a larger size to (nearly) half and then (nearly) half and ....  

Time & Space Complexity

Similar to binary lookup, each time I break the input size N to half so the time complexity will be O(logN).

In my above code, I use recursive calling which will stack to store information. This takes up extra space and the space is directly related to the calls which is also O(logN). So the space complexity is O(logN) as well.

Python 3 knowledge points

1. Inner (nested) function

https://stackabuse.com/python-nested-functions/

2. Use int() to transfer an float to an integer

Comments

Post a Comment

Popular posts from this blog

Leet Code 84. Largest Rectangle in Histogram — Graphically Explained Python3 Solution

-
Image
  Photo by  Pablo Hermoso  on  Unsplash Problem Description Given  n  non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height =  [2,1,5,6,2,3] . The largest rectangle is shown in the shaded area, which has area =  10  unit. Example: Input: [2,1,5,6,2,3] Output: 10 Solution Obvious Solution The obvious (and brute force) way is to use 2 pointers: left and right. Let left points to index 0 ~ N-1 and then right to left and N-1. For each left and right pair, I can calculate the area[left, right] using (right-left+1) * min(heights[left], heights[left+1],heights[left+2],…,heights[right]). Its time complexity is at least be O(N²). Best Solution (to me) [Credit]  This is described by @ TravellingSalesman  in disucssion area ( https://leetcode.com/problems/largest-rectangle-in-histogram/solution/ ) and here I just try to illustrate it furt
Read more

LeetCode 23. Merge k Sorted Lists— Graphically Explained Python3 Solution

-
Image
  Problem Description You are given an array of  k  linked-lists  lists , each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example: Input: lists = [[1,1,5],[1,3,4],[2,6]] Output: [1,1,1,2,3,4,5,6] Explanation: The linked-lists are: [ 1->1->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->1->2->3->4->5->6 Solution Obvious Solution The obvious (and brute force) way is to navigate ALL list items, save them into an array and then sort. The time complexity is: O(kN + kNLog(kN)) since for for total k Lists (each one with average N elements), I need to visit them all and the quick sort on final array takes kNLog(kN). The space complexity is O(kN) as all values will be saved. Best Solution (to me) Since each list is already sorted, I can definitely leverage that. To start with, let me use this example: To show it more clearer, let me put some twists (showing only the left
Read more