Skip to content

Algorithm Examples

Kadanes Algo

Max Subarray

Can be solved using Kadane's algorithm in linear time and without using additional space. The main ideas are:

  • Use the input vector nums to store the candidate subarrays sum (i.e. the greatest contiguous sum so far).
  • Ignore cumulative negatives, as they don't contribute positively to the sum.

Example: Given nums = [-2, 1, -3, 4]. Compare all elements with the cumulative sum stored in the previous index.

  1. Since -2 < 0, value -2 doesn't contribute to the sum. Thus, ignore it and proceed to the next index.
  2. Since 1 > 0, value 1 does contribute. Hence, compute -3+1 = -2 and store it in index 2.
  3. The result vector is so far: [-2, 1, -2, 4]. Last element to evaluate is 4.
  4. Since -2 < 0, -2 does not contribute positively to the sum. Thus, ignore it.
  5. Having checked all elements, the final result vector is: [-2, 1, -2, 4].
  6. The maximum subarray is max(num)=4.
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i - 1] > 0: 
                nums[i] += nums[i - 1] return max(nums

Intro
Binary Search is quite easy to understand conceptually. Basically, it splits the search space into two halves and only keep the half that probably has the search target and throw away the other half that would not possibly have the answer. In this manner, we reduce the search space to half the size at every step, until we find the target. Binary Search helps us reduce the search time from linear O(n) to logarithmic O(log n). But when it comes to implementation, it's rather difficult to write a bug-free code in just a few minutes. Some of the most common problems include:

When to exit the loop? Should we use left < right or left <= right as the while loop condition? How to initialize the boundary variable left and right? How to update the boundary? How to choose the appropriate combination from left = mid, left = mid + 1 and right = mid, right = mid - 1? A rather common misunderstanding of binary search is that people often think this technique could only be used in simple scenario like "Given a sorted array, find a specific value in it". As a matter of fact, it can be applied to much more complicated situations.

After a lot of practice in LeetCode, I've made a powerful binary search template and solved many Hard problems by just slightly twisting this template. I'll share the template with you guys in this post. I don't want to just show off the code and leave. Most importantly, I want to share the logical thinking: how to apply this general template to all sorts of problems. Hopefully, after reading this post, people wouldn't be pissed off any more when LeetCoding, "This problem could be solved with binary search! Why didn't I think of that before!"

Most Generalized Binary Search
Suppose we have a search space. It could be an array, a range, etc. Usually it's sorted in ascending order. For most tasks, we can transform the requirement into the following generalized form:

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

The following code is the most generalized binary search template:

def binary_search(array) -> int:
  def condition(value) -> bool:
    pass (1)

  left, right = min(search_space), max(search_space) #could be [0, n], [1, n] etc. Depends on prob
  while left < right:
    mid = left + (right - left) // 2
    if condition(mid):
      right = mid
    else:
      left = mid + 1
  return left

What's really nice of this template is that, for most of the binary search problems, we only need to modify three parts after copy-pasting this template, and never need to worry about corner cases and bugs in code any more:

  • Correctly initialize the boundary variables left and right to specify search space. Only one rule: set up the boundary to include all possible elements
  • Decide return value. Is it return left or return left - 1? Remember this: after exiting the while loop, left is the minimal k satisfying the condition function
  • Design the condition function. This is the most difficult and most beautiful part. Needs lots of practice.

Basic Application

278. First Bad Version [Easy]

You are a product manager and currently leading a team to develop a new product. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

First, we initialize left = 1 and right = n to include all possible values. Then we notice that we don't even need to design the condition function. It's already given by the isBadVersion API. Finding the first bad version is equivalent to finding the minimal k satisfying isBadVersion(k) is True. Our template can fit in very nicely:

class Solution:
    def firstBadVersion(self, n) -> int:
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

Binary Tree

let length(a,b) = number of edges between nodes a, b our objective is to maximize the diameter = maximize path length between two nodes

intuition: recognize that the longest path must include two leaf nodes, towards contradiction suppose longest path of length L starts at node a and ends at node b, we can increase this path by including children of a and b

standard tree question format: 

def solution(self, root):
    def solve(root):
        if not root:
            # do something
        solve(root.left)
        solve(root.right)
        return # something
    solve(root)
    return # something

Start by looking at simplest tree case with 1 leaf node (written as [1]), diameter is 0 Next simplest tree case with parent node 1 and two children 2, 3 (written as [1,2,3], diameter is 2

We are trying to maximize some variable so lets keep track of it as self.diameter At node A we care about my left child's longest path to leaf (lclp2l) and my right child's longest path to leaf (rclp2l), if I add the two then I get the diameter which is "centered" on node A

The only information we still need is lclp2l and rclp2l, in recursion we return to pass information up the tree

Assume we're at node V somewhere in the tree and that V is the left child of its parent node P, then by returning max(lclp2l, rclp2l) + 1 node P will know what the longest path in the tree (such that the path goes through node V and ends at a leaf) is from its left child, it will get the same information from its right child and update self.diameter in case the sum of those two lengths is larger

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0

        def dfs(node):
            if not node:
                # my parent is a leaf (and the leaf base case has diameter = 0)
                return 0 

            # len(longest path from r.left/right to some leaf)
            lclp2l, rclp2l = dfs(node.left), dfs(node.right) 

            # diameter including this node is # edges on left path + #E(right)
            d = lclp2l + rclp2l
            self.diameter = max(d, self.diameter)

            # tell my parent the length of the longest path to a leaf that goes through me
            # this is just the maximum of the same problem but for each of my children and +1  
            #  to include the edge from me to the longest child 
            return max(lclp2l, rclp2l) + 1     
        dfs(root)
        return self.diameter