CommonAlgorithms.md

Common Algorithms

For leetcode problems, the Python3 Solutions are published in jupyter notebook (still in progress). Check out more in Jupyter nbviewer.

Here, I summarized top common algorithms to deal with classic leetcode problems.

Binary Search

1. Search for exact match
   • 349. Intersection of Two Arrays
   • 350. Intersection of Two Arrays II
2. Search for position to insert
   • Patience Sorting
   • 300. Longest Increasing Subsequence
   • 354. Russian Doll Envelopes
   • 363. Max Sum of Rectangle No Larger Than K
   • 367. Valid Perfect Square
   • 441. Arranging Coins
   • 475. Heaters
   • 611. Valid Triangle Number
3. Sub-function (hard)
   • 410. Split Array Largest Sum
   • 774. Minimize Max Distance to Gas Station
   • 875. Koko Eating Bananas
   • 1011. Capacity To Ship Packages In N Days
   • 1231. Divide Chocolate
   • 1283. Find the Smallest Divisor Given a Threshold

Tree

1. Post-order Traversal Tree Problems
   • 124. Binary Tree Maximum Path Sum
   • 250. Count Univalue Subtrees
   • 298. Binary Tree Longest Consecutive Sequence
   • 508. Most Frequent Subtree Sum
   • 543. Diameter of Binary Tree
   • 549. Binary Tree Longest Consecutive Sequence II
   • 687. Longest Univalue Path
   • 1245. Tree Diameter
   • Max Path Sum in a Grid
   • Maximum number of unique prime factors
2. Segment Tree / Binary Indexed Tree (Fenwick Tree)
3. Morris Tree Traversal

Graph

1. Disjoint Sets (Union Find)
   • 200. Number of Islands
   • 947. Most Stones Removed with Same Row or Column
2. Shortest Paths Problems
   • Dijkstra
     • 787. Cheapest Flights Within K Stops
     • 1162. As Far from Land as Possible
   • Floyd-Warshall
   • Bellman-Ford
   • SPFA
     • 1162. As Far from Land as Possible
   • BFS
     • 365. Water and Jug Problem
     • 994. Rotting Oranges
     • 1162. As Far from Land as Possible
   • Bidirectional
     • 127. Word Ladder
     • 126. Word Ladder II
     • 433. Minimum Genetic Mutation
   • Multisource BFS
     • 317. Shortest Distance from All Buildings
     • 1162. As Far from Land as Possible
3. Kahn's Algorithm - Topological sorting
   • 207. Course Scheduling
   • 310. Minimum Height Trees
   • 1203. Sort items by groups respecting dependencies
4. Cycle Detection Algorithms
   • Tricolor DFS
     • 785. Is Graph Bipartite?
     • 802. Find Eventual Safe States
     • 1059. All Paths from Source Lead to Destination
   • Floyd's Tortoise and Hare
5. DFS
   • 365. Water and Jug Problem
6. Tarjan's algorithm
   Strongly Connected Components (SCC)
   • 928. Minimize Malware Spread II
   • 1192. Critical Connections in a Network
7. Kruskal's Algorithm
8. Maze router Problems
   • Lee algorithm
