Search value in sorted sequences

Note that the sorted list we search for result can either be the input list or the sequence of candidates. We will need to find the function that gives us the direction.

278. First Bad Version

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

Thought process:

  • Linear scan is \(O(N)\).
  • The function is a given API call, which the result for a sequential inputs are sroted: FFFFTTTT.
  • Use binary search to have \(logN\) search time.
def first_bad_version(n):
    l, h = 1, n
    while l < h:
        m = (l + h) // 2
        if isBadVersion(m): h = m
        else: l = m + 1
    return l

852. Peak Index in a Mountain Array

Let’s call an array A a mountain if the following properties hold:

  • A.length >= 3
  • There exists some 0 < i < A.length - 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1].

*Thought process: *

  • The search space is 0, len(A).
  • Sequential less than comparison results are sorted.
A[i - 2] < A[i - 1] < A[i] > A[i + 1] > A[i + 2]
   A[m]  < A[m + 1]                                 --> T
              A[m]  < A[m + 1]                      --> T
                      A[m]  < A[m + 1]              --> F
                                A[m]  < A[m + 1]    --> F
def peak_index_in_mountain_array(A):
    l, h = 0, len(A)
    while l < h:
        m = (l + h) // 2
        if A[m] < A[m + 1]: l = m + 1
        else: h = m
    return l

162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Thought process:

  • This is exactly the same question as the one above.
def find_peak_element(nums):
    l, h = 0, len(nums) - 1
    while l < h:
        m = (l + h) // 2
        if nums[m] < nums[m + 1]: l = m + 1
        else: h = m
    return l

875. Koko Eating Bananas

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Thought process:

  • Search space is 1, size(max pile), a tighter lower bound can be ceil(size(min_pile))
  • The function is f(x) = # hour it needs to eat all bananas < H.
  • The function space is FFFTTT.
import math

def min_eating_speed(piles, H):
    def can_eat_all(speed):
        return sum(math.ceil(num_bananas / speed) for num_bananas in piles) <= H

    l, h = math.ceil(min(piles) / H), max(piles)
    while l < h:
        m = (l + h) // 2
        if not can_eat_all(m): l = m + 1
        else: h = m
    return l

1060. Missing Element in Sorted Array

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

  • The actual search space is A[0], A[n - 1].
  • Directly search for the value is a bit difficult, we instead search for a quantity that have a fomularic relationship with the target.
  • Notice number of missing integers before idx i is A[i] - A[0] - i.
  • let A == [4,7,9,10], A[1] - A[0] - 1 == 7 - 4 - 1 == 2 and the missing integers before 7 are 5 and 6.
  • Use binary search to find smallest i such that number of missing intgers before A[i] is greater than k. FFFTTTTT
  • Then we can calculate the k th missing element based off that.
def missing_element(A, k):
    def missing(idx): return A[idx] - A[0] - idx

    n = len(A)
    if k > missing(n - 1):  return A[-1] + k - missing(n - 1)

    l, h = 0, n - 1
    while l < h:
        m = (l + h) // 2
        if missing(m) < k: l = m + 1
        else: h = m

    return A[l - 1] + k - missing(l - 1)

Search in Rotated Sorted Array

153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Thought process:

  • Compare the mid point with the high point.
  • nums[m] < nums[h] means that from m to h, it is sorted, thus the minimal value can only be to the left of it.
  • nums[m] > nums[h] means the minimal value must in between m and h. Think of the case m -> 7, 0, 1 <- h
def find_min(nums):
    l, h = 0, len(nums) - 1
    while l < h:
        m = (l + h) // 2
        if nums[m] < nums[h]: h = m
        else: l = m + 1
    return nums[l]

154. Find Minimum in Rotated Sorted Array II

Same as above, but the array may contain duplicates.

Thought process:

  • Add one line to handle the case of duplicates, decrement the right pointer.
def find_min(nums):
    l, h = 0, len(nums)-1
    while l < h:
        m = (l + h) // 2
        if nums[m] == nums[h]: l -= 1
        elif nums[m] < nums[h]: h = m
        else: l = m + 1
    return nums[l]

33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

You are given a target value to search. If found in the array return its index, otherwise return -1.

Thought process:

  • If mid pivot number is larger than the left number, the left half is sorted, right half is rotated sorted.
    • Numbers in the rotated sorted part is eithe larger than the max from left or smaller than the min from left.
    • Thus, if the target is between left and mid numbers, it has to be in the left half.
    • Otherwise it has to be in the right half.
  • Otherwise, the left half is rotated sorted, the right half is sorted
    • Use logic similar to above.
  /
 /
/
    /
   /
def search(nums, target):
    l, h = 0, len(nums) - 1

    while l <= h:
        mid = (l + h) // 2
        if nums[mid] == target: return mid

        if nums[mid] >= nums[l]:
            if nums[l] <= target < nums[mid]:
                h = mid - 1
            else:
                l = mid + 1
        else:
            if nums[mid] < target <= nums[h]:
                l = mid + 1
            else:
                h = mid - 1
    return -1

