Order, Search and Range Queries

Data Structures

  1. Segment Tree:

  • Sum, min, max, and custom range queries.

  • Lazy propagation for range updates.

  • Variants like mergeable segment trees.

  • Sample implementation

    Expand Code
      1from random import randint
  2from collections import Counter
  3
  4class RangeSumTree:
  5  def __init__(self, nums: List[int]):
  6    def build():
  7      for i, val in enumerate(nums):
  8        self.update_impl(1, 0, self.n-1, i, val)
  9
 10    self.n = len(nums)
 11    self.tree = [0] * 4 * self.n
 12    build()
 13
 14  def update_impl(self, root, t_left, t_right, index, val):
 15    """
 16    Updates the leaf value at index and then subsequently intermeidate tree values.
 17
 18    Params:
 19      root: root index of the tree
 20      t_left: left index in the original array spanned by the current subtree
 21      t_right: right index in the original array spanned by the current subtree
 22      index: index in the array for update
 23      val: value to be updated at index
 24    Returns:
 25      None
 26    """
 27    if t_left > t_right:
 28      return
 29
 30    if t_left == t_right:
 31      self.tree[root] = val
 32      return
 33
 34    t_mid = (t_left + t_right) // 2
 35    
 36    left_child = self.left_child_index(root)
 37    right_child = self.right_child_index(root)
 38
 39    if index <= t_mid:
 40      self.update_impl(left_child, t_left, t_mid, index, val)
 41    else:
 42      self.update_impl(right_child, t_mid + 1, t_right, index, val)
 43    
 44    self.tree[root] = self.tree[left_child] + self.tree[right_child]
 45
 46  def left_child_index(self, root):
 47    return root * 2
 48
 49  def right_child_index(self, root):
 50    return root * 2 + 1
 51
 52  def update(self, index: int, val: int) -> None:
 53    self.update_impl(1, 0, self.n-1, index, val)
 54
 55  def query(self, root, t_left, t_right, left, right):
 56    """
 57    Returns the range sum in the original array between left and right indices (both included)
 58
 59    Params:
 60      root: root index of the tree
 61      t_left: left index in the original array spanned by the current subtree
 62      t_right: right index in the original array spanned by the current subtree
 63      left: left index of the range in the array
 64      right: right index of the range in the array
 65    Returns:
 66      Sum of the numbers within range [left, right]
 67    """
 68    if t_left > right or t_right < left:
 69      return 0
 70    
 71    if t_left == left and t_right == right:
 72      return self.tree[root]
 73    
 74    t_mid = (t_left + t_right) // 2
 75    left_child = self.left_child_index(root)
 76    right_child = self.right_child_index(root)
 77
 78    if right <= t_mid:
 79      return self.query(left_child, t_left, t_mid, left, right)
 80    if t_mid < left:
 81      return self.query(right_child, t_mid + 1, t_right, left, right)
 82    else:
 83      return self.query(left_child, t_left, t_mid, left, t_mid) + self.query(right_child, t_mid + 1, t_right, t_mid + 1, right)
 84
 85  def sumRange(self, left: int, right: int) -> int:
 86    return self.query(1, 0, self.n-1, left, right)
 87
 88"""
 89The following is a more generic version of segment tree to be used for multiple range query tasks.
 90"""
 91class SegmentTree:
 92  def __init__(self, nums, combine):
 93    def build(root_index, range_left, range_right):
 94      nonlocal nums
 95      if range_left > range_right:
 96        return
 97      if range_left == range_right:
 98        self.tree[root_index] = nums[range_left]
 99        return
100      range_mid = (range_left + range_right) // 2
101      left_index, right_index = 2 * root_index, 2 * root_index + 1
102      build(left_index, range_left, range_mid)
103      build(right_index, range_mid + 1, range_right)
104      self.tree[root_index] = self.combine(self.tree[left_index], self.tree[right_index])
105
106    self.n = len(nums)
107    self.tree = [0] * 4 * self.n
108    self.combine = combine
109    build(1, 0, self.n-1)
110
111  def update(self, index: int, val: int) -> None:
112    def impl(root_index, range_left, range_right, insert_index, val):
113      if range_left > range_right:
114        return
115      if range_left == range_right:
116        self.tree[root_index] = val
117        return
118      range_mid = (range_left + range_right) // 2
119      left_index, right_index = 2 * root_index, 2 * root_index + 1
120      if insert_index <= range_mid:
121        impl(left_index, range_left, range_mid, insert_index, val)
122      else:
123        impl(right_index, range_mid + 1, range_right, insert_index, val)
124      self.tree[root_index] = self.combine(self.tree[left_index], self.tree[right_index])
125    
126    impl(1, 0, self.n-1, index, val)
127
128  def sumRange(self, left: int, right: int) -> int:
129    def impl(root_index, range_left, range_right, left, right):
130      if range_left > range_right:
131        return 0
132      if range_left == left and range_right == right:
133        return self.tree[root_index]
134      range_mid = (range_left + range_right) // 2
135      left_index, right_index = 2 * root_index, 2 * root_index + 1
136      if right <= range_mid:
137        return impl(left_index, range_left, range_mid, left, right)
138      elif range_mid < left:
139        return impl(right_index, range_mid+1, range_right, left, right)
140      return impl(left_index, range_left, range_mid, left, range_mid) + impl(right_index, range_mid + 1, range_right, range_mid + 1, right)
141    return impl(1, 0, self.n-1, left, right)
142
143class RangeSum(SegmentTree):
144    def __init__(self, arr):
145        super().__init__(arr=arr, combine=lambda x,y: x+y)
146
147class RangeMin(SegmentTree):
148    def __init__(self, arr):
149        super().__init__(arr=arr, combine=lambda x,y: min(x, y))
150
151class RangeFrequency(SegmentTree):
152    def __init__(self, arr):
153        counts = [(x,1) for x in arr]
154        def combine(x, y):
155            if x[0] < y[0]:
156                return x
157            if x[0] > y[0]:
158                return y
159            return (x[0], x[1]+y[1])
160        super().__init__(arr=counts, combine=combine)
161
162class RangeOrderStatistics(SegmentTree):
163    def __init__(self, arr):
164        counts = [1 if x == 0 else 0 for x in arr]
165        super().__init__(arr=counts, combine=lambda x,y: x+y)
166    def find_kth_idx(self, k):
167        def impl(i, tl, tr, k):
168            if k > self.tree[i]:
169                return -1
170            if tl == tr:
171                return tl
172            tm = tl+(tr-tl)//2
173            if k <= self.tree[2*i]:
174                return impl(2*i, tl, tm, k)
175            else:
176                return impl(2*i+1, tm+1, tr, k-self.tree[2*i])
177        return impl(1, 0, self.n-1, k)

  1. Fenwick Tree (Binary Indexed Tree):

  • Point updates and prefix/range queries.

  • Multidimensional Fenwick Trees.

  • Sample implementation

    Expand Code
     1class BinaryIndexedTree:
 2
 3  def __init__(self, nums: List[int]):
 4    def build():
 5      for i in range(self.n):
 6        self.add(i, self.nums[i])
 7
 8    self.n = len(nums)
 9    self.nums = nums
