Arrays

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.

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)

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

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

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

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)

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

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

Split Array Largest Sum [LC#412]

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split. A subarray is a contiguous part of the array.

Intuition

Binary search on the range of possible values.

Code

def splita_array_largest_sum(nums: List[int], k: int) -> int:
    left, right = max(nums), sum(nums)

    def valid(th):
        num_partitions = 0
        sum_partition = 0
        for num in nums:
            if sum_partition + num <= th:
                sum_partition += num
            else:
                sum_partition = num
                num_partitions += 1
            if num_partitions >= k:
                return False
        return True

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

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

Swim in Rising Water [LC#778]

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j). The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Intuition

• Solution is a path from source to target with least maximum elevation.
• Binary search on all possible paths
• BFS or DFS can be used interchangeably

Code

def swim_in_water(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

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

    def bfs_with_limit(limit):
        queue = deque([(0, 0)])
        seen = {(0, 0)}
        while queue:
            row, col = queue.popleft()
            if (row, col) == (m - 1, n - 1):
                return True
            for nx, ny in neighbours(row, col):
                if (nx, ny) not in seen and grid[nx][ny] <= limit:
                    queue.append((nx, ny))
                    seen.add((nx, ny))
        return False

    lo, hi = grid[0][0], max(max(grid[i]) for i in range(m))

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if bfs_with_limit(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Time complexity

• $T(n) = O(\log(2^b) mn) = O(mn)$
• $S(n) = O(mn)$

Monotonic Stack

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

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

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

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

References

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

Largest Rectangle in Histogram [ LC# 84]

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

Brute Force

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

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

Intuition: Monotonic Stack

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

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

Code

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

Time complexity

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

Sum of Subarray Minimums [LC#907]

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

Intuition

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

Monotonic Stack

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

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

Time Complexity

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

Daily Temperatures [LC#739]

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

Intuition

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

Code

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

OR

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

Note the different comparison signs between 2 implementation

Time Complexity

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

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
  

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

  )$

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

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.

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

Intervals

Merge Intervals [LC#56]

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

Sort and Itrate approach

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

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

Insert Interval [LC#57]

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

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

Return intervals after the insertion.

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

Intuition

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

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

We handle each of the 3 cases separately

Code

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

Time Complexity

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

Min meeting rooms [LC#253]

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

Intuition

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

Code

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

Time Complexity

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

Line Sweep

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

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

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

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

Zero Array Transformation I [LC#3355]

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

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

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

Intuition

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

Code

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

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

TimeComplexity

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

Zero Array Transformation II [LC#3356]

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

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

Intuition

Line sweep and binary search on min queries required.

Code

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

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

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

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

TimeComplexity

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

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

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

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

Intution

Code

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

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

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

Time complexity

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

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

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

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

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

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

Intuition: Greedy Approach

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

Code

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

Time complexity

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

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)

        # 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, left_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 traverse(node):
        nonlocal found
        if node is None: return node

        left = traverse(node.left)
        right = traverse(node.right)

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

        if right and left:
            return node
        return left if left else right

    node = traverse(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)