dsa1 min read
Split Array Largest Sum — Binary Search on Answer
Minimize the largest subarray sum when splitting into k parts using binary search on the possible answer range.
Read →
Dp
17 articles
dsa2 min read
Longest Arithmetic Subsequence — DP + Hash Map per Index
Find the longest arithmetic subsequence using dp[i][diff] = length ending at index i with given difference.
Read →
dsa1 min read
Jump Game VI — DP + Monotonic Deque
Maximize score jumping through an array with window k by combining DP with a monotonic decreasing deque.
Read →
dsa2 min read
Unique Binary Search Trees II
Generate all structurally unique BSTs with values 1 to n using divide and conquer with memoization.
Read →
dsa2 min read
House Robber III
Maximize robbery from a tree-structured neighborhood where adjacent (parent-child) nodes cannot both be robbed.
Read →
dsa3 min read
Kth Ancestor of a Tree Node
Find the Kth ancestor of any tree node in O(log k) per query using binary lifting (sparse table DP).
Read →
dsa2 min read
Unique Binary Search Trees
Count the number of structurally unique BSTs with n nodes using Catalan numbers and DP.
Read →
dsa3 min read
Subset Sum and Partition DP: Backtracking vs DP
Compare backtracking and DP approaches for subset sum: when to use each, conversion to knapsack, and bitset optimization.
Read →
dsa3 min read
Probability and Expected Value in Competitive Programming
Apply probability theory and expected value DP to competitive programming: dice problems, random walks, and geometric distribution.
Read →
dsa2 min read
Floyd-Warshall — All-Pairs Shortest Path
Compute shortest paths between all pairs of vertices using Floyd-Warshall's O(V³) DP. Handles negative weights and detects negative cycles.
Read →
dsa2 min read
Bellman-Ford — SSSP with Negative Edges and Cycle Detection
Compute single-source shortest paths in graphs with negative weight edges using Bellman-Ford. V-1 relaxation passes detect negative cycles on the Vth pass.
Read →
dsa2 min read
Number of Ways to Arrive at Destination — Dijkstra + Count
Count the number of shortest paths from source to destination using modified Dijkstra that tracks both minimum distance and path count simultaneously.
Read →
dsa2 min read
Longest Path in DAG — Graph DP with Memoisation
Find the longest path in a directed acyclic graph using DFS with memoisation. Since cycles are absent, DFS never revisits nodes, making top-down DP straightforward.
Read →
dsa2 min read
Longest Common Substring — DP and Rolling Hash Approaches
Find the longest common substring between two strings. DP approach O(nm), binary search + rolling hash O((n+m) log(n+m)).
Read →
dsa2 min read
String DP — Edit Distance, LCS, and Interleaving
Core string DP patterns: edit distance (Wagner-Fischer), longest common subsequence, interleaving strings, and regular expression matching.
Read →
dsa2 min read
Palindrome Problems — Expand Around Centre, DP, and Manacher
Comprehensive palindrome problem coverage: valid palindrome check, longest palindromic substring (three methods), count palindromic substrings, and palindrome partitioning.
Read →
dsa2 min read
Google — Word Break II (DP + Backtracking with Memoisation)
Return all ways to segment a string into dictionary words. Combines DP validity check with DFS+memo backtracking to avoid TLE on valid inputs.
Read →