10    self.bit = [0]*self.n
11    build()
12  
13  def nextIndex(self, index):
14    return index | (index + 1)
15
16  def prevIndex(self, index):
17    return (index & (index + 1)) - 1
18  
19  def add(self, index, delta):
20    curr_index = index
21    while curr_index < self.n:
22      self.bit[curr_index] += delta
23      curr_index = self.nextIndex(curr_index)
24  
25  def sum(self, right):
26    res = 0
27    curr_index = right
28    while curr_index >= 0:
29      res += self.bit[curr_index]
30      curr_index = self.prevIndex(curr_index)
31    return res
32
33  def update(self, index: int, val: int) -> None:
34    delta = val - self.nums[index]
35    self.nums[index] = val
36    self.add(index, delta)
37
38  def sumRange(self, left: int, right: int) -> int:
39    return self.sum(right) - self.sum(left-1)

  • 2D: Sample implementation

    Expand Code
     1from random import shuffle
 2from typing import List
 3
 4class BinaryIndexedTree2D:
 5
 6  def __init__(self, matrix: List[List[int]]):
 7    def build():
 8      for i in range(self.m):
 9        for j in range(self.n):
10          self.add(i, j, self.matrix[i][j])
11
12    self.m, self.n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
13    self.matrix = matrix
14    self.bit = [[0] * self.n for _ in range(self.m)]
15    build()
16    print(self.bit)
17  
18  def nextIndex(self, index):
19    return index | (index + 1)
20  
21  def prevIndex(self, index):
22    return (index & (index + 1)) - 1
23  
24  def add(self, rowIndex, colIndex, delta):
25    i = rowIndex
26    while i < self.m:
27      j = colIndex
28      while j < self.n:
29        self.bit[i][j] += delta
30        j = self.nextIndex(j)
31      i = self.nextIndex(i)
32
33  def sum(self, lastRowIndex, lastColIndex):
34    res = 0
35    i = lastRowIndex
36    while i >= 0:
37      j = lastColIndex
38      while j >= 0:
39        res += self.bit[i][j]
40        j = self.prevIndex(j)
41      i = self.prevIndex(i)
42    return res
43
44  def update(self, row: int, col: int, val: int) -> None:
45    delta = val - self.matrix[row][col]
46    self.matrix[row][col] = val
47    self.add(row, col, delta)
48
49  def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
50    topLeft = self.sum(row1-1, col1-1)
51    topRight = self.sum(row1-1, col2) - topLeft
52    botLeft = self.sum(row2, col1-1) - topLeft
53    botRight = self.sum(row2, col2) - topLeft - topRight - botLeft
54    return botRight

  1. Sparse Table:

  • Efficient for immutable data (static range queries like min, max, or GCD).

  1. Order Statistics Tree (Augmented BST or Fenwick Tree with Order Statistics):

  • Find kth smallest element.

  • Count of elements less than or greater than a given value.

  • Fundamental tree algorithms

    Expand Code
      1from typing import Optional
  2from random import shuffle
  3
  4class TreeNode:
  5    def __init__(self, val=0, left=None, right=None):
  6        self.val = val
  7        self.left = left
  8        self.right = right
  9    def __repr__(self):
 10        return f'TreeNode(val={self.val}),[left={self.left}],[right={self.right}]'
 11
 12class BST:
 13    def __init__(self):
 14        self.root = None
 15
 16    def find(self, val:int) -> Optional[TreeNode]:
 17        def find_impl(root, val):
 18            if root is None: return None
 19            if root.val == val: return root
 20            return find_impl(root.left, val) if val < root.val else find_impl(root.right, val)
 21        return find_impl(self.root, val)
 22
 23    def min(self) -> Optional[TreeNode]:
 24        def min_impl(root):
 25            if root is None: return None
 26            if root.left is None and root.right is None: return root
 27            return min_impl(root.left)
 28        return min_impl(self.root)
 29
 30    def max(self) -> Optional[TreeNode]:
 31        def max_impl(root):
 32            if root is None: return None
 33            if root.left is None and root.right is None: return root
 34            return max_impl(root.right)
 35        return max_impl(self.root)
 36    
 37    def remove(self, val:int):
 38        print(f'removing {val}')
 39        def remove_impl(root, val):
 40            if root is None:
 41                return None
 42            if val < root.val:
 43                root.left = remove_impl(root.left, val)
 44            elif root.val < val:
 45                root.right = remove_impl(root.right, val)
 46            else:
 47                if root.right is None:
 48                    return root.left
 49                prev, node = root.right, root.right.left
 50                if node is None:
 51                    prev.left = root.left
 52                    root = prev
 53                else:
 54                    while node.left is not None:
 55                        prev = node
 56                        node = node.left
 57                    prev.left = node.right
 58                    node.right = root.right
 59                    node.left = root.left
 60                    root = node
 61            return root
 62        self.root = remove_impl(self.root, val)
 63        return self.root
 64
 65    def add(self, val:int):
 66        def add_impl(root, val):
 67            if root is None:
 68                return TreeNode(val)
 69            if val < root.val:
 70                root.left = add_impl(root.left, val)
 71            elif root.val < val:
 72                root.right = add_impl(root.right, val)
 73            return root
 74        return add_impl(self.root, val)
 75
 76def test1():
 77    root = TreeNode(5)
 78    root.left = TreeNode(2)
 79    root.left.left = TreeNode(1)
 80    root.right = TreeNode(7)
 81    root.right.left = TreeNode(6)
 82    root.right.right = TreeNode(8)
 83
 84    bst = BST()
 85    bst.root = root
 86    print(f'min={bst.min()}, max={bst.max()}')
 87
 88    for i in range(10):
 89        if bst.find(i) is None:
 90            bst.add(i)
 91        print(f'min={bst.min()}, max={bst.max()},bst={bst.find(i)}')
 92
 93    values = list(range(10))
 94    shuffle(values)
 95    for i in values:
 96        bst.remove(i)
 97        print(f'bst={bst.root}')
 98
 99if __name__ == '__main__':
100    test1()

  • Check if a tree is a valid BST

    Expand Code
    1def isValidBST(self, root: Optional[TreeNode]) -> bool:
2        def impl(root, l, r):
3            if root is None: 
4                return True
5            if root.val < l or root.val > r:
6                return False
7            return impl(root.left, l, root.val-1) and impl(root.right, root.val+1, r)
8        return impl(root, float('-inf'), float('inf'))

  • Tree traversals with stack

    Expand Code
     1def inorder(root):
 2    res, stack = [], []
 3    while root or stack:
 4        while root:
 5            stack.append(root)
 6            root = root.left
 7        root = stack.pop()
 8        res.append(root.val)
 9        root = root.right
10    return res

  1. RMQ (Range Minimum Query):

  • Hybrid solutions combining segment tree and sparse table for efficiency.

  1. Wavelet Tree:

  • Handles range frequency queries and range kth order statistics.

  1. Mo’s Algorithm:

  • Square-root decomposition for offline range queries.

  1. Merge Sort Tree:

  • Efficient for range queries involving sorted data.

  1. Interval Tree and KD-Tree:

  • For multidimensional range queries.

  1. Monotonic Stack/Queue:

  • Span porblems in static data.

  1. Augmented Trie:

  • For string search.

  • Example Problem: Design Search Autocomplete System with HitCount

    Expand Code
     1class TrieNode:
 2  def __init__(self):
 3    self.children = {}
 4    self.sentences = defaultdict(int)
 5
 6class AutocompleteSystem:
 7
 8  def __init__(self, sentences: List[str], times: List[int]):        
 9    self.root = TrieNode()