81. Search in Rotated Sorted Array II

Same as above, difference is return True or False, and there can be duplicated values in the array.

   /
__/  ______
    /
l         h

Thought process:

  • Duplicates will hurts only when it happens as illustrated above.
  • Simple fix is to add one line to move either left or right pointer to break it.
def search(nums, target):
    l, h = 0, len(nums) - 1

    while l <= h:
        while l < h and nums[l] == nums[h]: l += 1  # only difference

        mid = (l + h) // 2
        if nums[mid] == target: return True

        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]:
                h = mid - 1
            else:
                l = mid + 1
        else:
            if nums[mid] < target <= nums[h]:
                l = mid + 1
            else:
                h = mid - 1
    return False

Not so obvious ones

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Thought process:

  • To find the middle elements of the merged array is equal to find a partition of the two arrays, such that, the left subarrys merged is equal in size to the right subarrys merges.
  • For partitions like these, we want one with the minimal value from the two right subarrays to be bigger than the maximuum value from the two left subarrays.
  • If we can find such a partition, the median can be calculated with the four elements on the boundary.
def find_median_from_two_sorted_arrays(nums1, nums2):
    if len(nums2) < len(nums1):
        nums1, nums2 = nums2, nums1

    l1, l2 = len(nums1), len(nums2)
    half_size = (l1 + l2 + 1) // 2

    l, h = 0, len(nums1)
    is_even = not ((l1 + l2) % 2)

    while l <= h:
        p1 = (l + h) // 2
        p2 = half_size - p1

        max_left_1 = float("-inf") if p1 == 0 else nums1[p1 - 1]
        min_right_1 = float("inf") if p1 == l1 else nums1[p1]
        max_left_2 = float("-inf") if p2 == 0 else nums2[p2 - 1]
        min_right_2 = float("inf") if p2 == l2 else nums2[p2]

        max_left, min_right = max(max_left_1, max_left_2), min(min_right_1, min_right_2)

        if max_left <= min_right:
            return (max_left + min_right) / 2 if is_even else max_left
        elif max_left_1 > min_right_2: h = p1 - 1
        elif max_left_2 > min_right_1: l = p1 + 1

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].

Thought process:

  • Use binary search twice, once for the left most, once for the right most.
from bisect import bisect_left, bisect_right

def search_range(nums, target):
    left = bisect_left(nums, target, 0, len(nums) - 1)
    if left == len(nums) or nums[left] != target: return [-1, -1]
    right = bisect_right(nums, target, left, len(nums) - 1)
    return [left, right] if nums[right] == target else [left, right - 1]

378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

*Thought process: *

  • The search space is the integers between matrix[0][0] and matrix[-1][-1]
  • The function f(x) = {# of elements in matrix smaller than x} < k. FFFFFFTTTTTTT
  • For calculating the above function, we can apply binary on each row.
from bisect import bisect_right

def kth_smallest(matrix, k):
    l, h = matrix[0][0], matrix[-1][-1]
    while l < h:
        mid = (l + h) // 2
        if sum(bisect_right(row, mid) for row in matrix) < k:
            l = mid +1
        else:
            h = mid
    return l

Combination with other techniques

658. Find K Closest Elements

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Thought process:

  • Find the target value via binary search.
  • Shrink the length == 2k window around the target with two pointers.
from bisect import bisect_left
def find_closest_elements(arr, k, x):
    if x <= arr[0]: return arr[:k]
    if x >= arr[-1]: return arr[-k:]
    n = len(arr)

    loc = bisect_left(arr, x)
    l, h = max(0, loc - k), min(n - 1, loc + k)
    while h - l + 1 > k:
        if l < 0 or x - arr[l] <= arr[h] - x: h -= 1
        elif h > n - 1 or x - arr[l] > arr[h] - x: l += 1

    return arr[l: h + 1]

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Thought process:

  • It a famous problem in CS, here for more detail.
def length_of_longest_increasing_subsequence(nums):
    n = len(nums)
    p = [0] * n
    m = [0] * (n + 1)
    max_l = 0
    for i, num in enumerate(nums):
        l, h = 1, max_l
        while l <= h:
            mid = (l + h) // 2
            if nums[m[mid]] < num:
                l = mid + 1
            else:
                h = mid - 1

        p[i] = m[l - 1]
        m[l] = i
        max_l = max(max_l, l)

    s = [None] * max_l
    k = m[max_l]
    for i in range(max_l):
        s[~i] = nums[k]
        k = p[k]
    return max_l

A shorter solution is as follows, it only returns the length, but not able to reconstruct the full optimal sequence. The tails[i] here is the tail element of the most recent length i increasing subsequence.

from bisect import bisect_left

def length_of_longest_increasing_subsequence(nums):
    tails = []
    for num in nums:
        i = bisect_left(tails, num)
        if i == len(tails):
            tails.append(num)
        else:
            tails[i] = num
    return len(tails)