Dynamic Programming Technique
High ImportanceSolve complex recursive problems by breaking them into overlapping subproblems and memoizing states.
When to Use Dynamic Programming:
Key problem characteristics and signals indicating that this technique is the optimal choice.
Optimization problems seeking minimum/maximum cost or count of distinct paths.
Decision stages having optimal substructure and overlapping subproblems.
Prerequisite Rule: Sliding window strictly applies to contiguous sequences (subarrays or substrings). For non-contiguous subsequences or when negative values invalidate monotonicity, prefix sum or dynamic programming approaches are standard.
Example Problem — Sum of Pair Equal to Target
The benchmark interview problem demonstrating the transition from quadratic brute force to linear optimality.
Problem Statement
Given a sorted array of integers arr[] and an integer target, determine whether there exists any pair of elements (arr[i], arr[j]) such that their sum equals the target.
arr = [1, 2, 4, 6, 8, 11], target = 10
True (Pair: 2 + 8 = 10 at indices [1, 4])
Explanation: Elements 2 (index 1) and 8 (index 4) sum up to 10, which exactly matches target.
Naive Method — O(n²) Time and O(1) Space
The baseline brute force approach recalculating candidates through nested loops.
The brute force approach generates all possible pairs of elements from the array using two nested loops and checks if the sum of any pair equals the target.
// Code snippet is being prepared.Why Naive Fails in Production & Interviews
For an array with n = 10⁵ elements, checking all pairs requires ~5 × 10⁹ operations, causing Time Limit Exceeded (TLE). It is blind to the sorted order of the sequence.
Dynamic Programming — O(n) Time and O(1) Space
The optimal strategy leveraging dynamic programming mechanics to achieve optimal time complexity.
By maintaining moving pointers/boundaries, we can solve range queries and subarray problems in optimal O(n) time.
Initialize Pointers: Set initial boundary coordinates according to pattern constraints.
Evaluate Invariant: At each iteration, evaluate current state against problem constraints.
Advance Pointers: Advance or shrink boundary in O(1) to transition to next valid state.
Interactive Trace
Step-by-step trace showing invariant evaluation.
Dynamic Programming Algorithm Code
Complete runnable solution in Python, C++, Java, and JavaScript.
// Code snippet is being prepared.How does this work?
Invariant Proof & Why It Is Guaranteed to Never Miss a Valid Pair
The power of Two Pointers comes from sorted monotonicity: each comparison permanently discards an entire candidate element in O(1) time without risking false negatives.
1. Sorted Monotonicity Invariant
The array satisfies arr[0] <= arr[1] <= ... <= arr[n-1]. Consequently, fixing any index i and increasing j strictly increases arr[i] + arr[j]. Conversely, decreasing j strictly decreases the sum.
2. Why is discarding arr[right] safe when sum > target?
If arr[left] + arr[right] > target, then since arr[left] is the smallest active element, pairing arr[right] with any other element >= arr[left] will also exceed target. Thus arr[right] cannot participate in ANY valid pair. Decrementing right is 100% safe.
3. Why is discarding arr[left] safe when sum < target?
If arr[left] + arr[right] < target, then since arr[right] is the largest active element, pairing arr[left] with any other element <= arr[right] will be even smaller. Thus arr[left] cannot reach target with any remaining candidate. Incrementing left is 100% safe.
4. The Boundary Guarantee
Whichever pointer reaches its true coordinate first will halt while every subsequent comparison directs the other pointer straight toward it. Pointers never skip past the true solution.
Core Pattern Variations & Blueprints
Explore the 3 structural variations that power all dynamic programming interview problems. Click each variation to expand its blueprint, interactive dry run, and implementation.
Curated Practice Ladder
Master this pattern progressively through verified interview questions.
Create a free account to track progress and unlock your free practice set.
Premium also includes the full problem library, detailed solutions, hints, and advanced revision tools.
Already have an account? Log in
“Master the invariants,
and the solution
writes itself.”