10    self.curr_node = self.root
11    self.current_sentence = []
12    self.build(sentences, times)
13
14  def add_sentence(self, sentence, count):
15    """ adds a sentence to the trie and increases the count as specified by the parameter """
16    node = self.root
17    for c in sentence:
18      if c not in node.children:
19        node.children[c] = TrieNode()
20      node = node.children[c]
21      node.sentences[sentence] += count
22
23  def build(self, sentences, times):
24    for i, sentence in enumerate(sentences):
25      self.add_sentence(sentence, times[i])
26
27  def input(self, c: str) -> List[str]:
28    # print(f'input={c}')
29    if c == '#':
30      sentence = ''.join(self.current_sentence)
31      self.add_sentence(sentence, 1)
32      self.curr_node = self.root
33      self.current_sentence = []
34      return []
35    else:
36      self.current_sentence.append(c)
37      if c not in self.curr_node.children:
38        self.curr_node.children[c] = TrieNode()
39      self.curr_node = self.curr_node.children[c]
40      # print(f'sentences={self.curr_node.sentences}')
41      sorted_sentences = sorted(self.curr_node.sentences.keys(), key=lambda k:(-self.curr_node.sentences[k], k))
42      # print(sorted_sentences)
43      return sorted_sentences[:3]
44
45  # Your AutocompleteSystem object will be instantiated and called as such:
46  # obj = AutocompleteSystem(sentences, times)
47  # param_1 = obj.input(c)

Algorithms

  1. Binary search

  1. Define search space

  2. Define condition which specifies a contiguous range in that search space touching either ends.

  3. Decide whether to find the left boundary of that space or right.

  4. Choose whether to search for max from left or min from right.

Expand Code
 1def search_right_for_min():
 2  # searching for the min of the segment num >= target
 3  n = len(nums)
 4  left, right = 0, n-1
 5  while left != right:
 6    mid = (left + right) // 2
 7    if nums[mid] >= target:
 8      right = mid
 9    else:
10      left = mid + 1
11  return -1 if nums[left] != target else left
12def search_left_for_max():
13  # searching for the max of the segment num <= target
14  n = len(nums)
15  left, right = 0, n-1
16  while left <= right:
17    mid = (left + right) // 2
18    if nums[mid] <= target:
19      left = mid + 1
20    else:
21      right = mid - 1
22  return -1 if nums[right] != target else right

  1. Application: Unsorted Array - Finding Peak Element

Expand Code
 1def findPeakElement(self, nums: List[int]) -> int:
 2  if len(nums) == 1:
 3    return 0
 4  # the fact that we're asked to return ANY peak is the key
 5  # for ANY array, it has a segment of monotonically decreasing segment
 6  # on the right, even if it's of length 1. We need to find the beginning of that
 7  # segment.
 8  # example: 1 2 3 4, the subarray that's monotonically decreasing is [4]
 9  # example: 1,2,5,4, the subarray that's monotonically decreasing is [5,4]
10  # we can use binary search to find this segment.
11  left, right = 0, len(nums)-1
12  while left < right:
13    mid = (left + right) // 2
14    if nums[mid] > nums[mid + 1]:
15      right = mid
16    else:
17      left = mid + 1
18  return left

  1. Application: Search Suggestions System

Expand Code
 1def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
 2  # the idea is to use binary search to find the range of matched words.
 3  # for the first letter in searchWord, we find the range [left, right] with
 4  # the match function. we add first three words within this range (if exists) to our
 5  # resultset.
 6  # 
 7  # then for the next letter, we confine ourselves within the existing range and find
 8  # a subrange for which the match only looks at the second letter between strings
 9  #
10  # we repeat this process until the range diminshes or we run out of letters
11  # we need to sort the products list beforehand to be able to do binary search on it.
12  #
13  # note that to be able to find the range, we need to convert the condition which 
14  # extends the range from either ends.
15  def eq(str1, str2, k):
16    # need to ensure that we're not comparing shorter words
17    if k >= len(str1) or k >= len(str2):
18      return False
19    return str1[k] == str2[k]
20
21  def geq(str1, str2, k):
22    # need to ensure that we're not comparing shorter words
23    if k >= len(str1) or k >= len(str2):
24      return False
25    return str1[k] <= str2[k]
26
27  def leq(str1, str2, k):
28    # need to ensure that we're not comparing shorter words
29    if k >= len(str1) or k >= len(str2):
30      return False
31    return str1[k] >= str2[k]
32
33  def find_left(words, left, right, word, k):
34    # find the leftmost index where words[index][k] <= word[k]
35    while left != right:
36      mid = (left + right) // 2
37      if leq(words[mid], word, k):
38        right = mid
39      else:
40        left = mid + 1
41    return left if eq(words[left], word, k) else -1
42
43  def find_right(words, left, right, word, k):
44    # find the leftmost index where word[k] <= words[index][k]
45    while left <= right:
46      mid = (left + right) // 2
47      if geq(words[mid], word, k):
48        left = mid + 1
49      else:
50        right = mid - 1
51    return right if right >= 0 and eq(words[right], word, k) else -1
52
53  products.sort()
54  left, right = 0, len(products)-1
55  results = []
56
57  for k in range(len(searchWord)):
58    if left <= right and left > -1:
59      left = find_left(products, left, right, searchWord, k)
60      right = find_right(products, left, right, searchWord, k)
61      end_list = min(left + 3, right + 1)
62      results.append(products[left:end_list])
63    else:
64      results.append([])
65  return results

  1. Find max by checking condition on solution space (Social Distancing)

Expand Code
 1from typing import List, Tuple
 2
 3class Solution:
 4    def max_dist(self, n: int, m: int, intervals: List[Tuple[int]]) -> int:
 5        
 6        def condition_satisfied(dist: int) -> bool:
 7            num_placed, last_placed = 0, intervals[0][0] - dist
 8            for first, last in intervals:
 9                if last_placed + dist < first:
10                    # this is important so that the next cow is placed at the beginning of the current interval
11                    last_placed = first - dist
12                while num_placed < n and first <= last_placed + dist <= last:
13                    num_placed += 1
14                    last_placed += dist
15                if num_placed == n:
16                    break
17            return num_placed == n
18        
19        intervals.sort()
20        # binary search on whether it's valid or not to place cows at a specific distance
21        left, right = 0, intervals[-1][1] - intervals[0][0]
22        while left < right:
23            mid = (left +  right + 1) // 2
24            if condition_satisfied(mid):
25                left = mid
26            else:
27                right = mid - 1
28        return left
29
30if __name__ == '__main__':
31    with open('socdist.in', 'r') as input:
32        n, m = map(int, input.readline().strip().split())
33        intervals = [tuple(int(x) for x in line.strip().split()) for line in input.readlines()]
34    
35    assert(m == len(intervals))
36    solution = Solution()
37    ans = solution.max_dist(n, m, intervals)
38    
39    with open('socdist.out', 'w') as output:
40        print(ans, file=output)

  1. Binary Search Rotated

  1. Find Pivot

