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

Edit Distance [LC#72]

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Intuition

Let cost[i][j] is the minimum edit distance (or the minimum number of operations) required to transform the first i characters of word1 into the first j characters of word2.

Dynamic Programming

def edit_distance(word1: str, word2: str) -> int:
    # Define the costs for operations
    costs = {'insert': 1, 'delete': 1, 'substitute': 1}
    m, n = len(word1), len(word2)
    
    cost = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize the first row and column
    for i in range(m + 1):
        # Cost of deleting all characters from word1 to form word2
        cost[i][0] = i  * costs['delete']
    for j in range(n + 1):
        # Cost of inserting all characters to word1 to form word2
        cost[0][j] = j  * costs['insert']

    # Fill the cost matrix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                cost[i][j] = cost[i - 1][j - 1]  # No operation needed
            else:
                cost[i][j] = min(
                    cost[i - 1][j] + costs['insert'],      # Insert
                    cost[i][j - 1] + costs['delete'],      # Delete
                    cost[i - 1][j - 1] + costs['substitute']  # Substitute
                )
    return cost[m][n]

• $T(n) = O(mn)$
• $S(n) = O(mn)$ but can be optimised to $O(\min(m,n))$

Parentheses matching

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)$

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

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)$

Distinct Subsequences [LC#115]

Given two strings s and t, return the number of distinct subsequences of s which equals t.

Intuition

Code

def distinct_subsequences(s: str, t: str) -> int:
    m = len(s) # i
    n = len(t) # j
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        if s[i] == t[0]:
            dp[i][0] = 1

    for j in range(1, n):
        running_sum = dp[0][j - 1]
        for i in range(1, m):
            if s[i] == t[j]:
                # dp[i][j] = sum(dp[k][j - 1] for k in range(i))
                dp[i][j] = running_sum
            running_sum += dp[i][j - 1]

    return sum(dp[i][n - 1] for i in range(m))

OR
def distinct_subsequences(s: str, t: str) -> int:
    m = len(s) # i
    n = len(t) # j
    dp = [[0] * (n+1) for _ in range(m+1)]

    dp[0][0] = 1

    for i in range(1, m+1):
        dp[i][0] = 1
        for j in range(1, n+1):
            dp[i][j] = dp[i-1][j]
            if s[i-1] == t[j-1]:
                dp[i][j] += dp[i-1][j - 1]
    return dp[m][n]

Time complexity

• $T(n) = O(mn)$
• $S(n) = O(mn)$ but can be space optimised to $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

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]