[Python 10 lines] Binary Search with thought process when being asked during interviews
Binary Search\nLet\'s simply the problem first. What if k is large enough such that there is only one pair for each i to construct the sequence? We just need to
### Binary Search\nLet\'s simply the problem first. What if `k` is large enough such that there is only one pair for each `i` to construct the sequence? We just need to check each pair to see if it\'s valid or not, and increase the final result by 1 if the pair is invalid.\n\nThen let\'s decrement `k` , the number of integers in each sequence is increased, meaning there is an index `j` exists such that `nums[j - k] <= nums[j] <= nums[j + k]`.   More similarly with smaller `k`, there are more integers in the sequence.  So we can check each independent sequence to get the result, and then sum up of results for each sequence.\n\nNow the problem is transfered to given a sequence, how many operations we can use to make it increasing? Does it look familar? \n\nNote we can make the sequence valid by changing any invalid integer to be as same as previous integer, for example `[5,2,3,2] => [5,5,5,5]`. So we can just get the increasing sequence and change all of the rest to be equal to any valid integers. \n\nFinally, this problem is converted to finding the longest non decreasing subsequence for each  group.\n\n```python\ndef kIncreasing(self, arr: List[int], k: int) -> int:\n\tdef helper(nums):\n\t\tlps = []\n\t\tfor num in nums:\n\t\t\tindex = bisect.bisect(lps, num)\n\t\t\tif index < len(lps):\n\t\t\t\tlps[index] = num\n\t\t\telse:     \n\t\t\t\tlps.append(num)\n\t\treturn len(nums) - len(lps)\n\treturn sum(helper([arr[j] for j in range(i, len(arr), k)]) for i in range(k))\n```\n\n*Time Complexity*= **O(NlgN)**\n*Space Complexity* = **O(N)**\n
['Binary Tree']