Expand Code
 1def findMin(self, nums: List[int]) -> int:
 2  """
 3  observations: 
 4  1. base case: num[left] < num[right] -> left is the answer
 5  2. at any given time, the range [left, right] contains the answer
 6  3. to satisfy left should never cross right, the condition should allow left == right
 7  4. in the end, the range reduces to 1 and left is the answer
 8  """
 9  def check_with_right():
10    # search range: [0, n-1]
11    left, right = 0, len(nums) - 1
12    # loop ends when left == right or num[left] < num[right]
13    while left != right and nums[left] > nums[right]:
14      # for the following, num[left] > num[right]
15      # find mid
16      mid = (left + right) // 2
17      # if num[mid] < num[right], answer lies in [left, mid]
18      if nums[mid] < nums[right]:
19        right = mid
20      # if num[mid] > num[right], answer lies in [mid + 1, right]
21      else:
22        left = mid + 1
23    # left contains the min
24    return nums[left]
25    
26  def check_with_left():
27    # search range: [0, n-1]
28    left, right = 0, len(nums) - 1
29    # loop ends when left == right or num[left] < num[right]
30    while left != right and nums[left] > nums[right]:
31      # for the following, num[left] > num[right]
32      # find mid
33      mid = (left + right) // 2
34      # if num[left] > num[mid], answer lies in [left, mid]
35      if nums[left] > nums[mid]:
36        right = mid
37      # if num[left] < num[mid], answer lies in [mid + 1, right]
38      else:
39        left = mid + 1
40    # left contains the min
41    return nums[left]

  1. Search in rotated

Expand Code
 1def direct_search(self, nums: List[int], target: int) -> int:
 2  left, right = 0, len(nums) - 1
 3  while left <= right:
 4    mid = (left + right) // 2
 5    # mid cuts the array in 3 parts
 6    # nums[left...mid-1], nums[mid], nums[mid+1...right]
 7    # case 1: we can check the shortest part first
 8    if nums[mid] == target:
 9      return mid
10    """
11    # case 2: of the two subarrays, at most one of them is rotated
12    # so at least one of them is sorted
13    """
14    # NOTE: it's also possible that both of them are sorted (if mid was the min)
15    # we check if left part is the sorted one
16    if nums[left] <= nums[mid]: # FOR DUPLICATES: check for nums[left] < nums[mid]
17      """ left subarray is sorted """
18      # NOTE: the <= sign instead of < (even though numbers are distinct)
19      # this is to tackle cases of arrays of size 1 and 2
20      if nums[left] <= target and target < nums[mid]:
21        # we can check if target is contained in this sorted half
22        right = mid - 1
23      else:
24        # target is not in the sorted half
25        left = mid + 1
26    else: # FOR DUPLICATES: check for elif nums[left] > nums[mid]:
27      """ right subarray is sorted """
28      if nums[mid] < target and target <= nums[right]:
29        # we can check if target is contained in this sorted half
30        left = mid + 1
31      else:
32        # target is not in the sorted half
33        right = mid - 1
34    # FOR DUPLICATES, WE NEED TO RESORT TO LINEAR SEARCH
35    # else: 
36    #     left += 1
37  return -1
38
39def indirect_search():
40  def find_pivot():
41    left, right = 0, len(nums) - 1
42    while left != right and nums[left] > nums[right]:
43      mid = (left + right) // 2
44      """ also works: if nums[left] > nums[mid]: """
45      if nums[mid] < nums[right]:
46        right = mid
47      else:
48        left = mid + 1
49    return left
50
51  def search_with_pivot(pivot_index):
52    n = len(nums)
53    left, right = 0, n - 1
54    while left <= right:
55      mid = (left + right) // 2
56      pivot = (mid + pivot_index) % n
57      if target == nums[pivot]:
58        return pivot
59      if target < nums[pivot]:
60        right = mid - 1
61      else:
62        left = mid + 1
63    return -1
64
65  return search_with_pivot(find_pivot())

  1. Divide-and-Conquer approaches (e.g., inversion count with merge sort).

  2. Sliding window techniques (efficient for specific range problems).

Note

  • fixed length

    • fixed sum with constant extra bookkeeping

    • fixed sum with auxiliary data structures

  • variable length

    • fixed sum with constant extra bookkeeping - aggregate >= value

    • fixed sum with auxiliary data structures - frequency, prefix sums -> dict, monotonic queue, bst

Attention

  • sequential grouping

  • sequential criteria - longest, smallest, contained, largest, smallest

  1. Two-pointer methods for range problems in sorted data.

  2. Offline processing for batch queries using Mo’s Algorithm or persistent data structures.

  3. Cycle sort

  1. Cycle detection: Floyd

Fundamental Problems

MEX - Minimum Excluded Element

  1. Cycle sort - First missing positive in range [1,n]

  2. Design data structure that pops smallest available numbers in infiite set with addback

Implicit MEX
 1from sortedcontainers import SortedSet
 2
 3"""
 4Think of it as if we're forming an array by calling popSmallest.
 5On that array, we're calling MEX operation.
 6
 7Observations
 8- The array isn't explicit here.
 9- we know that the array doesn't contain duplicates.
10- array can only contain unique elements.
11- we won't need to store a hashmap for counts.
12
13Bookkeeping
14- keep track of the mex elements.
15- keep track of the range of popped elements
16- added back elements form holes in that range
17- anything that's in that hole is smaller than popped max
18  - needs to be sorted
19  - needs fast retrieval
20- how does addback change the popped range?
21"""
22
23class MexImplSetAndHeap:
24  def __init__(self):
25    self.is_missing = set()
26    self.missing_minheap = []
27    self.max_added = 0
28
29  def popSmallest(self) -> int:
30    mex = self.max_added + 1
31    if self.is_missing:
32      mex = min(mex, heapq.heappop(self.missing_minheap))
33      self.is_missing.remove(mex)
34    self.max_added = max(self.max_added, mex)
35    return mex
36  
37  def addBack(self, num: int) -> None:
38    if num <= self.max_added and num not in self.is_missing:
39      self.is_missing.add(num)
40      heapq.heappush(self.missing_minheap, num)
41
42class MexImplSortedSet:
43  def __init__(self):
44    self.missing_numbers = SortedSet()
45    self.max_added = 0
46
47  def popSmallest(self) -> int:
48    mex = self.missing_numbers.pop(0) if self.missing_numbers else self.max_added + 1
49    self.max_added = max(self.max_added, mex)
50    return mex
51
52  def addBack(self, num: int) -> None:
53    if num <= self.max_added:
54      self.missing_numbers.add(num)
55
56class SmallestInfiniteSet:
57
58  def __init__(self):
59    # self.impl = MexImplSortedSet()
60    self.impl = MexImplSetAndHeap()
61
62  def popSmallest(self) -> int:
63    return self.impl.popSmallest()
64
65  def addBack(self, num: int) -> None:
66    self.impl.addBack(num)
67
68
69# Your SmallestInfiniteSet object will be instantiated and called as such:
70# obj = SmallestInfiniteSet()
71# param_1 = obj.popSmallest()
72# obj.addBack(num)

  1. MEX on array with updates

  2. TODO: https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i/description/

  3. TODO: https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-ii/