9. Euler Path (Hierholzer's algorithm)
   • 332. Reconstruct Itinerary

Dynamic Programming

1. Permutations and Combinations
   • 31. Permutation
   • 46. Permutations
   • 47. Permutations II
   • 60. Permutation Sequence
   • 78. Subsets
   • 90. Subsets II
   • 1255. Maximum Score Words Formed by Letters
   • 1286. Iterator for Combination
2. Classic DP
   • 256. Paint House
   • 265. Paint House II
   • 276. Paint Fence
   • 887. Super Egg Drop
   • 1411. Number of Ways to Paint N × 3 Grid
3. Knapsack problem
   1. 0/1 Knapsack
      • 416. Partition Equal Subset Sum
      • 871. Minimum Number of Refueling Stops
   2. Complete Knapsack
      • 279. Perfect Squares
      • 322. Coin Change
      • 377. Combination Sum IV
      • 518. Coin Change 2
4. Kadane's algorithm (DP approach to solve the largest contiguous elements in an array)
   • 53. Maximum Subarray
   • 978. Longest Turbulent Subarray
   • 1186. Maximum Subarray Sum with One Deletion
   • 1191. K-Concatenation Maximum Sum
5. Two-dimensional DP
   • LIS series
     • 300. Longest Increasing Subsequence
     • 491. Increasing Subsequences
   • LCS series
     • 1143. Longest Common Subsequence
     • 1092. Shortest Common Supersequence - SCS
     • 516. Longest Palindromic Subsequence
     • 1216. Valid Palindrome III
     • 72. Edit Distance
     • 673. Number of Longest Increasing Subsequence
   • Palindromic Substring Other Solution: Middle-to-two-ends / Manacher
     • 5. Longest Palindromic Substring
     • 214. Shortest Palindrome
     • 647. Palindromic Substrings
6. Game Theory Other Solution: MinMax
   • 292. Nim Game
   • 464. Can I Win
   • 486. Predict the Winner
   • 1025. Divisor Game
   • 877. Stone Game
   • 1140. Stone Game II
   • 5 Pirates and 100 Gold Coins
   • LintCode 394. Coins in a Line
   • LintCode 395. Coins in a Line II

Misc

1. Interval Scheduling
   Solution: Greedy / Boundary Counting
   • 56. Merge Intervals
   • 252. Meeting Rooms
   • 253. Meeting Rooms II
   • 435. Non-overlapping Intervals
   • 452. Minimum Number of Arrows to Burst Balloons
   • 57. Insert Interval
   • 352. Data Stream as Disjoint Intervals
   • 436. Find Right Interval
   • 616. Add Bold Tag in String
   • 636. Exclusive Time of Functions
   • 646. Maximum Length of Pair Chain
   • 699. Falling Squares
   • 715. Range Module
   • 729. My Calendar I
   • 731. My Calendar II
   • 732. My Calendar III
   • 759. Employee Free Time
   • 986. Interval List Intersections
   • 1109. Corporate Flight Bookings
   • 1235. Maximum Profit in Job Scheduling
   • 1288. Remove Covered Intervals - Boundary Counting doesn't work?
2. Sliding window
   • Easy
     • 643. Maximum Average Subarray I
   • Hard
     • 727. Minimum Window Subsequence
     • 904. Fruit Into Baskets
     • 992. Subarrays with K Different Integers
     • 1234. Replace the Substring for Balanced String
   • Substring search Template
     • 3. Longest Substring Without Repeating Characters
     • 30. Substring with Concatenation of All Words
     • 76. Minimum Window Substring
     • 159. Longest Substring with At Most Two Distinct Characters
     • 340. Longest Substring with At Most K Distinct Characters
     • 438. Find All Anagrams in a String
3. PreSum
   • Easy
     • 53. Maximum Subarray
     • 643. Maximum Average Subarray I
4. Stack
   1. Monotonic stack
      • 42. Trapping Rain Water
      • 84. Largest Rectangle in Histogram
      • 581. Shortest Unsorted Continuous Subarray
      • 739. Daily Temperatures
   2. RPN (Reversed Polish Notation)
      • 224. Basic Calculator
      • 227. Basic Calculator II
      • 772. Basic Calculator III
      • 770. Basic Calculator IV - Hard
   3. Good stack problems
      • 388. Longest Absolute File Path
      • 496. Next Greater Element I
      • 503. Next Greater Element II
      • 636. Exclusive Time of Functions
      • 856. Score of Parentheses
      • 901. Online Stock Span
      • 907. Sum of Subarray Minimums
      • 1111. Maximum Nesting Depth of Two Valid Parentheses Strings
      • 1130. Minimum Cost Tree From Leaf Values
5. Bit Operation
   • 137. Single Number II
   • 318. Maximum Product of Word Lengths
6. Sieve of Eratosthenes
   • 204. Count Primes
   • Number which has the maximum number of distinct prime factors in the range M to N
7. Integer Factorization
8. Fourier Transform
9. Modulo Arithmetic
10. Link Analysis
11. Reservoir Sampling
12. Boyer-Moore Majority Vote algorithm
13. Bézout's identity (GCD)
    • 365. Water and Jug Problem
    • 1250. Check If It Is a Good Array
14. Euclidean
    • 780. Reaching Points
15. SLR(1)
    • 282. Expression Add Operators
16. DFA - Deterministic Finite Automaton
    • 10. Regular Expression Matching
    • 65. Valid Number
17. Round Robin
    • 68. Text Justification Use case: Find the majority element in a list of values. Check this article.
    • 169. Majority Element
    • 229. Majority Element II
    • 1150. Check If a Number Is Majority Element in a Sorted Array
    • 1157. Online Majority Element In Subarray

Tricky Solutions

* [65. Valid Number]() - DFA
* [136. Single Number]() - XOR
* [240. Search a 2D Matrix II]() - Start from Right-top Corner

String

1. TBD