Search value in sorted sequences

Note that the sorted list we search for result can either be the domain or range.
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

1231. Divide Chocolate

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.
You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.
Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

class Solution:
    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
        def can_divide(target_minimal):
            pieces = 0
            accum = 0
            for amt in sweetness:
                accum += amt
                if accum >= target_minimal:
                    accum = 0
                    pieces += 1
            return pieces >= k + 1
        
        l, h = 0, sum(sweetness) // (k + 1) + 1
        while l < h:
            m = (l + h) // 2
            if not can_divide(m):
                h = m
            else:
                l = m + 1
        return l - 1

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 can_eat_all(m): 
            h = m
        else: 
            l = m + 1
    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 or equal to k. FFFFFFTTTTTTT+ Then we can calculate the k th missing element based off that. ```python def missing_element(A, k): def missing(idx): return A[idx] - A[0] - idx
l, h = 0, len(A)
while l < h:
    m = (l + h) // 2
    if missing(m) >= k:   # i >= m -> missing(m) >= k
        h = m
    else: 
        l = m + 1

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

Peak Finding

  • Binary search applied to unsorted array to find a local peak.
  • This is done by comparing middle point with its adjacent neighbor and cut space in half.

    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]: 
          h = m
      else: 
          l = m + 1
  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]: 
          h = m
      else: 
          l = m + 1
  return l

1901. Find a Peak Element II

A peak element in a 2D grid is an element that is strictly greater than all of its adjacent neighbors to the left, right, top, and bottom. Given a 0-indexed m x n matrix mat where no two adjacent cells are equal, find any peak element mat[i][j] and return the length 2 array [i,j]. You may assume that the entire matrix is surrounded by an outer perimeter with the value -1 in each cell. You must write an algorithm that runs in O(m log(n)) or O(n log(m)) time.

def findPeakGrid(mat):
    l, h = 0, len(mat) - 1
    while l < h:
        m = (l + h) // 2
        if max(mat[m]) >= max(mat[m + 1]):
            h = m
        else:
            l = m + 1
    return [l, mat[l].index(max(mat[l]))]

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:
            h = mid
        else:
            l = mid +1
    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. ```python 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. (TODO: Monotonic Stack?)

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)

Google List

Straight forward