Pointer Gynmastics

  1. Rotate array

Expand Code
 1from random import shuffle
 2
 3def reverse(nums, l, r):
 4  while l < r:
 5    nums[l], nums[r] = nums[r], nums[l]
 6    l += 1
 7    r -= 1
 8
 9def rotateRight(nums, k):
10  n = len(nums)
11  reverse(nums, 0, n-1)
12  reverse(nums, 0, k-1)
13  reverse(nums, k, n-1)
14
15def rotateLeft(nums, k):
16  n = len(nums)
17  reverse(nums, 0, k-1)
18  reverse(nums, k, n-1)
19  reverse(nums, 0, n-1)
20
21if __name__ == '__main__':
22  nums = list(range(10))
23  shuffle(nums)
24  print(nums)
25  rotateRight(nums, 3)
26  print(nums)
27  rotateLeft(nums, 3)
28  print(nums)

Inversions

  1. Shortest Unsorted Continuous Subarray to Sort

Two approaches - Two pointers, monotonic stack
 1def twoPointersTwoPass(self, nums: List[int]) -> int:
 2  """
 3  Note:
 4  if we sort the numbers, then it is easy to find the solution
 5  which involves identifying interval [i,j] where i is the
 6  leftmost index where sorted[i] differs from nums[i] and j
 7  is the rightmost index where sorted[j] differs from nums[j].
 8  
 9  The trick here is to identify i and j without sorting via understanding inversions.
10  
11  Note that when we sort it, the leftmost point where nums[i] != sorted[i]
12  is where the first inversion happens - nums[i] must have gotten swapped
13  with someting smaller on the right.
14  Similarly, for the rightmost point.
15  
16  We define two intervals: [0,j] and [i,n-1] and take their intersections.
17  (a) Find [0,j] => where j is the rightmost index which is inverted.
18  (b) Find [i,n-1] => where i is the leftmost index which is inverted.
19  
20  For inversions, keep in mind:
21  if nums[p] <-> nums[q] is inverted for some p < q, and nums[r] > nums[p]
22  for p < r < q, then nums[r] <-> nums[p] is also inverted.
23  
24  Therefore, when traversing from left to right, we just need to keep 
25  track of the max we've seen from the left and find inversions on the 
26  right just by comparing it with max.
27  
28  Similarly, when traversing from right to left, we just need to keep
29  track of the min we've seen from right, and find inversions on the left
30  by comparisng only with it
31  """
32  n = len(nums)
33  maxLeftIndex, minRightIndex = 0, n-1
34  rightmostInverted, leftmostInverted = -1, 0
35  for index in range(n):
36    if nums[maxLeftIndex] <= nums[index]:
37      maxLeftIndex = index
38    else:
39      # found someting smaller on the right
40      rightmostInverted = index
41  for index in range(n-1,-1,-1):
42    if nums[index] <= nums[minRightIndex]:
43      minRightIndex = index
44    else:
45      # found something larger on the left
46      leftmostInverted = index
47  return rightmostInverted - leftmostInverted + 1
48
49def monotonicStackSinglePass(self, nums: List[int]) -> int:
50  """
51  Keep track of the index of the leftmost element popped
52  and the largest value of the popped elements so that we
53  can find the rightmost element that's inverted
54  """
55  n = len(nums)
56  maxLeftIndex = 0
57  leftmostInverted, rightmostInverted = n, n-1
58  stack = []
59  for index in range(n):
60    while stack and nums[stack[-1]] > nums[index]:
61      # found something larger on the left
62      leftmostInverted = min(leftmostInverted, stack.pop())
63    if nums[maxLeftIndex] <= nums[index]:
64      maxLeftIndex = index
65    else:
66      # found something smaller on the right
67      rightmostInverted = index
68    stack.append(index)
69  return rightmostInverted - leftmostInverted + 1

  1. Shortest Unsorted Continuous Subarray to Reove

Two pointers
 1def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
 2  length = len(arr)
 3  left, right = 0, len(arr)-1
 4  while left < length-1 and arr[left] <= arr[left+1]:
 5    left += 1
 6  while right > 0 and arr[right-1] <= arr[right]:
 7    right -= 1
 8  if left >= right:
 9    return 0
10  # print(left, right)
11  min_width = min(length - left - 1, right)
12  # print(min_width)
13  for l in range(left + 1):
14    r = right
15    while r < length and arr[l] > arr[r]:
16      r += 1
17    min_width = min(min_width, r-l-1)
18  return min_width

Order Statistics

  1. Kth Largest/Smallest Element in a Stream

  • Maintain the top k elements in a stream of data.

  • Hints: Leverage min-heaps or order statistics trees.

  1. Kth Largest/Smallest Element in an Array

Expand Code
 1def findKthLargest(self, nums: List[int], k: int) -> int:
 2  def quickselect():
 3    # the idea is pick a number at a random index
 4    # partition the array to find the correct index of that number
 5    # array: [left_index, p_index-1][p_index][p_index+1, right]
 6    #                   L               P             R
 7    # if len(L) == k, P is answer
 8    # if len(L) > k, we recurse into the left subarray for k-th largest
 9    # if len(L < k, we recurse into the right subarray for k-len(L)-th largest
10    def partition(left, right, pivot):
11      p_index, index = left, left
12      while index <= right:
13        if nums[index] < pivot:
14          nums[p_index], nums[index] = nums[index], nums[p_index]
15          p_index += 1
16        index += 1
17      return p_index
18
19    def quickselect_impl(left, right, k):
20      if left > right:
21        return None
22      
23      # randomly select a partiton index as pivot and move it to the right
24      p_index = random.randint(left, right)
25      nums[p_index], nums[right] = nums[right], nums[p_index]
26
27      # partition the array based on pivot
28      p_index = partition(left, right-1, nums[right])
29      nums[p_index], nums[right] = nums[right], nums[p_index]
30
31      size_left = p_index - left + 1
32      if size_left-1 == k:
33        return nums[p_index]
34
35      if k < size_left-1:
36        return quickselect_impl(left, p_index-1, k)
37
38      return quickselect_impl(p_index+1, right, k-size_left)
39
40    n = len(nums)
41    return impl(0, n-1, n-k)
42  
43  def heap():
44    # need to find k-th largest
45    # so need a minheap so that whne something larger comes up,
46    # we pop the smallest
47    # the heap stores all numbers greater than or equal to top
48    minheap = []
49    for num in nums:
50      heapq.heappush(minheap, num)
51      if len(minheap) > k:
52        heapq.heappop(minheap)
53    return minheap[0] if len(minheap) else 0
54  
55  return heap()
56  # return quickselect()

  1. Find the Median of a Running Stream

  • Use two heaps (max-heap and min-heap) for efficiency.

  1. Count of Smaller/Larger Numbers After Self

  • Given an array, for each element, count how many elements are smaller/larger to its right.

  • Solution: Fenwick Tree, segment tree, or merge sort.

  1. Find the Kth Largest Element in an Unsorted Array

  • Variants where you cannot sort directly (e.g., use Quickselect).

  1. kth Element in the Cartesian Product

  • Problem: Given two sorted arrays \(A\) and \(B\), find the \(k\)-th smallest tuple \((a, b)\) in \(A \times B\) under the order relation defined above (based on the sum \(a + b\)).

  • Hints: Use a min-heap with tuples to track possible combinations efficiently.

  1. Median in a Sliding Window

  • Problem: Given an array of integers and a sliding window of size \(k\), find the median of each window as it slides from left to right.

  • Hints: Use two heaps (max-heap and min-heap) to dynamically maintain the window.

  1. Inversion Count in Subarrays

  • Problem: For an array \(A\), process \(q\) queries of the form \((L, R)\) where you need to count the number of inversions in the subarray \(A[L:R]\).

  • Hints: Use a segment tree with merge-sort logic at each node.

  1. Range k-th Smallest Element

  • Problem: Given an array and \(q\) queries of the form \((L, R, k)\), find the \(k\)-th smallest element in the range \([L, R]\).

  • Hints: Use a merge sort tree or wavelet tree for efficient query processing.

  1. Count of Numbers in Range with a Given Frequency

  • Problem: Given an array and \(q\) queries of the form \((L, R, F)\), count how many numbers in the range \([L, R]\) appear exactly \(F\) times.

  • Hints: Use Mo’s Algorithm with frequency tracking or segment trees with custom nodes.

