Arrays

Two sum [LC#1]

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Sorting and two pointers

• $T(n) = O(n \log n)$; $S(n) = O(n)$ for maintaining the index.

def two_sum(nums: List[int], target:Int) -> Tuple[int, int]:
    indexed_nums  = sorted((n, i) for i, n in enumerate(nums))
    left, right = 0, len(indexed_nums) - 1
    
    while left < right:
        current_sum = indexed_nums[left][0] + indexed_nums[right][0]
        
        if current_sum == target:
            return (indexed_nums[left][1], indexed_nums[right][1])
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return (-1, -1)

Hashset

• $T(n) = O(n)$; $S(n) = O(n)$

def two_sum(nums: List[int], target: int) -> Tuple[int, int]:
    num_to_idx = {}
    for i, num in enumerate(nums):
        residue = target - num
        if residue in lut:
            return (i, num_to_idx[residue])
        num_to_idx[num] = i
    return (-1, -1)

Three Sum [LC#15]

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Duplicate Number [LC#287]

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and using only constant extra space.

Rotate Array [LC#189]

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Intuition

• If we look at the indices formed by k hops, they form a cycle ending at the start indices. If n%k = 0 , then there are k such cycles.
• We use 1 extra storage and simply swap the elemnts to their right position.

Code

def rotate_array(nums: List[int], k: int) -> None:
    n = len(nums)
    k = k % n # for k > n
    start = 0
    count = 0
    while count < n:
        curr = start
        storage = nums[curr]
        while True:
            curr = (curr + k) % n
            nums[curr], storage = storage, nums[curr]
            count += 1
            if start == curr:
                break
        start += 1

Time complexity

• $T(n) = O(n)$
• $S(n) = O(1)$

Sorting

Quick Select

Partition Scheme intuition.

• Select the last element in the array as pivot.
• Maintain 2 pointer, left and right.
• Traverse the array updating both pointers such that the values in [left, right] is always > the pivot.

#  [ ≤ ][ ≤ ][ > ][ > ][ > ][ > ][ ? ][ hi ]     
#              └─ left        └─ right 

def lomuto_partition(A, lo, hi):
    pivot = A[hi]
    left = lo
    for right in range(lo,  hi): 
        if A[right] <= pivot:
            A[left], A[right] = A[right], A[left]
            left = left + 1
    A[left], A[hi] = A[hi], A[left]
    return left

Quick sort using the partition scheme

def quicksort(A, lo, hi):
    if lo >=hi or lo <0:
        return 
    p = lomuto_partition(A, lo, hi)
    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)

Strings

Longest Common Prefix

Group Anagrams

Reorganize String [LC#767]

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return "" if not possible.

Intuition

• If the character with largest frequency appears more that (n+1)//2 times, then such an arrangement is not possible.
• Simply arrange max frequent character in interleaved indexes and fill out other characters in the gaps.

Code

def reorganize_string(self, s: str) -> str:
    character_counts = Counter(s)
    n = len(s)
    if max(character_counts.values()) > (n + 1) // 2:
        return ""

    def interleaved_index_generator(n):
        for i in range(0, n, 2):
            yield i
        for i in range(1, n, 2):
            yield i

    characters = list(s)
    characters.sort(
        key=lambda char: (character_counts[char], char), 
        # break tie when 2 chars have same counts
        reverse=True
    )
    output = characters.copy()
    interleaved_index = interleaved_index_generator(n)
    for character in characters:
        output[next(interleaved_index)] = character
    return "".join(output)

Time complexity

• $T(n) = O(n \log n)$ $S(n) = O(n)$. Time complexity is $O(n)$ if we sort while exploiting the fact that there are only constant number of characters.

Subarray

Maximum Subarray Sum [LC#53]

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Kadane’s algorithm

• Find the max sum of subarray ending at location i.
• $T(n) = O(n)$; $S(n) = O(1)$

def max_subarray_sum(nums: List[int]) -> int:
    curr, ans = 0, nums[0]
    for num in nums:
        curr = max(curr + num, num)
        ans = max(ans, curr)
    return ans

Best Time to Buy and Sell Stock [LC#121]

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Inutition

• The solution is a variation of Kadane’s algorithm.
• Keep track of minimum seen so far.
• Max profit if we sell now can be computed with this minimum.
• Keep track of max profit.

Code

def max_profit(prices: List[int]) -> int:
    max_profit = 0
    min_price = prices[0]
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

Time Complexity

• $T(n) = O(n)$ and $S(n) = O(1)$

Best Time to Buy and Sell Stock II [LC#122]

You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.

Intuition

• Every climb is the sub profit. Add all sub profits.
• [1,7,5,8]. (7-1) + (8-5) > (8 - 1).

Code

def max_profit(self, prices: List[int]) -> int:
    profit = 0
    for i in range(1, len(prices)):
        if prices[i - 1] < prices[i]:
            profit += (prices[i] - prices[i - 1])
    return profit

Time complexity

• $T(n) = O(n)$
• $S(n) = O(1)$

Best Time to Buy and Sell Stock IV [LC#188]

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Intuition

• f[k][i] denotes maximum profit obtainable by doing k transactions with first i prices.
• The dp equation is

  f[k][i] = max(
      f[k][i-1], 
      max( prices[i] - prices[j] + f[k-1, j] for i in [0, i-1] )
  )
  = max(
      f[k][i-1], 
      prices[i] + max( f[k-1, j] - prices[j] +  for i in [0, i-1] )
  )
  

• Also, f[k][0] = 0 and f[0][i] = 0
• The inner max can be maintained as a running maximum.

Code

def max_profit_with_k_transactions(K: int, prices: List[int]) -> int:
    n = len(prices)
    f = [[0] * (n) for _ in range(K + 1)]
    max_profit = 0
    for k in range(1, K + 1):
        t = f[k - 1][0] - prices[0]
        for i in range(1, n):
            t = max(t, f[k - 1][i] - prices[i])
            f[k][i] = max(f[k][i - 1], prices[i] + t)
            max_profit = max(max_profit, f[k][i])
    return max_profit

Time complexity

• $T(n) = O(nk)$
• $S(n) = O(n)$ Currently $O(nk)$ but can be optimised to use only two array of storage. The algorithm can also be modified to use only $O(k)$ storage.

Continuous Subarray Sum [LC#523]

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise. A good subarray is a subarray where:

• Its length is at least two, and
• The sum of the elements of the subarray is a multiple of k.

Intuition

• For quickly finding sum of a subarray, we can use prefix sums.
  • sum(i:j) = prefix(i) - prefix(j)
• mod operator preoperty:
  • (a-b)%k = (a%k - b%k)%k = a%k - b%k
• So if prefix(i)%k == prefix(j)%k for any i and j more than 2 indices apart, the answer is true.
• Only corner case is a prefix array sum itself that sum%k to 0.

Solution

def check_subarray_sum(nums: List[int], k: int) -> bool:
    n = len(nums)
    mod_seen = {0: -1}  # for prefixes that exactly sum%k to 0
    prefix_sum = 0
    for i in range(n):
        prefix_sum = prefix_sum + nums[i]
        prefix_mod = prefix_sum % k
        if prefix_mod in mod_seen:
            if i - mod_seen[prefix_mod] > 1:
                return True
        else:
            mod_seen[prefix_mod] = i

        prefix_sum = prefix_mod
    return False

Time Complexity

• $T(n) = O(n)$ and $S(n) = O(n)$

Subarray Sum Equals K [LC#560]

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Intuition

• For quickly finiding sum of a subarray, we can use prefix sums.
  • sum(i:j) = prefix(i) - prefix(j)
• While we are computing prefix(i) if residue = prefix(i) - k is already among prefixes, then there is a subarray with sum k. We simply have to keep a count.

Solution

def count_subarray_sum_to_targets(nums: List[int], k: int) -> int:
    prefixes = defaultdict(int)
    prefixes[0] = 1 # empty array is a subarray of sum 0

    current = 0
    counts = 0
    for num in nums:
        current += num
        counts += prefixes[current - k]
        prefixes[current] += 1
    return counts

Time Complexity

• $T(n) = O(n)$ and $S(n) = O(n)$

Product of Array Except Self [LC#238]

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

Code

def product_except(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1,]
    for i in range(n - 1):
        ans.append(ans[-1] * nums[i])
    post = 1
    for i in range(n - 2, -1, -1):
        post = post * nums[i + 1]
        ans[i] = ans[i] * post
    return ans

Time Complexity

• $T(n)= O(n)$ and $S(n)= O(n)$

Maximize Subarray Sum After Removing All Occurrences of One Element [LC#3410]

You are given an integer array nums. You can do the following operation on the array at most once:

• Choose any integer x such that nums remains non-empty on removing all occurrences of x.
• Remove all occurrences of x from the array.

Return the maximum subarray sum across all possible resulting arrays.

Intuition

Code

Time complexity

• $T(n) = $
• $S(n) = $

Stack

Asteroid Collision [LC#735]

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Intuition

Code

def asteroid_collision(asteroids: List[int]) -> List[int]:
    stack = []

    for asteroid in asteroids:
        store = True
        while stack and stack[-1] > 0 and asteroid < 0:
            # there is collision
            if abs(stack[-1]) < abs(asteroid):
                stack.pop()
                continue                
            elif abs(stack[-1]) == abs(asteroid):
                stack.pop()
                store = False
                break
            else:
                store = False
                break
        if store:
            stack.append(asteroid)
    return stack

Time complexity

• $T(n) = O(n)$
• $S(n) = O(n)$

Linked List

Reverse Linked List [LC#206]

Given the head of a singly linked list, reverse the list, and return the reversed list.

Iterative approach

     ┌────┐    ┌────┐    ┌────┐
 <-- │prev│    │curr│--> │next│-->
     └────┘    └────┘    └────┘
     ┌────┐    ┌────┐    ┌────┐
 <-- │prev│ <--│curr│    │next│-->
     └────┘    └────┘    └────┘
     ┌────┐    ┌────┐    ┌────┐
 <-- │    │ <--│prev│    │next│-->
     └────┘    └────┘    └────┘
     ┌────┐    ┌────┐    ┌────┐
 <-- │    │ <--│prev│    |curr│-->
     └────┘    └────┘    └────┘

def fn(head):
    curr = head
    prev = None
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Time Complexity

• $T(n) = O(n)$
• $S(n) = O(1)$

Remove Nth Node From End of List [LC#19]

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Code

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    fake_head = ListNode(0, head)
    P = fake_head
    while n>0 and P:
        P = P.next
        n=n-1
    if not P: return head # less than n nodes

    Q = fake_head
    while P.next:
        P = P.next
        Q = Q.next
    Q.next = Q.next.next
    return fake_head.next

Merge Two Sorted Lists [LC#21]

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

# Definition for singly-linked list.
@dataclass
class ListNode:
    val: int = 0
    next: Optional[ListNode] = None

Iterate and Merge

• $T(n) = O(m+n)$; $S(n) = O(1)$

def merge_two_sorted_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
      fake_head = ListNode()
      current = fake_head
      
      while list1 and list2:
          if list1.val < list2.val:
              current.next = list1
              list1 = list1.next
          else:
              current.next = list2
              list2 = list2.next
          current = current.next
      current.next = list1 if list1 else list2
      
      return fake_head.next

Merge k Sorted Lists [LC#23]

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.

Brute-Force

• Merge all lists into one and sort the list
• $T(n) = O(n \log n)$ ; $S(n) = O(n)$

Priority Queue or Min Heap

• Create a min heap with first values of all the lists
• Repeatedly pop the root of min heap, add to the answer and push the next value of the list where root was from to the heap
• $T(n) = O(k + n \log k)$ heapify + n pop root
• $S(n) = O(k)$ for the heap

def merge_sorted_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    class HeapNode:
        def __init__(self, node: ListNode):
            self.node = node
        def __lt__(self, other):
            return self.node.val < other.node.val
    
    heap = []
    current = dummy = ListNode(0)
    for lst in lists:
        if lst:
            heapq.heappush(heap, HeapNode(lst))
    
    while heap:
        node = heapq.heappop(heap).node
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, HeapNode(node.next))

    return dummy.next

Iterative Mergesort on sorted lists

• Take 2 pairs of list and sort them together
• Do this iteratively until there is only 1 left
• $T(n) = O(n + n/2 + n/4 + … +n/k) = O(n \log k)$
• $S(n) = O(1)$

Linked List Cycle [LC#141]

Given head, the head of a linked list, determine if the linked list has a cycle in it. Return true if there is a cycle in the linked list. Otherwise, return false.

Floyd’s Turtle and hare algorithm

It relies on the fact that if two pointers are moving at different speeds within a cycle, their distances will reach a max length before being reset to zero at which point they will point to the same element.

Time complexity

• $T(n) = O(n)$ Will travel initial n of non-cyclic then k which is cycle length.
• $S(n) = O(n)$

Code

def has_cycle(head: Optional[ListNode]) -> bool:
    turtle, hare = ListNode(0, head), ListNode(0, head)
    while turtle and hare:
        if turtle == hare:
            return True
        turtle = turtle.next
        hare = hare.next.next if hare.next else None
    return False

Implementing LRU Cache [LC#146]

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in $O(1)$ average time complexity.

Intuition

• Values can be stored in a dictionary
• For keeping track of freshness, we use a doubly linked list.
  • New values are inserted at the right end
  • existing values are removed and nserted at the right end to implement recently used property
  • Capacity can be enforced by removing nodes from left. Nodes in the left are least recently used.

Code

class Node:
    def __init__(self, key, val, nxt=None, prev=None):
        self.key = key
        self.val = val
        self.next = nxt
        self.prev = prev
    
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.storage = {}
        self.head = Node(-1, -1, None, None)
        self.tail = Node(-2, -2, None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def add_at_end(self, node):
        node.prev = self.tail.prev
        node.next = self.tail 
        self.tail.prev.next = node
        self.tail.prev = node

    def remove_node(self, node):
        node.next.prev = node.prev
        node.prev.next = node.next
        return node.key

    def get(self, key: int) -> int:
        if key in self.storage:
            # update freshness
            node = self.storage[key]
            self.remove_node(node)
            self.add_at_end(node)
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.storage:
            self.storage[key].val = value
            self.get(key)
        else:
            node = Node(key, value, None, None)
            self.storage[key] = node
            self.add_at_end(node)
            if len(self.storage)>self.capacity:
                rm_key = self.remove_node(self.head.next)
                del self.storage[rm_key]     

Time Complexity

• $O(1)$ for get and put
• $O(n)$ storage for dictionary and linkeidnlist

Remove Nodes From Linked List [LC#2487]

You are given the head of a linked list. Remove every node which has a node with a greater value anywhere to the right side of it. Return the head of the modified linked list.

Intuition

• Use a monotonic increasing stack. The nodes that are left on the stack is the answer.

Code

def remove_nodes(self, head: Optional[Node]) -> Optional[Node]:
    stack = []
    node = head
    while node:
        while stack and node and stack[-1].val < node.val:
            mid = stack.pop()
        stack.append(node)
        node = node.next
    
    dummy = node = Node(0, None)
    for v in stack:
        node.next = v
        node = v
    return dummy.next

Time complexity

• $T(n) = O(n)$
• $S(n) = O(n)$

Sequences

Longest Consecutive Sequence [LC#128]

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Brute Force

• Consider each element as seed.
• Check if next element in the sequece is in the list. keep track of sequence length
• $T(n) = O(n^3)$; $S(n) = O(1)$

Sorting

• Sort the array.
• Check the length of longest conseqtive sequence
• $T(n) = O(n \log n)$; $S(n) = O(n)$

Hash Table based look up

• For each num, if num-1 is not in the list, then its possibly a sequence’s begning
• For each sequence begning, check if conseqtive elements are in the list
• Each valid sequence is tested once
• $T(n) = O(n)$
• $S(n) = O(n)$

def longest_consecutive_sequence(nums: List[int]) -> int:
    entries = set(nums)
    best = 0
    for num in nums:
        if num-1 not in entries:
            next_num, seq_len = num+1, 1
            while next_num in entries: 
                next_num += 1
                seq_len += 1
            best = max(best, seq_len)
    return best

Longest Increasing Subsequence [LC#300]

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Dynamic programming approach

• Find the length of longest increasing subsequence ending at i.

  def length_of_lis(nums: List[int]) -> int:
      if not nums: return 0
      max_length = [1] * len(nums)
      for i in range(1, len(nums)):
          for j in range(i):
              if nums[i] > nums[j]:
                  max_length[i] = max(max_length[i], max_length[j] + 1)
      return max(max_length)
  

• $T(n) + O(n^2)$; $S(n) = O(n)$

Technique based on patience sorting

• If the number is larger than the largest element in the temporary array, append it. Otherwise, replace the found position with the current number.
• The length of the temporary array will give the length of the longest increasing subsequence.
• The temp array may not always have a valid subsequence, but its length will always be equal to longest subsequence.

  from bisect import bisect_left
  
  def length_of_lis(nums: List[int]) -> int:
      if not nums: return 0
      tails = []
      for num in nums:
          pos = bisect_left(tails, num)
          if pos == len(tails):
              tails.append(num)
          else:
              tails[pos] = num
      return len(tails)
  

• $T(n) = O(n \log n)$; $S(n) = O(n)$

Russian Doll Envelopes [LC#354]

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope. One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height. Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other). Note: You cannot rotate an envelope.

Intuition

• The problem is a 2D version of Longest Increasing Subsequence, but since the item order is not static in the original problem, we can convert it to a 1D version as follows.
• If a set of envelopes share same width, then 2 in such should not be selected. To ensure this, we sort the sequence in increasing order of width and then decreasing order of height. This also ensures that when a taller one is selected, the shorter ones are not selected after that.

Code

def russian_dolls(envelopes: List[List[int]]) -> int:
    envelopes.sort(key=lambda r: (r[0], -r[1]))
    return self.length_of_lis(h for w, h in envelopes)

def length_of_lis(nums: List[int]) -> int:
    if not nums:
        return 0
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

Run time

Time complexity for sorting is $O(n \log n)$ and for LIS it is $O(n \log n)$. Depending on the implementation, we need $O(n)$ extra space.

• $T(n) = O(n \log n)$ and $S(n) = O(n)$

Longest Common Subsequence [LC#1143]

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”. A common subsequence of two strings is a subsequence that is common to both strings.

Dynamic programming approach

• dp[i][j] contains length of longest subsequence by using first i-1 characters of first string and j-1 characters of second string.
• dp[i][0] = 0 and dp[0][j] = 0
• $T(n) = O(mn)$; $S(n) = O(mn)$

  def longest_common_subsequence(text1: str, text2: str) -> int:
      m = len(text1)
      n = len(text2)
  
      # Create a 2D array to store lengths of longest common subsequence.
      dp = [[0] * (n + 1) for _ in range(m + 1)]
  
      # Build the dp array
      for i in range(1, m + 1):
          for j in range(1, n + 1):
              if text1[i - 1] == text2[j - 1]:
                  dp[i][j] = dp[i - 1][j - 1] + 1
              else:
                  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  
      # The length of the longest common subsequence is in dp[m][n]
      return dp[m][n]
  

Dynamic programming approach with space optimisation

• $T(n) = O(mn)$ ; $S(n) = O(\min\{m,n\})$

  def longest_common_subsequence(text1: str, text2: str) -> int:
      if len(text2) > len(text1):
          return longest_common_subsequence(text2, text1)
  
      m = len(text1)
      n = len(text2)
  
      prev = [0] * (n + 1)
      curr = [0] * (n + 1)
      for i in range(1, m + 1):
          for j in range(1, n + 1):
              if text1[i - 1] == text2[j - 1]:
                  curr[j] = prev[j - 1] + 1
              else:
                  curr[j] = max(curr[j - 1], prev[j])
          prev, curr = curr, prev
      return prev[n]
  

Longest Palindromic Subsequence [LC#516]

Given a string s, find the longest palindromic subsequence’s length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Intuition

If the characters at the both ends of the string sre the same, they must be part of the longest palindrome. We can add 2 to the length and remove those characters. If they are not equal, then the longest palindrome would be in either of the arrays with one of the end characters removed.

Dynamic Programming

def longest_palindrommic_subsequence(s: str) -> int:
    @cache
    def longest(i, j):
        if i == j:
            return 1
        if i > j:
            return 0
        if s[i] == s[j]:
            return 2 + longest(i + 1, j - 1)
        else:
            return max(longest(i + 1, j), longest(i, j - 1))
    return longest(0, len(s) - 1)

Time Complexity

• $T(n) = O(n^2)$ and $S(n) = O(n^2)$

Dynamic Programming with space optimisation

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    curr_dp, prev_dp = [0] * n, [0] * n

    for i in range(n - 1, -1, -1):
        curr_dp[i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                curr_dp[j] = prev_dp[j - 1] + 2
            else:
                curr_dp[j] = max(prev_dp[j], curr_dp[j - 1])
        prev_dp = curr_dp[:]

    return curr_dp[n - 1]

Time Complexity

• $T(n) = O(n^2)$ and $S(n) = O(n)$

Sum of Good Subsequences [LC#3351]

You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1. Return the sum of all possible good subsequences of nums (modulo $10^9 + 7$). Note that a subsequence of size 1 is considered good by definition.

Intuition

• We can append num to a sequence ending in num-1 or num+1 or start a new good subsequence, i.e, count[num] = count[num-1] + count[num+1] + 1
• Contribution of num to the final sum is (num * count[num]). But to avoid duplicates, we iterate over the array and keep the total in another counter

Solution

def sum_of_good_subsequences(nums: List[int]) -> int:
    mod = 10 ** 9 + 7
    total = Counter()
    count = Counter()
    for num in nums:
        ending_at = count[num - 1] + count[num + 1] + 1
        total[num] += total[num - 1] + total[num + 1] + num * ending_at
        count[num] += ending_at
    return sum(total.values()) % mod

Time Complexity

• $T(n) = O(n)$; $S(n) = O(n)$

Palindromes

Longest Palindromic Substring [LC#5]

Given a string s, return the longest palindromic substring in s.

Intuition

Expand around Center

Code

def longestPalindrome(string: str) -> str:
    def expand_around_center(left: int, right: int, string: str) -> str:
        while left >= 0 and right < len(string) and string[left] == string[right]:
            left = left - 1
            right = right + 1
        return string[left + 1 : right]

    longest = ""
    for i in range(len(s)):
        longest = max(
            longest,
            expand_around_center(i, i, string),
            expand_around_center(i, i + 1, string),
            key=len,
        )
    return longest

Time Complexity

• $T(n) = O(n^2)$
• $S(n) = O(1)$

Count Palindromic Substrings [LC#647]

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Intuition

Expand around Center

Code

def count_palindromic_substrings(s: str) -> int:
    def expand_around_center(left: int, right: int) -> int:
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left = left - 1
            right = right + 1
            count = count + 1
        return count

    count = 0
    for i in range(len(s)):
        # odd length palindromes
        count += expand_around_center(i, i)

        # even length palindromes
        count += expand_around_center(i, i + 1)
    return count

def count_palindromic_substrings_faster(s: str) -> int:
    p = manacher(s)
    count = 0
    for length in p:
        if length % 2 == 0:
            count += length // 2
        else:
            count += length // 2 + 1
    return count

def manacher(self, s):
    t = "#".join("^{}$".format(s))
    n = len(t)
    p = [0] * n
    center = right = 0

    for i in range(1, n - 1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        if i + p[i] > right:
            center, right = i, i + p[i]

    return p[1:-1]

Time Complexity

• $T(n) = O(n^2)$ $O(n)$ if you use manacher.
• $S(n) = O(1)$

Manacher Algorithm

All palindromes in $O(1)$

def manacher(s: str):
    t = '#'.join('^{}$'.format(s))
    n = len(t)
    p = [0] * n
    center = right = 0

    for i in range(1, n - 1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
            
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        if i + p[i] > right:
            center, right = i, i + p[i]

    return p[1:-1]

Palindromic Partition

Parentheses

Longest Valid Parentheses [LC32]

Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses substring

Using stack

def longest_valid_parentheses(self, s: str) -> int:
    ans = 0
    stack = [-1]
    for i in range(len(s)):
        if s[i] == "(":
            stack.append(i)
        else:
            stack.pop()
            if stack:
                ans = max(ans, i - stack[-1])
            else:
                stack.append(i)
    return ans

Time Complexity

• $T(n) = O(n)$ and $S(n) = O(n)$

Using 2 pointers

One of the passes will catch all the longest substring. Check the counter comparison condition and order of the comparisons.

def longest_valid_parentheses(self, s: str) -> int:
    left, right = 0, 0
    ans = 0
    for c in s:
        if c == '(':
            left += 1
        else:
            right += 1
            
        if right == left:
            ans = max(ans, 2*right)
        elif right > left:
            left = right = 0
    
    left = right = 0
    for c in reversed(s):
        if c == '(':
            left += 1
        else:
            right += 1

        if right == left:
            ans = max(ans, 2*right)
        elif left > right:
            left = right = 0
    return ans

Time Complexity

• $T(n) = O(n)$ and $S(n) = O(1)$

Valid Parenthesis String [LC#678]

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid. The string is valid if it is a valid paranthesised string where any '*' could be treated as '(' or ')' or empty string.

Intuition

• there is a 2 stacks approach where one stack is used to store indices of '(' and match with the corresponding ')' while the other maintains indices of '*'.

• The key observation here is to note that either the aesterics can all be left or empty OR right or empty in valid configurations. We count from both sides for either.

Code

def valid_parenthesis(string: str) -> bool:
    n = len(string)
    open_cnt = 0
    close_cnt = 0
    for left, right in zip(range(n), range(n-1, -1, -1)):

        if string[left] in ["(", "*"]:
            open_cnt += 1
        else:
            open_cnt -= 1

        if string[right] in [")", "*"]:
            close_cnt += 1
        else:
            close_cnt -= 1

        if open_cnt < 0 or close_cnt < 0:
            return False
    return True

Time complexity

• $T(n) = O(n)$
• $S(n) = O(1)$

Minimum Add to Make Parentheses Valid [LC#921]

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))". Return the minimum number of moves required to make s valid.

Intuition

Code

def make_valid(s: str) -> int:
    stack = []
    insert_count = 0
    for char in s:
        if char =='(':
            stack.append(char)
        if char == ')':
            if stack:
                stack.pop()
            else:
                insert_count +=1
    insert_count += len(stack)
    return insert_count

def make_valid(self, s: str) -> int:
    insert_count = 0
    open_count = 0
    for char in s:
        if char =='(':
            open_count+=1
        if char == ')':
            if open_count>0:
                open_count-=1
            else:
                insert_count +=1
    insert_count += open_count
    return insert_count

Time complexity

• $T(n) = O(n)$
• $S(n) = O(1)$. If using stack then $O(n)$.

Two Pointers

Containers with most water [LC#11]

Given $n$ non-negative integers $a_1$, $a_2$, … , $a_n$ , where each represents a point at coordinate $(i, a_i)$. $n$ vertical lines are drawn such that the two endpoints of the line $i$ is at $(i, a_i)$ and $(i, 0)$. Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Two pointer approach

• Given 2 walls, the volume of water between them is limited by the smaller one. So we can move inwards from the smaller wall.
• This can be implemented using a 2 pointer approach closing in from both ends.
• $T(n) = O(n)$

def max_water(height: List[int]) -> int:
    left, right = 0, len(height)-1
    max_area = 0
    while left < right:
        max_area = max(
            max_area, 
            (right - left)*(min(height[left], height[right])) 
        )
        # we have to move away from the smaller wall
        # as it is limiting factor of the area
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

Sliding Window

Longest Substring Without Repeating Characters [LC#3]

Given a string s, find the length of the longest substring without repeating characters.

Sliding Window and 2 pointers

• Start with left and right at 0.
• Expand: Move right to add characters and update counts until a repeat is found.
• Shrink: Move left to remove characters until all are unique.
• Track maximum length of the window.
• $T(n) = O(n)$; $S(n) = O(|char set|)$

  def max_substring_without_repetition(s: str) -> int:
      char_count = defaultdict(int)
      left = 0
      ans = 0
      for right in range(len(s)):
          current_char = s[right]
          char_count[current_char] += 1 
          while char_count[current_char]>1:
              char_count[s[left]] -= 1 
              left += 1
          ans = max(ans, right-left+1)
      return ans
  

Optimised Sliding window

• Same as previous approach, but keep track last occurance of all characters seen so far.
• Jump to the next after last occurence whenever a character is encountered again.
• $T(n) = O(n)$; $S(n) = O(|char set|)$

  def max_substring_without_repetition(s: str) -> int:
      last_found_at = {}
      left = 0
      ans = 0
      for right in range(len(s)):
          current_char = s[right]
          if current_char in last_found_at:
              left = max(left, last_found_at[current_char]+1)
          last_found_at[current_char] = right
          ans = max(ans, right - left +1)
      return ans
  

String Compression [LC#443]

Given an array of characters chars, compress it using the following algorithm: Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group’s length is 1, append the character to s.
• Otherwise, append the character followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars. After you are done modifying the input array, return the new length of the array.

Intuition

• Two Pointers and sliding window

Code

def string_compress(chars: List[str]) -> int:
    left = 0
    pos = 0
    chars.append(" ") # to proccess last group
    for right in range(len(chars)):
        if chars[right] != chars[left]:
            length = right - left
            if length == 1:
                string = chars[left]
            else:
                string = f"{chars[left]}{length}"
            for c in string:
                chars[pos] = c
                pos += 1
            left = right
    return pos

Time complexity

• $T(n) = O(n)$
• $S(n) = O(1)$

Take K of Each Character From Left and Right [LC#2516]

You are given a string s consisting of the characters ‘a’, ‘b’, and ‘c’ and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s. Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

Intuition

We are looking for a largest window that can be removed without making count of all characters going below k

Code

def take_characters(s: str, k: int) -> int:
    if k == 0 : return 0 
    count = Counter({"a": 0, "b": 0, "c": 0})
    for char in s:
        count[char] += 1

    if min(count.values()) < k:
        return -1

    max_window = 0
    left = 0
    for right in range(len(s)):
        count[s[right]] -= 1
        while left <= right and min(count.values()) < k:
            count[s[left]] += 1
            left += 1
        max_window = max(max_window, right - left + 1)
    return len(s) - max_window

Time complexity

• $T(n) = O(n)$
• $S(n) = O(|characters|)$

Partition Labels [LC#763]

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part. Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s. Return a list of integers representing the size of these parts.

Intuition

• While iterating through the string, if we know the last position of each character, we can keep extending the span of sting to include to safely include c.
• If the span and the current index coincide, then the string can be partitioned at the current index.

Code

def partition_string(string: str) -> List[int]:
    last_pos = defaultdict(int)
    for i, char in enumerate(string):
        last_pos[char] = i

    left = 0
    right = 0
    lengths = []
    for i, char in enumerate(string):
        right = max(right, last_pos[char])
        if right == i:
            lengths.append(right - left + 1)
            left = i + 1
    return lengths

Time complexity

• $T(n) = O(n)$
• $S(n) = O(|c|)$

Trees

Tree Traversals

In Order

Pre Order

Post Order

Level Order

Construct Binary Tree from Preorder and Inorder Traversal [LC#105]

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Intuition

The elements in preorder represents the roots where the inorder traversal needs to be bifurcated. Maintaining a index map of inorder to quickly map to position of any element will allow quickly building the tree recursively.

Code

def build_tree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    val_to_idx = {val: idx for idx, val in enumerate(inorder)}

    def construct(in_left, in_right):
        if in_left > in_right:
            return None

        val = preorder.pop(0)
        in_idx = val_to_idx[val]
        node = TreeNode(val)

        node.left = construct(in_left, in_idx - 1)
        node.right = construct(in_idx + 1, in_right)
        return node
    return construct(0, len(preorder) - 1)

Time Complexity

• $T(n) = O(n)$ and $S(n) = O(n)$ for the recursion stack

Binary Tree Maximum Path Sum [LC#124]

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Depth first traversal

• The answer is inspired from from Kadane’s algorithm for max array sum
• At every node, we are looking for what is max path sum of the path ending at the node and containing only the node’s children.
• Once we have that for both children, we can also calculate the max path sum of the path passing through the node.
• Keep track of the maximum of such path sum’s
• $T(n) = O(n)$; $S(n) = O(h)$. recursion depth $\approx$ max height of the tree

def binary_tree_max_path_sum(root: Optional[TreeNode]) -> int:
    ans = float('-inf')
    def ending_with(node):
        # What is the max path sum with path ending at node
        # and the path contains only node's children?

        nonlocal ans
        if not node: return 0

        left_gain = max(ending_with(node.left), 0)
        right_gain = max(ending_with(node.right), 0)

        # max path sum of path passing through node
        current_max = left_gain + node.val + right_gain

        ans = max(ans, current_max)

        node_gain = max(left_gain, right_gain) + node.val
        return node_gain

    ending_with(root)
    return ans

Lowest Common Ancestor

Lowest Common Ancestor of a Binary Tree [LC#236]

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Code

class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def lowest_common_ancestor(root: "Node", p: "Node", q: "Node") -> "Node":
    def search(node):
        if node in [p, q, None]:
            return node
        left = search(node.left)
        right = search(node.right)
        if left and right:
            return node
        return left if left else right
    return search(root)

Time complexity

• $T(n) = O(n)$ and $S(n)= O(n)$ for the recursion stack in worst case.

If nodes are not guranteed to be in the tree

def lowest_common_ancestor(root: "Node", p: "Node", q: "Node") -> "Node":
    found = 0
    def search(node):
        nonlocal found
        if node is None: 
            return node

        if node in [p, q]:
            found += 1
            return node

        left = search(node.left)
        right = search(node.right)
        if left and right:
            return node
        return left if left else right

    node = search(root)
    if found >= 2:
        return node
    return None

Lowest Common Ancestor of a Binary Search Tree [LC#235]

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Time complexity

• $T(n) = O(n)$ and $S(n)= O(n)$ for the recursion stack in worst case.

Segment Trees

The sum of the root vertex at index 1, the sums of its two child vertices at indices 2 and 3.

class SegmentTree:
    def __init__(self, arr: List[int]):
        self.size = len(arr)
        self.tree = [0] * (4 * self.size)  # Allocate space for the segment tree
        self.build(arr, 1, 0, self.size - 1)

    def operator(self, a:int, b:int):
        return a+b

    def build(self, array: List[int], node: int, left: int, right: int):
        if left == right:
            self.tree[node] = array[left]
        else:
            mid = (left + right) // 2
            self.build(array, node * 2, left, mid)
            self.build(array, node * 2 + 1, mid + 1, right)
            self.tree[node] = self.operator(self.tree[node * 2], self.tree[node * 2 + 1])

    def query(self, node: int, left: int, right: int, query_left: int, query_right: int) -> int:
        if query_left > query_right:
            return 0
        if query_left == left and query_right == right:
            return self.tree[node]
        mid = (left + right) // 2
        return (self.sum(node * 2, left, mid, query_left, min(query_right, mid)) +
                self.sum(node * 2 + 1, mid + 1, right, max(query_left, mid + 1), query_right))

    def update(self, node: int, left: int, right: int, position: int, new_value: int):
        if left == right:
            self.tree[node] = new_value
        else:
            mid = (left + right) // 2
            if position <= mid:
                self.update(node * 2, left, mid, position, new_value)
            else:
                self.update(node * 2 + 1, mid + 1, right, position, new_value)
            self.tree[node] = self.operator(self.tree[node * 2], self.tree[node * 2 + 1])

    def range_query(self, query_left: int, query_right: int) -> int:
        return self.query(1, 0, self.size - 1, query_left, query_right)

    def point_update(self, position: int, new_value: int):
        self.update(1, 0, self.size - 1, position, new_value)

Check Completeness of a Binary Tree [LC#958]

Given the root of a binary tree, determine if it is a complete binary tree. In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Intuition

• We do a BFS of the tree. This traverses the tree level by level.
• We should not encounter a null/empty node twice before queue is empty.

Code

def is_complete_tree(root: Optional[TreeNode]) -> bool:
    queue = deque([root])
    null_found = False
    while queue:
        node = queue.popleft()
        if node:
            if null_found:
                return False
            else:
                queue.append(node.left)
                queue.append(node.right)
        else:
            null_found = True
    return True

Time complexity

• $T(n) = O(n)$
• $S(n) = O(n)$

Heap

Find Median from Data Stream [LC#295]

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Intuition

• We can easily find median if we have access to the 2 middle elements.
• The middle elements are largest of the first half and smallest of the second half if the array was sorted
• We can maintain first half of elements in a max heap and second half in min heap
• Always maintain insertion so that max heap has at most 1 value more than the min heap

Code

class MedianFinder:
    def __init__(self):
        self.low = [] # stores n or n+1 elements
        self.high = [] # stores n elements

    def add(self, num: int) -> None:
        val = heapq.heappushpop(self.low, -num)
        heapq.heappush(self.high, -val)
        if len(self.low) <  len(self.high):
            val = heapq.heappop(self.high)
            heapq.heappush(self.low, -val)

    def find_median(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0])/2

Time complexity

• $T(n) = O(\log n) $ for each insertion and median can be computed in $O(1)$ always
• $S(n) = O(n)$ for the heaps

BFS

Template

def bfs():
    queue = deque()
    seen = set()
    queue.append(start_node)
    seen.add(start_node)
    while queue:
        node = queue.popleft()
        for neigh in neighbors(node):
            if neigh not in seen:
                visit(neigh)
                queue.append(neigh)
                seen.add(neigh)

Shortest Path in Binary Matrix [LC#1091]

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix from top left to bottom right. If there is no clear path, return -1. The matrix is 8 connected and you can only move in cells marked 0.

Intuition

BFS gives the shortest path in binary matrix

Code

def shortest_path_in_binary_matrix(grid: List[List[int]]) -> int:
    n = len(grid[0])

    def neighbours(x, y):
        for dx, dy in [
            (-1, -1), (-1, +0), (-1, +1),
            (+0, -1),           (+0, +1),
            (+1, -1), (+1, +0), (+1, +1),
        ]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                yield nx, ny

    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1

    queue = deque()
    seen = set()
    queue.append((0, 0, 1))
    seen.add((0, 0))
    while queue:
        x, y, d = queue.popleft()
        if x == n - 1 and y == n - 1:
            return d
        for nx, ny in neighbours(x, y):
            if grid[nx][ny] == 0 and (nx, ny) not in seen:
                queue.append((nx, ny, d + 1))
                seen.add((nx, ny))
    return -1

Time complexity

• $T(n) = O(mn)$
• $S(n) = O(mn)$

01 Matrix [LC#542]

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two cells sharing a common edge is 1.

Intuition

BFS starting at all 0. BFS for binary graph give shortest path.

Code

def neares_zero(matrix: List[List[int]]) -> List[List[int]]:
    m = len(matrix)
    n = len(matrix[0])

    def neighbors(x, y):
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                yield nx, ny

    queue = deque()
    seen = set()

    for x in range(m):
        for y in range(n):
            if matrix[x][y] == 0:
                queue.append((x, y, 0))
                seen.add((x, y))

    while queue:
        row, col, steps = queue.popleft()
        for nx, ny in neighbors(row, col):
            if (nx, ny) not in seen:
                matrix[nx][ny] = steps + 1
                queue.append((nx, ny, steps + 1))
                seen.add((nx, ny))
    return matrix

Time complexity

• $T(n) = O(mn)$
• $S(n) = O(mn)$

All Nodes Distance K in Binary Tree [LC#863]

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node. You can return the answer in any order.

Intuition

Nodes at distance k can be children of the node or can be be children of one of the ancestors of the node. But without parent pointers searching for children on ancestors is very inefficient. So we create auxillary struture to maintain parent pointers and then perform BFS on the induced graph.

Code

def nodes_at_k_hops(root: TreeNode, target: TreeNode, k: int) -> List[int]:
    parent_node = {}

    def create_parent_node(parent, node):
        if node:
            parent_node[node] = parent
            create_parent_node(node, node.left)
            create_parent_node(node, node.right)

    create_parent_node(None, root)

    # BFS
    visited = set()
    queue = deque([(target, k)])
    answers = []
    while queue:
        node, distance = queue.popleft()
        if not node or node in visited:
            continue

        visited.add(node)

        if distance == 0:
            answers.append(node.val)
            continue

        queue.append((node.left, distance - 1))
        queue.append((node.right, distance - 1))
        queue.append((parent_node[node], distance - 1))
    return answers

Time complexity

Parent pointer creation is $O(n)$ and takes $O(n)$ space. BFS takes simlar space and time.

• $T(n) = O(n)$
• $S(n) = O(n)$

DFS

Reconstruct Itinerary [LC#332]

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”]. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Intuition

• Eulerian Path , greedy DFS

Code

def reconstruct_iternary(tickets: List[List[str]]) -> List[str]:
    # Eulerian Path , greedy DFS
    graph = defaultdict(list)
    for frm, to in sorted(tickets)[::-1]:
        graph[frm].append(to)

    stack = ["JFK"]
    ans = []
    while stack:
        while graph[stack[-1]]:
            neigh = graph[stack[-1]].pop()
            stack.append(neigh)
        node = stack.pop()
        ans.append(node)        
    return ans[::-1]

Time complexity

• $T(n) = O(E)$
• $S(n) = O(E)$

Single Source Shortest Path

Dijkstra algorithm

• graph = {u : [(v, w(u,v)), ..], ... }

def dijkstra(graph: List[List[Tuple[int, float]]], source: int) -> List[float]:
    n = len(graph)
    distances: List[float] = [math.inf] * n
    distances[source] = 0.0
    heap: List[Tuple[float, int]] = [(0.0, source)]

    while heap:
        curr_dist, node = heapq.heappop(heap)
        # if curr_dist > distances[node]:
        #     continue
        
        for neighbour, weight in graph[node]:
            dist = curr_dist + weight
            if dist < distances[neighbour]:
                distances[neighbour] = dist
                heapq.heappush(heap, (dist, neighbour))
    
    return distances

• $T(n) = O( (V+E) \log V)$
  • $O(V \log{V})$: Extract the minimum node from the heap for each vertex.
  • $O(E \log{V})$: Time taken to insert or update distances for each edge.
• $S(n) = O(V)$

Cheapest Flights Within K Stops [LC#787]

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Intuition

• Dijkstra’s single source shortest path algorithm with added constraint to update distance only if the stops are less than limit
• Can also solve with level wise BFS.

Code : Dijkstra’s

def min_distance_within_k_hops(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    graph = defaultdict(list)
    for frm, to, price in flights:
        graph[frm].append((to, price))
    dist = {src: math.inf for src in range(n)}

    dist[src] = 0
    heap = [(0, 0, src)]

    while heap:
        stops, distance, node = heapq.heappop(heap)

        for neigh, weight in graph[node]:
            if stops <= k and dist[neigh] > distance + weight:
                dist[neigh] = distance + weight
                heapq.heappush(heap, (stops + 1, dist[neigh], neigh))

    return -1 if dist[dst] == math.inf else dist[dst]

Time complexity : Dijkstra’s

• $T(n) = O(N + EK \log(EK) )$
• $S(n) = O(N + EK)$

Code : Level wise BFS

def min_distance_within_k_hops(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    graph = defaultdict(list)
    for frm, to, price in flights:
        graph[frm].append((to, price))
    dist = {src: math.inf for src in range(n)}
    dist[src] = 0
    queue = deque([(src, 0)])

    steps = 0
    while steps <= k and queue:
        level_size = len(queue)
        for _ in range(level_size):
            node, distance = queue.popleft()
            for neigh, weight in graph[node]:
                if dist[neigh] > distance + weight:
                    dist[neigh] = distance + weight
                    queue.append((neigh, dist[neigh]))
        steps += 1
    return -1 if dist[dst] == math.inf else dist[dst]

Time complexity : Level wise BFS

• $T(n) = O(N + EK)$
• $S(n) = O(N + EK)$

Bellman-Ford

def bellman_ford(graph, source):
    # Initialize distances from source to all vertices as INFINITE
    distances = {v: float("inf") for v in graph}
    distances[source] = 0  # Distance from source to itself is always 0

    # Relax all edges |V| - 1 times
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, w in graph[u]:
                if distances[u] != float("inf") and distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w

    # Check for negative-weight cycles
    for u in graph:
        for v, w in graph[u]:
            if distances[u] != float("inf") and distances[u] + w < distances[v]:
                print("Graph contains negative weight cycle")
                return None

    return distances

Minimum Spanning Tree

Kruskal’s algorithm for Minimum spanning tree

Kruskal’s algorithm is as follows.

• Go in order of lowest to highest weighted edges.
• Add edge to the graph if it doesn’t create a cycle.

@dataclass
class Edge:
    u: int
    v: int
    w: float

def kruskal_mst(num_edges: int, edges: List[Edge]) -> Tuple[List[Edge], float]:
    edges.sort(key=lambda x: x.w)
    dsu = DisjointSetUnion(num_edges)
    mst = []
    total_weight = 0

    for edge in edges:
        if dsu.find(edge.u) != dsu.find(edge.v):
            dsu.union(edge.u, edge.v) 
            mst.append(edge)
            total_weight += edge.w
            
    return mst, total_weight

• Time Complexity: $O(m \log m + n + m) = O(m \log n)$
  • $O(m \log m)$ for sorting all edges
  • $O(n)$ for make set on each edges
  • $O(m)$ for find and union on all nodes in edges
• Space Complexity: Extra space to maintaint the DSU datastructure ~ $O(n)$

Min Cost to Connect All Points [LC#1584]

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Intuition

• Generate the graph of all pairs with distance.
• The answer is MST of this graph

Code

def min_cost_connect_points(points: List[List[int]]) -> int:
    class DSU:
        def __init__(self):
            self.parent = {}
            self.rank = {}

        def find(self, node):
            if node not in self.parent:
                self.parent[node] = node
                self.rank[node] = 1

            if self.parent[node] != node:
                self.parent[node] = self.find(self.parent[node])
            return self.parent[node]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return False

            if self.rank[x] < self.rank[y]:
                x, y = y, x

            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

            return True

    def manhattan_distance(p, q):
        return abs(p[0] - q[0]) + abs(p[1] - q[1])

    dsu = DSU()
    edge_list = []
    for i in range(len(points)):
        dsu.find(i)
        for j in range(0, i):
            edge_list.append((i, j, manhattan_distance(points[i], points[j])))

    edge_list.sort(key=lambda r: r[2])
    min_cost = 0
    for i, j, d in edge_list:
        if dsu.find(i) != dsu.find(j):
            min_cost += d
            dsu.union(i, j)

    return min_cost

Time complexity

If n is number of points

• $T(n) = O(n^2) + O(n^2 \log n^2) + O(n^2)$ Constructing graph, sorting edges, mst construction.
• $S(n) = O(n^2)$

Prim’s Algorithm for Minimum spanning tree

• Start with adding a randomly choosen vertex to mst
• Find an edge such that one vertex is in the constructed mst, the other is not and the weight is smallest. Add this edge and vertex to mst
• repeat untill mst has all vertices.

@dataclass
class Edge:
    u: int
    v: int
    w: float

def prims_mst(num_vertices: int, edges: List[Edge]) -> Tuple[List[Edge], float]:
    graph = {u: [] for u in range(num_vertices)}
    for edge in edges:
        graph[edge.u].append((edge.v, edge.w))
        graph[edge.v].append((edge.u, edge.w))

    visited = [False] * num_vertices
    min_heap = [(0.0, 0)]  # (weight, vertex)
    total_cost = 0
    mst_edges = []

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total_cost += weight

        if weight > 0:  # Skip the initial vertex
            mst_edges.append(Edge(prev_vertex, u, weight))

        for v, edge_weight in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (edge_weight, v))
                prev_vertex = u  # Track the previous vertex for the edge

    return mst_edges, total_cost, all(visited)

Time Complexity

• While loop is executed n times as the MST only has n-1 edges. This give no of times heappop is called.
• The heap push is called max m times.
• $T(n) = O(n \log n + m \log n) = O((m+n) \log n)$
• $S(n) = O(n)$ for the heap

Topological Sort

Kahn’s Algorithm (BFS-like)

def topological_sort_kahn(graph: Dict[str, List[str]]) -> List[str]:
    in_degree = {u: 0 for u in graph}  # Initialize in-degrees to 0
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1  # Increment in-degree for each edge

    queue = deque([u for u in in_degree if in_degree[u] == 0])
    topological_order = []

    while queue:
        u = queue.popleft()  # Get a vertex with in-degree 0
        topological_order.append(u)  # Add it to the topological order
        
        for v in graph[u]:
            in_degree[v] -= 1  # Remove the edge u -> v
            if in_degree[v] == 0:  # If in-degree becomes 0, add to queue
                queue.append(v)

    if len(topological_order) != len(graph):
        return []
    return topological_order

Example Graph

graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['E'],
    'E': []
}

DFS like topological sort

def topological_sort_dfs(graph: Dict[str, List[str]]) -> List[str]:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    stack: List[str] = []

    def dfs(node: str) -> bool:
        if color[node] == GRAY:
            return False # Cycle detected
        if color[node] == WHITE:
            color[node] = GRAY
            for neighbor in graph[node]:
                if not dfs(neighbor):
                    # cycle in recursion
                    return False
            color[node] = BLACK
            stack.append(node)
        return True

    for vertex in graph:
        if color[vertex] == WHITE:
            if not dfs(vertex):  # If a cycle is detected
                return []

    return stack[::-1]

Find Eventual Safe States [LC#802]

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node). Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Intuition

Terminal nodes are safe nodes. Any node whose all ougoing edge are to safe nodes are also safe. We can iteratively grow the list of safe nodes this way. Essentially, topological sort on the reverse graph.

Code

def eventual_safe_nodes(graph: List[List[int]]) -> List[int]:
    n = len(graph)
    in_degree = [0] * n
    reverse_graph = [[] for _ in range(n)]
    for i in range(n):
        for node in graph[i]:
            reverse_graph[node].append(i)
            in_degree[i] += 1
    safe_nodes = []
    queue = deque([i for i in range(n) if in_degree[i]==0])
    while queue:
        node = queue.popleft()
        safe_nodes.append(node)
        for neigh in reverse_graph[node]:
            in_degree[neigh] -= 1
            if in_degree[neigh] == 0:
                queue.append(neigh)
    return sorted(safe_nodes)

Time complexity

$T(n) = $ $S(n) = $

Max Flow Min Cut

Intervals

Merge Intervals [LC#56]

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort and Itrate approach

• Sort the intervals by start time
• Iterate over the intervals one by on merging the current with the previous if there is an overlap
• $T(n) = O(n \log n + n)$; $S(n) = O(n)$

def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    intervals = sorted(intervals)
    ans = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= ans[-1][1]:
            ans[-1][1] = max(ans[-1][1], end)
        else:
            ans.append([start, end])
    return ans

Insert Interval [LC#57]

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don’t need to modify intervals in-place. You can make a new array and return it.

Intuition

Since the intervals are sorted by start time, when we loop through them in order, we will encounter 3 cases

1. The interval ends before the new interval
2. The interval overlaps with the new interval
3. The interval starts after the new interval

We handle each of the 3 cases separately

Code

@dataclass
class Interval:
    start: float
    end: float
    
def insert_interval(intervals: List[Interval], new: Interval) -> List[Interval]:
    ans = []
    for curr in intervals:
        if curr.end < new.start: # ends before
            ans.append(curr)
        elif curr.start > new.end: # begins after
            if new:
                ans.append(new)
                new = None
            ans.append(curr)
        else: # overlap
            new = Interval(
                min(curr.start, new.start), max(curr.end, new.end)
            )
    if new: # handle when intervals are empty
        ans.append(new)
    return ans

Time Complexity

• $T(n) = O(n)$

Min meeting rooms [LC#253]

Meeting Rooms II : Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Intuition

• Sort all meetings by their start time
• Keep the ending times of currently occupied meeting rooms in the min heap
• If current start time is earlier than the min heap end time, we need a new room else we can pop the top and add a new room

Code

def min_meeting_rooms(intervals: List[List[int]]) -> int:
    intervals = sorted(intervals)
    heap = [intervals[0][1]]  # first end time
    meeting_rooms = 1
    for start_time, end_time in intervals[1:]:
        if start_time >= heap[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, end_time)
        meeting_rooms = max(meeting_rooms, len(heap))
    return meeting_rooms

Time Complexity

• $T(n) = O(n \log n + n \log n)$ sorting + n pops
• $S(n) = O(n)$

Line Sweep

This is a technique where we sweep an imaginary line across the whole domain, and the line’s intersections with intervals are used to solve problems. They are particularly useful for problems where we have range updates and we need to find the final state of the array.

Say we are given queries = [(left, right, value),] implying all values in [left, right] are to be incremented by value. To quickly find the final value, we can do the following.

def apply_range_updates(queries, n):
    arr = [0]*n
    for left, right, value in queries:
        arr[left] += value
        arr[right] -= value
    prev = 0
    for i in range(n):
        prev+=arr[i]
        arr[i] = prev
    return arr

The function apply_range_updates takes the list of queries and the size of the array n, and returns the final state of the array after applying all the range updates.

Zero Array Transformation I [LC#3355]

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [li, ri]. For each queries[i]:

• Select a subset of indices within the range [li, ri] in nums.
• Decrement the values at the selected indices by 1.

A Zero Array is an array where all elements are equal to 0. Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

Intuition

The key idea is to find the maximum possible decrements that can be applied to each element in the array. If the maximum possible decrements for any element is less than the initial value of that element, then it is not possible to transform the array into a Zero Array. We can use a line sweep approach to efficiently compute the maximum possible decrements for each element.

Code

def is_zero_array(nums: List[int], queries: List[List[int]]) -> bool:
    n = len(nums)
    arr = [0] * n
    for left, right in queries:
        arr[left] += 1
        if right + 1 < n:
            arr[right + 1] -= 1

    prev = 0
    for i in range(n):
        prev += arr[i]
        if prev < nums[i]:
            return False
    return True

TimeComplexity

• $T(n) = O(n)$ and $S(n) = O(n)$

Zero Array Transformation II [LC#3356]

You are given an integer array nums of length n and a 2D array queries where queries[i] = [l_i, r_i, val_i]. Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [l_i, r_i] in nums by at most val_i.
• The amount by which each value is decremented can be chosen independently for each index. A Zero Array is an array with all its elements equal to 0. Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Intuition

Line sweep and binary search on min queries required.

Code

def minZeroArray(nums: List[int], queries: List[List[int]]) -> int:
    n, m = len(nums), len(queries)

    def apply_query(T) -> bool:
        arr = [0] * n
        for left, right, val in queries[:T]:
            arr[left] += val
            if right + 1 < n:
                arr[right + 1] -= val
        prev = 0
        for i in range(n):
            prev += arr[i]
            if prev < nums[i]:
                return False
        return True

    L, R = 0, m
    if not apply_query(m):
        return -1

    while L < R:
        mid = L + (R - L) // 2
        if apply_query(mid):
            R = mid
        else:
            L = mid + 1
    return R

TimeComplexity

If $n$ is the size of array and $m$ is number of queries, then

• $T(n) = O(n \log m)$ and $S(n) = O(n)$

Smallest Range Covering Elements from K Lists [LC#632]

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists. We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Intution

Code

def smallestRange(nums: List[List[int]]) -> List[int]:
    heap = [(arr[0], i, 0) for i, arr in enumerate(nums)]
    heapq.heapify(heap)
    right = max(arr[0] for arr in nums)
    ans = (-math.inf, math.inf)
    
    while heap:
        left, row, col = heapq.heappop(heap)
        if right - left < ans[1] - ans[0]:
            ans = left, right

        if col + 1 == len(nums[row]):
            return ans

        next_point = nums[row][col + 1]
        right = max(right, next_point)
        heapq.heappush(heap, (next_point, row, col + 1))

Time complexity

$n$ max size of lists and $m$ is number of lists

• $T(n) = O(n \log m)$. $S(n) = O(m)$

Minimum Number of Arrows to Burst Balloons [LC#452]

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Intuition: Greedy Approach

• This problem is about find min vertical lines intersecting a given set of intervals.
• We pick an interval as a root interval. Any interval intersecting with this one can all be taken out by a single arrow.
• To find minimum such sets, we sort the interval by ending time, pick first interval as root, and find the intesecting intervals to it by checking the ones whose start time is earlier.
• Iteratively we can find all such combinations.

Code

def min_arrows(balloons: List[List[int]]) -> int:
    if not balloons:
        return 0
    balloons.sort(key = lambda r: r[1])
    end_location = balloons[0][1]
    num_arrows = 1
    for balloon in balloons:
        if balloon[0] > end_location:
            end_location = balloon[1]
            num_arrows +=1
    return num_arrows

Time complexity

Time complexity is domniated by sorting. $T(n) = O(n \log n) + O(n)$ , $S(n) = O(1)$

Monotonic Stack

A monotonic decreasing stack is a data structure based on a stack. While traversing an array, it maintains a sorted list of elements encountered so far that are strictly greater than or equal to the current element being processed. It upholds this property by continuously removing elements from the top of the stack that violate the requirement (i.e., elements that are less than the current element).

stack = []
for num in nums:
    while stack and stack[-1] <= num:
        stack.pop()
    stack.append(num)
    # stack[-1] > stack[-2] > ... > stack[0]

Although a monotonic stack can be used to solve problems that require finding previous smaller (or larger) elements from the stack, a more interesting use is to exploit the interim states of the monotonic stack while it updates itself to maintain the property of monotonicity. Ex.

stack = []
arr.append(-math.inf) # to ensure all elements are processed
for idx range(len(arr)):
    while stack and arr[stack[-1]] <= arr[idx]:
        mid = stack.pop()
        left = -1 if not stack else stack[-1]
        right = idx
        # do something with arr[left] > a[mid] < a[right]
    stack.append(idx)

References

• https://labuladong.gitbook.io/algo-en/ii.-data-structure/monotonicstack
• https://leetcode.com/discuss/study-guide/2347639/A-comprehensive-guide-and-template-for-monotonic-stack-based-problems

Largest Rectangle in Histogram [ LC# 84]

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Brute Force

• Enumerate every range. Compute the Area
• $T(n) = O(n^2)$; $S(n) = O(n^2)$

area[i][j] = min_heights[i:j] * ( j-i+1 )
min_heights[i:j] = min(min_heights[i-1:j-1], heights[i], heights[j])
min_heights[i:i] = heights[i]

Intuition: Monotonic Stack

• If we are at a rectangle of height $h$ and we are interested in finding the largest rectangle with minimum height $h$ in the histogram. We can extend the rectangle to both the sides till we encounter a height that is smaller.
• If we trasverse the histogram from left to right and maintain a non-decreasing monotonic stack, it will have all these states that we need.

           ┌─┐         ┌─┐    
       ┌─┐ │ │       ┌─┤ │    
   ┌─┐ │ ├─┤ │     ┌─┤ │ │    
   │ ├─┤ │ │ │   ┌─┤ │ │ │    
   │ │ │ │ │ │...│h│ │ │ ├─┐   
 ┌─┤ │ │ │ │ │   │ │ │ │ │ │   
 └─┴─┴─┴─┴─┴─┘   └─┴─┴─┴─┴─┘   
   └─────────────────────┘                
┌─┴──┐          ┌─┴─┐  ┌──┴──┐
 left            mid    right

Code

def largest_rectangle_in_historgam(heights: List[int]) -> int:
    stack = [-1] # monotonic stack : non decreasing order
    max_area = 0
    
    heights.append(0)
    for i in range(len(heights)):
        while stack and heights[stack[-1]] > heights[i]:
            mid = stack.pop()
            left = stack[-1] + 1
            right = i
            max_area = max(max_area,  heights[mid] * (right - left))
        stack.append(i)
    return max_area

Time complexity

• $T(n) = O(n)$; $S(n) = O(n)$

Sum of Subarray Minimums [LC#907]

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo $10^9 + 7$.

Intuition

If arr[k] is minimum element in [i, j], then arr[k] appears in (k - i) * (j - k) subarrays.

Monotonic Stack

def sum_subarrray_mins(arr: List[int]) -> int:
    stack = []
    sum_of_minimums = 0
    arr.append(-math.inf) # so that everything gets popped out in the end
    for i in range(len(arr)):
        while stack and arr[stack[-1]] >= arr[i]:
            mid = stack.pop()
            left = -1 if not stack else stack[-1]
            right = i

            count = (mid - left) * (right - mid)
            sum_of_minimums += (count * arr[mid])
        stack.append(i)
    return sum_of_minimums

Time Complexity

• $T(n) = O(n)$ ; $S(n) = O(n)$

Daily Temperatures [LC#739]

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Intuition

We have to fine the next largest in the array for every element.

Code

def next_warmer_day(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    stack = []
    answers = [0] * n
    for i in range(n - 1, -1, -1):
        while stack and temperatures[stack[-1]] <= temperatures[i]:
            stack.pop()
        if stack:
            answers[i] = stack[-1] - i
        stack.append(i)
    return answers

OR

def next_warmer_day(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    stack = []
    answers = [0] * n
    for curr_day in range(n):
        while stack and temperatures[stack[-1]] < temperatures[curr_day]:
            prev_day = stack.pop()
            answers[prev_day] = curr_day - prev_day
        stack.append(curr_day)
    return answers

Note the different comparison signs between 2 implementation

Time Complexity

• $T(n) = O(n)$ ; $S(n) = O(n)$

Tries

Word break [LC#139]

Given a string and a vocabulary, return true if the string can be segmented into a space-separated sequence of one or more words from the vocabulary. Note that the same word in the vocabulary may be reused multiple times in the segmentation.

Intuition

• Use a Trie for efficient prefix searching.
• Use a boolean array reachable to track if substrings can be segmented.
• From each reachable index, use the trie search to find more reachable index
• Return reachable[n] to determine if the entire string can be segmented.

Code

def word_break(string: str, vocabulary: List[str]) -> bool:
    n = len(string)
    TRIE = {}
    EOW = "$"
    for word in vocabulary:
        if len(word) > n:
            continue
        node = TRIE
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node[EOW] = ""

    reachable = [False] * (n + 1)
    reachable[0] = True

    for i in range(n + 1):
        if reachable[i]:
            node = TRIE
            j = i
            while j < n:
                if string[j] not in node:
                    break
                node = node[string[j]]
                if EOW in node:
                    reachable[j + 1] = True
                j += 1

    return reachable[n]

Time complexity

n = len(string), m = len(vocabulary), k = max(len(word) in vocabulary)

• $T(n) = O(mk) + O(nk)$ trie construction and search
• $S(n) = O(mk) + O(n)$ trie and reachable

Permutations

Next Permutation [LC#31]

Given an array of integers nums, find the next permutation of nums.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

Intuition

• [Step 1] Find the largest i such that nums[i] < nums[i+1]. If no such index exists, then this is the last sequence in the permutation. Reset array to sorted order (first element in the sequence).
• [Step 2] Find the largest index j > i such that nums[i] < nums[j]. Swap these 2 numbers
• [Step 3] Reverse the array from i+1 till the end.

Code

    def next_permutation(self, nums: List[int]) -> List[int]:
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]

        def reverse(start, end):
            nums[start : end + 1] = nums[start : end + 1 : -1]

        n = len(nums)
        # Step 1
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
            
        if i >= 0:
            # Step 2
            j = n - 1
            while nums[i] >= nums[j]:
                j -= 1
            swap(i, j)
        
        # Step 3
        reverse(i + 1, n - 1)
        return nums

Time complexity

• $T(n) = O(n)$
• $S(n) = O(1)$

Permutation Sequence [LC#60]

The set [1, 2, 3, ..., n] contains a total of n! unique permutations. Given n and k, return the kth permutation sequence.

Intuition

• Let $F$ be the factorial number system representation of the number $k$ for the base $n$. Indexing of $k$ starts from $0$.
• For each digit $f$ in $F$, select the $f^{th}$ digit from the set of numbers and add it to the answer. After selecting, remove that digit from set.
• Example:
  • For $n=6$, $2982 = 4:0:4:1:0:0:0_!$ so the permutation is $(4,0,6,2,1,3,5)$
• Reference
  • Factorial Number System

Code

def kth_permutation(n: int, k: int) -> str:
    factorials = [1]
    digits = ["1"]
    for i in range(1, n):
        factorials.append(factorials[-1] * i)
        digits.append(str(i + 1))

    output = []
    k -= 1
    for i in range(n - 1, -1, -1):
        # index = k // factorials[i]
        # k = k - idx * factorials[i]
        index, k = divmod(k, factorials[i])
        output.append(digits[index])
        del digits[index]
    return "".join(output)