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.

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
  

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

Binary Search

Minimize k , s.t. condition(k) is True

  [ f ][ f ][ f ][ t ][ t ][ t ][ t ][ t ]     
                   └── ans 

• Set up the boundary to include all possible elements

def binary_search(search_space) -> int:
    left, right = min(search_space), max(search_space)
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left

Binary search in a sorted array

  [      <      ][ = ][      >      ]                            

def binary_search_array(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left if arr[left] == target else -1

Find First and Last Position of Element in Sorted Array [LC#34]

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

Code

def searchRange(nums: List[int], target: int) -> Tuple[int, int]:
    def binary_search(value):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] >= value:
                right = mid
            else:
                left = mid + 1
        return left

    nums.append(math.inf) # to handle edge cases

    pos_beg = binary_search(target)
    if nums[pos_beg] != target:
        return (-1, -1)
    pos_end = binary_search(target + 1)
    return (pos_beg, pos_end - 1)

Time Complexity

$T(n) = O(\log n)$

Find Minimum in Rotated Sorted Array [LC#153]

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Intuition

minimum number is present in the smallest index k such that nums[k] < nums[-1]

Code

def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= nums[-1]:
            right = mid
        else:
            left = mid + 1
    return nums[left] 

Minimum Limit of Balls in a Bag [LC#1760]

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer max_operations. You can perform the following operation at most max_operations times:

• Take any bag of balls and divide it into two new bags with a positive number of balls. For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations. Return the minimum possible penalty after performing the operations.

Intuition

Binary search on penalty.

Code

def minimum_size(nums: List[int], max_operations: int) -> int:
    def valid(th):
        count = 0
        for num in nums:
            operations = math.ceil(num / th) - 1
            count += operations
            if count > max_operations: return False
        return True
    
    left, right = 1, max(nums)

    while left < right:
        mid = left + (right - left) // 2
        if valid(mid):
            right = mid
        else:
            left = mid + 1
    return left

Time Complexity

The search take log(range) steps. The range is of size $2^b$ if $b$ is max number of bits representing the numbers in the list nums. Hence number of search steps is upperbounded by $\log (2^b) = b$. Each step take $O(n)$ to evaluate the validity condition. So time complexity $T(n) = O(b \ast n)$. If we consider $b$ as a constant then time complexity is $O(n)$

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[i]:
        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)$

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

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

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[i][0] = i  # Cost of deleting all characters from word1 to form word2
    for j in range(n + 1):
        cost[0][j] = j  # Cost of inserting all characters to word1 to form word2

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

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

Time Complexity

• $T(n) = O(n^2)$
• $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

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
  

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

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

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

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

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

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)

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

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

        ans = max(ans, current_max)
        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.

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)

Graphs

BFS

DFS

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 []  # 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]

Connected Components

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

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

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

Max Flow Min Cut

Sets

Subsets II [LC#90]

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Intuition

• Consider elements with duplicate as 1 element
• when we need to add this element to subset, we add it once per each frequency
• $T(n) = O(2^n)$; $S(n) = O(2^n)$

def subsets_of_multiset(nums: List[int]) -> List[List[int]]:
    powerset = [[],]
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1

    for num, num_freq in freq.items():
        curr = []
        for subset in ans:
            for ff in range(1, num_freq + 1):
                new_subset = subset + [num] * ff
                curr.append(new_subset)
        powerset.extend(curr)
    return powerset

DSU Union-Find

class DSU:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, x):
        if x not in self.parent:
            # new node
            self.parent[x] = x
            self.rank[x] = 0
            
        if self.parent[x] != x:
            # path compression
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

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

        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x 

        self.parent[root_y] = root_x

        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True

The Earliest Moment When Everyone Become Friends [LC#1101]

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestamp i.

Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b.

Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return -1.

Intuition

Since the friendship is symetric, wheever two people become friends, we can merge their acquaintance sets togethere. When there is only 1 such sets, everyone is aquainted. For finding earliest time, we simply go through the logs in chronological order.

Code

def earliestAcq(self, logs: List[List[int]], n: int) -> int:
    dsu = DSU()
    for i in range(n):
        dsu.find(i)
    for timestamp, x, y in sorted(logs):
        if dsu.union(x, y):
            if dsu.components == 1:
                return timestamp
    return -1

Time Complexity

$T(n) = O(n)$ since union is $O(\alpha(n))$. $S(n) = O(n)$

DSU with Rollbacks

• We do not add path compression as addition of roll back will results in unnecessary operations. This results in O(log n) for find (due to merge by rank)

class DSU_rollback:
    def __init__(self):
        self.parent = {}
        self.rank = {}
        self.history = []

    def find(self, v):
        if v not in self.parent:
            self.parent[v] = v
            self.rank[v] = 0
      
        if v == self.parent[v]:
            return v
        # self.parent[v] = self.find(self.parent[v])
        # We don't perform path compression
    
        return self.find(self.parent[v])

    def union(self, v, u):
        v = self.find(v)
        u = self.find(u)
        if v == u:
            return False
        if self.rank[v] > self.rank[u]:
            v, u = u, v
        
        self.history.append((v, self.rank[v], u, self.rank[u]))
        
        self.parent[v] = u
        if self.rank[v] == self.rank[u]:
            self.rank[u] += 1
        return True

    def rollback(self):
        if not self.history:
            return
        v, rank_v, u, rank_u = self.history.pop()
        self.parent[v] = v
        self.rank[v] = rank_v
        self.parent[u] = u
        self.rank[u] = rank_u