Range Query Problems

  1. Range Sum Query with Updates

  • Hints: Solve using segment trees or Fenwick trees with range updates.

  1. Range Minimum/Maximum Query

  • Hints: Solve using segment trees, sparse tables, or hybrid methods.

  1. Dynamic Range Median Queries

  • Hints: Maintain a dynamic dataset and answer queries for the median of a range.

  1. Range XOR Query

  • Hints: Solve using segment trees.

  1. Sum of Range Products

  • Hints: Given an array, answer the sum of products of all pairs in the range [L, R].

  1. Number of Distinct Elements in Range

  • Hints: Use Mo’s Algorithm or a segment tree with a map structure.

  1. Range Frequency Query

  • Hints: Solve using a wavelet tree or merge sort tree.

  1. Dynamic Range Median Queries

  • Problem: Maintain a dynamic array supporting

    1. Insertion of an element.

    2. Deletion of an element.

    3. Querying the median of any range \([L, R]\).

  • Hints: Combine balanced BST or heaps with a range query structure like segment trees.

  1. Range XOR with Updates

  • Problem: Given an array of integers, process the following operations efficiently

    1. Update the \(i\) -th element to \(x\).

    2. Query the XOR of elements in the range \([L, R]\).

  • Hints: Use a segment tree with XOR as the operation and point updates.

  1. Maximum Frequency in a Range

  • Problem: Given an array and \(q\) queries of the form \((L, R)\), find the most frequent number in the range \([L, R]\).

  • Hints: Use a segment tree with frequency maps stored at each node.

  1. Maximum Subarray Sum in a Range

  • Problem: Process queries of the form \((L, R)\), where you must find the maximum subarray sum in the range \([L, R]\).

  • Hints: Augment the segment tree to store max subarray sums and handle overlapping subranges efficiently.

  1. Range Updates with a Custom Function

  • Problem: Design a data structure to efficiently handle

    1. Updates: Apply a custom function \(f(x)\) to all elements in the range \([L, R]\).

    2. Queries: Retrieve the sum of all elements in the range \([L, R]\).

  • Hints: Use a segment tree with lazy propagation where \(f(x)\) can be propagated efficiently.

Hybrid Problems

  1. Dynamic Skyline Problem

  • Given a list of intervals, dynamically insert or delete intervals and determine the current skyline.

  1. Maximum Sum Rectangle in a 2D Matrix

  • Use a 1D segment tree approach for optimal results.

  1. Range GCD Query

  • Find the GCD of elements in the range [L, R] using a segment tree or sparse table.

  1. Number of Rectangles Containing a Point

  • Problem: You are given a list of \(n\) rectangles (defined by two opposite corners) and \(q\) points. For each point, count how many rectangles contain it.

  • Hints: Use a segment tree or 2D Fenwick Tree to maintain active ranges as you sweep through one coordinate.

  1. Dynamic Skyline

  • Problem: Maintain the skyline (maximum height of buildings seen from a distance) as you dynamically add and remove buildings.

  • Hints: Use an interval tree or segment tree to handle dynamic range updates efficiently.

  1. Count Subarrays with Given Sum in Range

  • Problem: For \(q\) queries \((L, R, S)\), count how many contiguous subarrays in the range \([L, R]\) have a sum equal to \(S\).

  • Hints: Use prefix sums with a Fenwick Tree to count valid subarray sums efficiently.

  1. Maximum Overlap of Intervals

  • Problem: Given a list of intervals, process \(q\) queries to find the maximum overlap of intervals in a given range \([L, R]\).

  • Hints: Use a difference array combined with prefix sums or a segment tree for dynamic updates.

  1. Submatrix Sum Queries

  • Problem: Given a 2D grid, process

    1. Updates: Add a value to all elements in a submatrix.

    2. Queries: Find the sum of elements in any submatrix.

  • Hints: Use a 2D Fenwick Tree or segment tree for efficient query and update operations.

Problems Using Monotonic Stack

  1. Largest Rectangle in Histogram

  • Problem: Given an array of heights representing a histogram, find the area of the largest rectangle.

  • Hints: Use a monotonic stack to track bars in increasing order.

  • Sample implementation

    Expand Code
     1class TreeNode:
 2    def __init__(self, idx):
 3        self.idx = idx
 4        self.left = None
 5        self.right = None
 6
 7class CartesianTree:
 8    def __init__(self, nums):
 9        def construct(nums):
10            stack = []
11            for i in range(len(nums)):
12                last = None
13                while stack and nums[stack[-1].idx] > nums[i]:
14                    last = stack.pop()
15                curr = TreeNode(idx=i)
16                curr.left = last
17                if stack:
18                    stack[-1].right = curr
19                stack.append(curr)
20            return stack[0]
21        self.root = construct(nums)
22
23class Solution:
24    def bruteforce(self, nums):
25        n, res = len(nums), 0
26        for i in range(n):
27            curr = inf
28            for j in range(i,n):
29                curr = min(curr, nums[j])
30                res = max(res, curr * (j-i+1))
31        return res
32    def divideAndConquerNaive(self, nums):
33        def findMin(l, r):
34            """ can optimize this """
35            # linear search -> lg(n) search with segment tree -> O(1) search with cartesian tree
36            nonlocal nums
37            currIdx = r
38            for i in range(l,r):
39                currIdx = i if nums[currIdx] > nums[i] else currIdx
40            return currIdx
41        def impl(l, r):
42            nonlocal nums, res
43            if l > r: return -1
44            minIdx = findMin(l, r)
45            curr = 0
46            if minIdx != -1:
47                left = impl(l, minIdx-1)
48                right = impl(minIdx+1, r)
49                curr = max(left, right, nums[minIdx] * (r-l+1))
50                res = max(res, curr)
51            return curr
52        res = 0
53        return impl(0, len(nums)-1)
54    def divideAndConquerCartesianTree(self, heights):
55        root = CartesianTree(heights).root
56        def impl(root, l, r):
57            nonlocal heights
58            if root is None:
59                return 0
60            minHeight = heights[root.idx]
61            currArea = (r-l+1) * minHeight
62            leftMaxArea = impl(root.left, l, root.idx-1)
63            rightMaxArea = impl(root.right, root.idx+1, r)
64            return max(currArea, leftMaxArea, rightMaxArea)
65        return impl(root, 0, len(heights)-1)
66    def monotonicStack(self, nums):
67        """ simulates cartesian tree """
68        # every time something is popped, it's the min of some range
69        # those ranges cover all possible ranges exhaustively
70        n, res = len(nums), 0
71        stack = [-1]
72        for i in range(n):
73            while stack[-1] >= 0 and nums[stack[-1]] > nums[i]:
74                curr = nums[stack.pop()]
75                # popped in the range min of curr top+1 and i-1
76                l, r = stack[-1]+1, i-1
77                res = max(res, curr * (r-l+1))
78            stack.append(i)
79        while stack[-1] >= 0:
80            curr = nums[stack.pop()]
81            # popped is the range min of top+1 and n-1
82            l, r = stack[-1]+1, n-1
83            res = max(res, curr * (r-l+1))
84        return res
85    def largestRectangleArea(self, heights: List[int]) -> int:
86        return self.monotonicStack(heights)

  • Related: Maximum rectangle in binary matrix. Can be reduced to above.

    Expand Code
     1def maximalSquare(self, matrix: List[List[str]]) -> int:
 2  # if the current entry in the matrix is 1, then it can contribute
 3  # to 3 possible squares, one ending with top (i-1, j), one on the left
 4  # (i, j-1) and one ending on the corner (i-1, j-1)
 5  # case by case explanation:
 6  # if the square ending at (i-1, j) is the min, then we know for sure
 7  # that the one ending at (i, j-1) covers at least as many rows as (i-1, j). 
 8  # this is guaranteed since they are SQUARES not RECTANGLES.
 9  m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
10  prev_row = [1 if x == '1' else 0 for x in matrix[0]]
11  curr_row = [0] * n
12  result = max(prev_row)
13  for i in range(1, m):
14    curr_row[0] = 1 if matrix[i][0] == '1' else 0
15    result = max(result, curr_row[0])
16    for j in range(1, n):
17      if matrix[i][j] == '1':
18        curr_row[j] = min(curr_row[j-1], prev_row[j-1], prev_row[j]) + 1
19        result = max(result, curr_row[j])
20    for j in range(n):
21      prev_row[j] = curr_row[j]
22      curr_row[j] = 0
23  return result * result
24  
25def maximalRectangle(self, matrix: List[List[str]]) -> int:
26  # the approach for maximal square doesn't apply here
27  # we solve it by folding it and forming histograms
28  def max_consecutive_ones(arr):
29    left = 0
30    res = 0
31    for right in range(len(arr)):
32      if arr[right] == 0:
33        left = right + 1
34      else:
35        res = max(right - left + 1, res)
36    return res
37
38  def largest_histogram(heights):
39    # we scan from left to right and check the min of every interval
40    # everything that gets popped is the min of some interval
41    max_area = 0
42    minstack = [-1]
43    for i, height in enumerate(heights):
44      while minstack[-1] != -1 and heights[minstack[-1]] >= height:
45        prev_min_index = minstack.pop()
46        # prev_min_index is the min of the range(stack[-1] + 1, i - 1)
47        left, right = minstack[-1] + 1, i - 1 # IMPORTANT: THIS IS WHY WE NEED -1
48        width = right - left + 1
49        max_area = max(max_area, width * heights[prev_min_index])
50      minstack.append(i)
51    # everything that remains on stack is also min of some range
52    while minstack[-1] != -1:
53      prev_min_index = minstack.pop()
54      # prev_min_index is the min of the range(stack[-1] + 1, n - 1)
55      left, right = minstack[-1] + 1, len(heights) - 1
56      width = right - left + 1
57      max_area = max(max_area, width * heights[prev_min_index])
58    return max_area
59
60  m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
61  if not m or not n:
62    return 0
63
64  histogram = [1 if x == '1' else 0 for x in matrix[0]]
65  max_area = max_consecutive_ones(histogram)
66  for i in range(1, m):
67    for j in range(n):
68      histogram[j] = histogram[j] + 1 if matrix[i][j] == '1' else 0
69    max_area = max(max_area, largest_histogram(histogram))
70  return max_area

  1. Trapping Rain Water

  • Problem: Given an array representing heights, calculate how much water can be trapped after it rains.

  • Hints: Use a monotonic stack to find the bounds of trapped water.

  1. Next Greater Element (NGE)

  • Problem: For an array, find the next greater element for each element.

  • Hints: Traverse from the end and use a monotonic stack to maintain greater elements.

  1. Next Smaller Element

  • Problem: For an array, find the next smaller element for each element.

  • Hints: Similar to NGE, but with a decreasing monotonic stack.

  1. Sum of Subarray Minimums

  • Problem: Given an array, find the sum of the minimum values of all subarrays.

  • Hints: Use a monotonic stack to find the nearest smaller elements on both sides.

  1. 132 Pattern

  • Problem: Find if there exists a 132 pattern in an array.

  • Hints: Use a monotonic stack to maintain potential “3” values while iterating.

  1. Daily Temperatures

  • Problem: For each day’s temperature, find how many days you’d have to wait for a warmer temperature.

  • Hints: Monotonic stack tracks indices of temperatures.

  1. Asteroid Collision

  • Problem: Simulate asteroid collisions where larger ones destroy smaller ones.

  • Hints: Use a monotonic stack to simulate collisions.

Problems Using Monotonic Queue

  1. Sliding Window Maximum

  • Problem: Find the maximum element in every sliding window of size \(k\).

  • Hints: Maintain a monotonic queue to store potential maxima.

  1. Shortest Subarray with Sum at Least K

  • Problem: Given an array, find the shortest subarray with a sum \(\geq K\).

  • Hints: Use a monotonic queue to optimize prefix sums.

    Monotonic queue for rightmost left index
     1from itertools import accumulate
 2class Solution:
 3    def shortestSubarray(self, nums: List[int], k: int) -> int:
 4        n = len(nums)
 5        cumsum = [x for x in accumulate(nums)]
 6        print(cumsum)
 7        # for each r, find the largest l in [0,r-1] such that
 8        # cumsum[r]-cumsum[l] >= k, or cumsum[l] <= cumsum[r]-k
 9        minLen = 2*n
10        minQ = deque()
11        for r in range(n):
12            minLen = min(minLen, r+1) if cumsum[r] >= k else minLen
13            while minQ and cumsum[minQ[0]] <= cumsum[r]-k:
14                minLen = min(minLen, r-minQ[0])
15                minQ.popleft()
16            while minQ and cumsum[minQ[-1]] > cumsum[r]:
17                minQ.pop()
18            minQ.append(r)
19        return minLen if minLen < 2*n else -1

  • This can also be solved using segment tree but it’s suboptimal

    Shortest Subarray with Sum at Least K
     1"""
 2862. Shortest Subarray with Sum at Least K
 3https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/
 4Given an integer array nums and an integer k, return the length of the shortest 
 5non-empty subarray of nums with a sum of at least k. 
 6If there is no such subarray, return -1.
 7A subarray is a contiguous part of an array.
 8
 9Note:
10This is not the optimal solution for this problem.
11That uses monotonic queue and works in O(n).
12This one is useful when there are updates to the array.
13"""
14class SegmentTree:
15    def __init__(self, arr):
16        self.n = len(arr)
17        self.nodes = [0]*4*self.n
18        def build(i, l, r):
19            nonlocal arr
20            if l > r: return            
21            if l == r:
22                self.nodes[i] = arr[l]
23            else:
24                m = l+(r-l)//2
25                build(2*i, l, m)
26                build(2*i+1, m+1, r)
27                self.nodes[i] = min(self.nodes[2*i], self.nodes[2*i+1])
28        build(1, 0, self.n-1)
29    def search(self, r, q):
30        def impl(i, tl, tr, r, q):
31            if tl > r: # invalid range
32                return -1
33            if self.nodes[i] > q:
34                return -1
35            if tl == tr: # leaf
36                return tl
37            else:
38                tm = (tl+tr)//2
39                if tm < r:
40                    if self.nodes[2*i+1] <= q:
41                        return impl(2*i+1, tm+1, tr, r, q)
42                    else: # self.tree[2*i] <= q
43                        return impl(2*i, tl, tm, r, q)
44                else:
45                    return impl(2*i, tl, tm, r, q)
46        x = impl(1, 0, self.n-1, r, q)
47        return x
48class Solution:
49    def shortestSubarray(self, nums: List[int], k: int) -> int:
50        if len([True for num in nums if num >= k]) > 0:
51            return 1
52        n = len(nums)
53        # sums keeps the prefix sum
54        sums = nums[:]
55        for i in range(1, n):
56            sums[i] += sums[i-1]
57        # For each Q=sums[r], need to find rightmost l
58        # such that sums[r]-sum[l] >= k
59        # Idea: Find rightmost x <= sums[r]-k using segment tree.
60        # O(n) build time, n queries with O(log n), overall O(n log n)
61        tree = SegmentTree(sums)
62        minLen = 2*n
63        for r in range(1, n):
64            minLen = min(minLen, r+1) if sums[r] >= k else minLen
65            l = tree.search(r-1, sums[r]-k)
66            minLen = min(minLen, r-l) if l != -1 else minLen
67        return minLen if minLen < 2*n else -1

Interview Problems

  1. Sliding Window Maximum

  1. Basic Variant

  • Problem: Find the maximum element in every sliding window of size \(k\) in an array.

  • Hints: Use a monotonic deque to store indices of potential maxima, maintaining decreasing order.

  1. Dynamic Data (Real-Time Updates)

  • Change: The array is dynamic, and elements can be added/removed in real-time.

  • Hints: Use a Segment Tree or Fenwick Tree to track maxima in specific ranges.

  1. Multiple Queries

  • Change: Instead of just one pass, answer multiple queries of the form \([L, R]\) to find the maximum in subarrays.

  • Hints: Preprocess with a Sparse Table (for static queries) or Segment Tree (for dynamic updates).

  1. Largest Rectangle in Histogram

  1. Basic Variant

  • Problem: Find the area of the largest rectangle that can be formed in a histogram.

  • Hints: Use a monotonic stack to find the next smaller and previous smaller heights for each bar.

  1. 2D Matrix (Maximal Rectangle)

  • Change: Extend the to a binary matrix to find the largest rectangle containing only 1s.

  • Hints: Treat each row as a histogram and use the stack approach iteratively.

  1. Dynamic Histogram Updates

  • Change: Allow updates to histogram heights and dynamically compute the largest rectangle.

  • Hints: Use a Segment Tree to store and query the largest rectangle efficiently.

  1. Trapping Rain Water

  1. Basic Variant

  • Problem: Given an array of heights, calculate the total water trapped after rain.

  • Hints: Use two-pointer technique or monotonic stack to find bounds for water levels.

  1. Dynamic Updates

  • Change: Heights can be updated, and the total trapped water must be recalculated efficiently.

  • Hints: Use a Fenwick Tree to maintain prefix max values and efficiently compute water levels.

  1. Multiple Queries

  • Change: For multiple ranges \([L, R]\), calculate the water trapped in those ranges.

  • Hints: Precompute prefix max/min values for efficient range queries.

  1. Next Greater Element (NGE)

  1. Basic Variant

  • Problem: For an array, find the next greater element for each element.

  • Hints: Use a monotonic stack while iterating from the end of the array.

  1. Circular Array

  • Change: The array is circular, so elements wrap around.

  • Hints: Simulate wrapping by iterating twice through the array with a stack.

  1. Dynamic Updates

  • Change: Support updates to the array and answer NGE queries efficiently.

  • Hints: Use a Segment Tree or Ordered Set to dynamically track and query next greater elements.

  1. Range Sum Query

  1. Basic Variant

  • Problem: Given an array, calculate the sum of elements in a range \([L, R]\) .

  • Hints: Use a prefix sum array for efficient range queries.

  1. Dynamic Updates

  • Change: Allow updates to the array and answer range sum queries.

  • Hints: Use a Fenwick Tree or Segment Tree for \(O(\log n)\) updates and queries.

  1. Range Sum with Modulo or Constraints

  • Change: Add a constraint to compute range sums modulo \(k\), or find if the sum in a range satisfies certain conditions.

  • Hints: Use a Segment Tree with custom lazy propagation to handle constraints.

  1. Stock Span Problem

  1. Basic Variant

  • Problem: For each day’s stock price, find the number of consecutive days before it with a price less than or equal to the current day.

  • Hints: Use a monotonic stack to track indices.

  1. Dynamic Price Updates

  • Change: Allow updates to stock prices and recalculate the span dynamically.

  • Hints: Use a Segment Tree to maintain range queries for stock prices.

  1. Multiple Queries for Ranges

  • Change: Answer span queries for multiple subranges \([L, R]\) .

  • Hints: Combine Segment Tree or Sparse Table with preprocessing for efficient queries.

  1. Sum of Subarray Minimums

  1. Basic Variant

  • Problem: Find the sum of minimum values of all subarrays of an array.

  • Hints: Use a monotonic stack to find the nearest smaller elements on both sides.

  1. Dynamic Array Updates

  • Change: Support updates to array elements and recompute the sum of subarray minimums.

  • Hints: Use a Segment Tree to track minimums and their contributions dynamically.

  1. Additional Constraints

  • Change: Add constraints like subarray sums must be within a given range or subarray lengths must be limited.

  • Hints: Combine a Fenwick Tree with constraint checks for efficient processing.

  1. Binary Search Variants

  1. Basic Variant

  • Problem: Find an element in a sorted array using binary search.

  • Hints: Divide and conquer to find the target element.

  1. Rotated Sorted Array

  • Change: The array is rotated; find the target element.

  • Hints: Modify binary search to handle rotations.

  1. Minimum in Rotated Sorted Array with Duplicates

  • Change: The rotated array contains duplicates.

  • Hints: Adapt binary search with careful handling of duplicate elements.

  1. Find Median in a Stream

  • Change: Support dynamic updates and find the median efficiently.

  • Hints: Use a combination of Heaps or Balanced BSTs for dynamic median maintenance.