Search Blogs

Showing results for "Partitioning"

Found 5 results

LeetCode 769: Max Chunks To Make Sorted – Java Solution, Approach & Explanation

IntroductionLeetCode 769, Max Chunks To Make Sorted, is an interesting array partitioning problem.The array is a permutation of numbers from 0 to n - 1. The goal is to divide the array into multiple contiguous chunks, sort each chunk independently, and then join all the sorted chunks together.The challenge is to find the maximum number of chunks for which the final concatenated array becomes completely sorted.For example:arr = [1,0,2,3,4]The array can be divided as:[1,0] [2] [3] [4]After sorting every chunk:[0,1] [2] [3] [4]The final array is:[0,1,2,3,4]Therefore, the answer is 4.The given solution approaches the problem using recursion and backtracking to generate possible partitions and then checks which partitions produce a sorted array.Question LinkLeetCode 769 – Max Chunks To Make SortedUnderstanding the ProblemThe important word in the problem is chunks.A chunk must contain consecutive elements from the original array.For example:[4,3,2,1,0]Possible partition:[4,3] [2,1,0]After sorting:[3,4] [0,1,2]Combining them gives:[3,4,0,1,2]which is not sorted.So this partition is invalid.The task is not simply to split the array into as many pieces as possible. Every chosen partition must satisfy the condition that sorting each piece independently produces the globally sorted array.Approach: Recursion + BacktrackingThe given solution tries every possible way of partitioning the array.At every index, it considers every possible ending position for the current chunk.For example:arr = [1,0,2]Starting from index 0, possible first chunks are:[1][1,0][1,0,2]For each choice, recursion continues from the next index.This generates different partition configurations such as:[1] [0] [2][1,0] [2][1] [0,2][1,0,2]Each complete partition is then checked to determine whether it produces a sorted array.Generating the ChunksThe recursive function is:public void sol(int[] arr, int ind, List<List<Integer>> chunk)Here:ind represents the current starting index.chunk stores the chunks selected so far.The loop:for(int i = ind; i < arr.length; i++){ List<Integer> lis = subar(arr, ind, i); chunk.add(lis); sol(arr, i + 1, chunk); chunk.remove(chunk.size() - 1);}tries every possible ending point for the current chunk.The important part is:sol(arr, i + 1, chunk);Once a chunk from ind to i has been selected, the next chunk must begin at i + 1.Creating a ChunkThe subar() method creates a list containing the elements between two indices.public List<Integer> subar(int[] arr, int st, int en){ List<Integer> lis = new ArrayList<>(); for(int i = st; i <= en; i++){ lis.add(arr[i]); } return lis;}For example:arr = [1,0,2,3]st = 0en = 1produces:[1,0]Checking a PartitionOnce a complete partition has been generated, the vali() method checks whether it is valid.First, every chunk is sorted:Collections.sort(a);Then all sorted chunks are concatenated into one list:res.add(a.get(i));Finally, the resulting array is checked to see whether it is globally sorted.for(int i = 0; i < res.size() - 1; i++){ if(res.get(i) > res.get(i + 1)){ return false; }}If no decreasing pair exists, the partition is valid.Java Solutionclass Solution { int an = 0; // Generates all possible partitions public void sol(int[] arr, int ind, List<List<Integer>> chunk) { // A complete partition has been created if(ind == arr.length){ // Check whether this partition produces // the completely sorted array if(vali(chunk)){ an = Math.max(an, chunk.size()); } return; } // Try every possible ending point // for the current chunk for(int i = ind; i < arr.length; i++){ // Create the current chunk List<Integer> lis = subar(arr, ind, i); // Choose the chunk chunk.add(lis); // Recursively create the remaining chunks sol(arr, i + 1, chunk); // Backtrack chunk.remove(chunk.size() - 1); } } // Creates a subarray from st to en public List<Integer> subar(int[] arr, int st, int en){ List<Integer> lis = new ArrayList<>(); for(int i = st; i <= en; i++){ lis.add(arr[i]); } return lis; } // Checks whether the selected partition is valid public boolean vali(List<List<Integer>> liss){ List<Integer> res = new ArrayList<>(); // Sort every chunk independently for(List<Integer> a : liss){ Collections.sort(a); // Add the sorted chunk to the result for(int i = 0; i < a.size(); i++){ res.add(a.get(i)); } } // Check whether the final array is sorted for(int i = 0; i < res.size() - 1; i++){ if(res.get(i) > res.get(i + 1)){ return false; } } return true; } public int maxChunksToSorted(int[] arr){ List<List<Integer>> liss = new ArrayList<>(); sol(arr, 0, liss); return an; }}Dry RunConsider:arr = [1,0,2,3,4]One of the partitions generated by recursion is:[1,0] [2] [3] [4]The chunks are individually sorted:[0,1] [2] [3] [4]After concatenation:[0,1,2,3,4]The resulting array is sorted, so the partition is valid.It contains:4 chunksThe recursion also examines partitions with fewer chunks, such as:[1,0,2,3,4][1,0] [2,3,4][1] [0,2,3,4][1,0] [2] [3,4]Among all valid partitions, the solution keeps the maximum number of chunks using:an = Math.max(an, chunk.size());Therefore:Answer = 4Why Does the Maximum Number of Chunks Matter?A partition with fewer chunks can still produce the sorted array.For example:[1,0,2,3,4]can be split as:[1,0] [2,3,4]After sorting:[0,1] [2,3,4]which produces:[0,1,2,3,4]So this is valid.But it is not the maximum because:[1,0] [2] [3] [4]also works and gives more chunks.Therefore, every valid partition cannot simply be accepted—the number of chunks must also be maximized.Complexity AnalysisThe number of ways to split an array of length n into contiguous chunks is:2^(n-1)because every gap between two elements can either contain a partition or not.For example, with:[a,b,c]there are two gaps:a | b | cEach gap has two choices, giving:2² = 4possible partitions.For every complete partition, the solution also sorts the chunks and constructs the resulting array.Therefore, the overall complexity is exponential.Time Complexity: Approximately O(2^n × n log n)Space Complexity: Approximately O(n × 2^n) in the worst case because many partition configurations and temporary lists are generated.Since the given constraint is only:n <= 10this brute-force approach is feasible.A Better ObservationAlthough recursion works for the small constraint, this problem has a much simpler O(n) greedy solution.The key observation comes from the fact that the array is a permutation of:0, 1, 2, ..., n-1Suppose the current chunk ends at index i.If the maximum value seen so far is exactly i, then the current elements contain exactly the values that should occupy positions 0 through i.Therefore, the chunk can safely end at this position.For example:arr = [1,0,2,3,4]Track the maximum:index value max 0 1 1 1 0 1 2 2 2 3 3 3 4 4 4Whenever:max == indexa new chunk can be created.This happens at:index 1index 2index 3index 4So the answer is:4The optimized implementation is:class Solution { public int maxChunksToSorted(int[] arr) { int max = 0; int chunks = 0; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); if(max == i){ chunks++; } } return chunks; }}This reduces the complexity to:Time Complexity: O(n)Space Complexity: O(1)Interview TipWhen a problem says the array is a permutation from 0 to n-1, that property is usually extremely important.Instead of immediately trying to generate all possibilities, look for a relationship between:the current indexthe values seen so farthe final sorted positionFor this problem, the condition:maximum value seen so far == current indexmeans that the current portion contains exactly the values needed for that prefix of the sorted array.That single observation turns an exponential backtracking solution into a linear greedy solution.ConclusionLeetCode 769 is a good example of how the same problem can be approached at different levels.The recursive solution explores every possible contiguous partition, sorts each chunk, and checks whether the final result is sorted. It is straightforward and works well under the small constraint n <= 10.However, the permutation property provides a much stronger observation. Whenever the maximum value seen so far equals the current index, a chunk can safely end there.That leads to a simple:O(n) timeO(1) spacegreedy solution.The main lesson is to first understand the brute-force structure, then look for properties in the input that can eliminate the need to explore every possibility.

LeetCodeJavaRecursionBacktrackingGreedyArraysSortingPermutationPartitioningMedium

LeetCode 2161: Partition Array According to Given Pivot – Java Easy Stable Partition Solution

IntroductionLeetCode 2161 is a clean and important array manipulation problem that tests:Array traversalStable partitioningOrder preservationTwo-pass and three-pass approachesLogical grouping of elementsThe interesting part of this problem is that we are not only partitioning the array around a pivot, but we also need to preserve the relative order of elements.This makes the problem slightly different from classical partition algorithms like QuickSort partitioning.In this article, we will understand:The intuition behind stable partitioningWhy order preservation mattersStep-by-step explanationDry runTime and space complexityComplete optimized Java solutionProblem StatementTry this probelm here :- Partition ArrayYou are given:An integer array:numsAn integer:pivotYou must rearrange the array such that:All elements smaller than pivot come firstAll elements equal to pivot come nextAll elements greater than pivot come lastRelative ordering must remain preservedReturn the rearranged array.ExampleInputnums = [9,12,5,10,14,3,10]pivot = 10Output[9,5,3,10,10,12,14]ExplanationElements less than 109, 5, 3Elements equal to 1010, 10Elements greater than 1012, 14All relative orderings are preserved.Key ObservationWe do NOT need sorting.We only need grouping while maintaining original order.This is called:Stable PartitioningApproachWe create a new array and fill it in 3 phases:Phase 1Insert all elements:< pivotPhase 2Insert all elements:== pivotPhase 3Insert all elements:> pivotThis naturally preserves relative ordering because we traverse left-to-right every time.Optimized Java Solutionclass Solution { public int[] pivotArray(int[] nums, int pivot) { int[] ans = new int[nums.length]; int index = 0; // Smaller than pivot for(int i = 0; i < nums.length; i++) { if(nums[i] < pivot) { ans[index] = nums[i]; index++; } } // Equal to pivot for(int i = 0; i < nums.length; i++) { if(nums[i] == pivot) { ans[index] = nums[i]; index++; } } // Greater than pivot for(int i = 0; i < nums.length; i++) { if(nums[i] > pivot) { ans[index] = nums[i]; index++; } } return ans; }}Step-by-Step ExplanationStep 1: Create Answer Arrayint[] ans = new int[nums.length];Stores final partitioned result.Step 2: Insert Smaller Elementsif(nums[i] < pivot)All smaller elements go first.Step 3: Insert Equal Elementsif(nums[i] == pivot)Pivot values are placed in the middle.Step 4: Insert Larger Elementsif(nums[i] > pivot)Larger elements go to the end.Dry RunInputnums = [9,12,5,10,14,3,10]pivot = 10Pass 1: Smaller ElementsAdd:9, 5, 3Current array:[9,5,3]Pass 2: Equal ElementsAdd:10, 10Current array:[9,5,3,10,10]Pass 3: Greater ElementsAdd:12, 14Final array:[9,5,3,10,10,12,14]Time ComplexityWe traverse the array 3 times.Time ComplexityO(N)Because:3N → O(N)Space ComplexityWe use an extra array.Space ComplexityO(N)Why This Problem is ImportantThis problem teaches:Stable partitioningArray groupingRelative order preservationMulti-pass array processingClean implementation strategyThese concepts are frequently used in:Sorting systemsData pipelinesStream processingPartition-based algorithmsCommon Mistakes1. Using QuickSort Partition LogicQuickSort partitioning does NOT preserve order.This problem specifically requires stable ordering.2. Forgetting Equal ElementsSome solutions only handle:< pivotand> pivotBut pivot values must remain in the center.3. Overcomplicating with Two PointersA simple three-pass solution is cleaner and easier to understand.Interview ExplanationIn interviews explain:Since relative order must remain preserved, we cannot use traditional in-place partitioning. Instead, we perform stable partitioning by collecting smaller, equal, and larger elements sequentially.This demonstrates:Understanding of stable operationsStrong array fundamentalsClean coding approachAlternative ApproachAnother approach is using:Three separate listsThen merging themExample:small + equal + largeBut using one answer array is more space efficient.ConclusionLeetCode 2161 is a simple yet important stable partition problem.The key insight is:We must preserve relative ordering while grouping elements around the pivot.Using a clean three-pass traversal gives an elegant and efficient O(N) solution.

LeetCodeJavaMediumArrayArray PartitionPivot

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

IntroductionQuick Sort is one of the most powerful and widely used sorting algorithms in computer science. It follows the Divide and Conquer approach and is known for its excellent average-case performance.What makes Quick Sort special is:It sorts in-place (no extra array required)It is faster in practice than many O(n log n) algorithms like Merge SortIt is heavily used in real-world systems and librariesIn this article, we’ll go deep into:Intuition behind Quick SortPartition logic (most important part)Step-by-step dry runJava implementation with commentsTime complexity analysisCommon mistakes and optimizations🔗 Problem LinkGeeksforGeeks: Quick SortProblem StatementGiven an array arr[], sort it in ascending order using Quick Sort.Requirements:Use Divide and ConquerChoose pivot elementPlace pivot in correct positionElements smaller → left sideElements greater → right sideExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [2, 1, 6, 10, 4, 1, 3, 9, 7]Output:[1, 1, 2, 3, 4, 6, 7, 9, 10]Core Idea of Quick SortPick a pivot → Place it correctly → Recursively sort left & right🔥 Key Insight (Partition is Everything)Quick Sort depends entirely on partitioning:👉 After partition:Pivot is at its correct sorted positionLeft side → smaller elementsRight side → larger elementsIntuition (Visual Understanding)Consider:[4, 1, 3, 9, 7]Step 1: Choose PivotLet’s say pivot = 4Step 2: Rearrange Elements[1, 3] 4 [9, 7]Now:Left → smallerRight → largerStep 3: Apply RecursivelyLeft: [1, 3]Right: [9, 7]Final result:[1, 3, 4, 7, 9]Partition Logic (Most Important)Your implementation uses:Pivot = first elementTwo pointers:i → moves forwardj → moves backwardJava Codeclass Solution { public void quickSort(int[] arr, int low, int high) { // Base case: if array has 1 or 0 elements if (low < high) { // Partition array and get pivot index int pivotInd = partition(arr, low, high); // Sort left part quickSort(arr, low, pivotInd - 1); // Sort right part quickSort(arr, pivotInd + 1, high); } } // Function to swap two elements void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private int partition(int[] arr, int low, int high) { int pivot = arr[low]; // choosing first element as pivot int i = low + 1; // start from next element int j = high; // start from end while (i <= j) { // Move i forward until element > pivot while (i <= high && arr[i] <= pivot) { i++; } // Move j backward until element <= pivot while (j >= low && arr[j] > pivot) { j--; } // Swap if pointers haven't crossed if (i < j) { swap(arr, i, j); } } // Place pivot at correct position swap(arr, low, j); return j; // return pivot index }}Step-by-Step Dry RunInput:[4, 1, 3, 9, 7]Execution:Pivot = 4i → moves until element > 4j → moves until element ≤ 4Swaps happen → pivot placed correctlyFinal partition:[1, 3, 4, 9, 7]Complexity AnalysisTime ComplexityCaseComplexityBest CaseO(n log n)Average CaseO(n log n)Worst CaseO(n²)Why Worst Case Happens?When array is:Already sortedReverse sortedPivot always becomes smallest/largest.Space ComplexityO(log n) (recursion stack)❌ Common MistakesWrong partition logicInfinite loops in while conditionsIncorrect pivot placementNot handling duplicates properly⚡ Optimizations1. Random PivotAvoid worst-case:int pivotIndex = low + new Random().nextInt(high - low + 1);swap(arr, low, pivotIndex);2. Median of ThreeChoose better pivot:median(arr[low], arr[mid], arr[high])Quick Sort vs Merge SortFeatureQuick SortMerge Sort link to get moreSpaceO(log n)O(n)SpeedFaster (practical)StableWorst CaseO(n²)O(n log n)Why Quick Sort is PreferredCache-friendlyIn-place sortingFaster in real-world scenariosKey TakeawaysPartition is the heart of Quick SortPivot must be placed correctlyRecursion splits problem efficientlyAvoid worst case using random pivotWhen to Use Quick SortLarge arraysMemory constraints (in-place)Performance-critical applicationsConclusionQuick Sort is one of the most efficient and practical sorting algorithms. Mastering its partition logic is crucial for solving advanced problems and performing well in coding interviews.Understanding how pointers move and how pivot is placed will make this algorithm intuitive and powerful.Frequently Asked Questions (FAQs)1. Is Quick Sort stable?No, it is not stable.2. Why is Quick Sort faster than Merge Sort?Because it avoids extra space and is cache-efficient.3. What is the most important part?👉 Partition logic

MediumJavaSortingQuick SortGeeksofGeeks

What Is Dynamic Programming? Origin Story, Real-Life Uses, LeetCode Problems & Complete Beginner Guide

Introduction — Why Dynamic Programming Feels Hard (And Why It Isn't)If you've ever stared at a LeetCode problem, read the solution, understood every single line, and still had absolutely no idea how someone arrived at it — welcome. You've just experienced the classic Dynamic Programming (DP) confusion.DP has a reputation. People treat it like some dark art reserved for competitive programmers or Google engineers. The truth? Dynamic Programming is one of the most logical, learnable, and satisfying techniques in all of computer science. Once it clicks, it really clicks.This guide will take you from zero to genuinely confident. We'll cover where DP came from, how it works, what patterns to learn, how to recognize DP problems, real-world places it shows up, LeetCode problems to practice, time complexity analysis, and the mistakes that trip up even experienced developers.Let's go.The Origin Story — Who Invented Dynamic Programming and Why?The term "Dynamic Programming" was coined by Richard Bellman in the early 1950s while working at RAND Corporation. Here's the funny part: the name was deliberately chosen to sound impressive and vague.Bellman was doing mathematical research that his employer — the US Secretary of Defense, Charles Wilson — would have found difficult to fund if described accurately. Wilson had a well-known distaste for the word "research." So Bellman invented a name that sounded suitably grand and mathematical: Dynamic Programming.In his autobiography, Bellman wrote that he picked the word "dynamic" because it had a precise technical meaning and was also impossible to use negatively. "Programming" referred to the mathematical sense — planning and decision-making — not computer programming.The underlying idea? Break a complex problem into overlapping subproblems, solve each subproblem once, and store the result so you never solve it twice.Bellman's foundational contribution was the Bellman Equation, which underpins not just algorithms but also economics, operations research, and modern reinforcement learning.So the next time DP feels frustrating, remember — even its inventor named it specifically to confuse people. You're in good company.What Is Dynamic Programming? (Simple Definition)Dynamic Programming is an algorithmic technique used to solve problems by:Breaking them down into smaller overlapping subproblemsSolving each subproblem only onceStoring the result (memoization or tabulation)Building up the final solution from those stored resultsThe key insight is overlapping subproblems + optimal substructure.Overlapping subproblems means the same smaller problems come up again and again. Instead of solving them every time (like plain recursion does), DP solves them once and caches the answer.Optimal substructure means the optimal solution to the whole problem can be built from optimal solutions to its subproblems.If a problem has both these properties — it's a DP problem.The Two Approaches to Dynamic Programming1. Top-Down with Memoization (Recursive + Cache)You write a recursive solution exactly as you would naturally, but add a cache (usually a dictionary or array) to store results you've already computed.fib(n):if n in cache: return cache[n]if n <= 1: return ncache[n] = fib(n-1) + fib(n-2)return cache[n]This is called memoization — remember what you computed so you don't repeat yourself.Pros: Natural to write, mirrors the recursive thinking, easy to reason about. Cons: Stack overhead from recursion, risk of stack overflow on large inputs.2. Bottom-Up with Tabulation (Iterative)You figure out the order in which subproblems need to be solved, then solve them iteratively from the smallest up, filling a table.fib(n):dp = [0, 1]for i from 2 to n:dp[i] = dp[i-1] + dp[i-2]return dp[n]This is called tabulation — fill a table, cell by cell, bottom to top.Pros: No recursion overhead, usually faster in practice, easier to optimize space. Cons: Requires thinking about the order of computation upfront.🧩 Dynamic Programming Template CodeBefore diving into how to recognize DP problems, here are ready-to-use Java templates for every major DP pattern. Think of these as your reusable blueprints — every DP problem you ever solve will fit into one of these structures. Just define your state, plug in your recurrence relation, and you are good to go.Template 1 — Top-Down (Memoization)import java.util.HashMap;import java.util.Map;public class TopDownDP {Map<Integer, Integer> memo = new HashMap<>();public int solve(int n) {// Base caseif (n <= 1) return n;// Check cacheif (memo.containsKey(n)) return memo.get(n);// Recurrence relation — change this part for your problemint result = solve(n - 1) + solve(n - 2);// Store in cachememo.put(n, result);return result;}}Template 2 — Bottom-Up (Tabulation)public class BottomUpDP {public int solve(int n) {// Create DP tableint[] dp = new int[n + 1];// Base casesdp[0] = 0;dp[1] = 1;// Fill the table bottom-upfor (int i = 2; i <= n; i++) {// Recurrence relation — change this part for your problemdp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}}Template 3 — Bottom-Up with Space Optimizationpublic class SpaceOptimizedDP {public int solve(int n) {// Only keep last two values instead of full tableint prev2 = 0;int prev1 = 1;for (int i = 2; i <= n; i++) {// Recurrence relation — change this part for your problemint curr = prev1 + prev2;prev2 = prev1;prev1 = curr;}return prev1;}}Template 4 — 2D DP (Two Sequences or Grid)public class TwoDimensionalDP {public int solve(String s1, String s2) {int m = s1.length();int n = s2.length();// Create 2D DP tableint[][] dp = new int[m + 1][n + 1];// Base cases — first row and columnfor (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;// Fill table cell by cellfor (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// Recurrence relation — change this part for your problemif (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j],Math.min(dp[i][j - 1], dp[i - 1][j - 1]));}}}return dp[m][n];}}Template 5 — Knapsack Patternpublic class KnapsackDP {public int solve(int[] weights, int[] values, int capacity) {int n = weights.length;// dp[i][w] = max value using first i items with capacity wint[][] dp = new int[n + 1][capacity + 1];for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {// Don't take item idp[i][w] = dp[i - 1][w];// Take item i if it fitsif (weights[i - 1] <= w) {dp[i][w] = Math.max(dp[i][w],values[i - 1] + dp[i - 1][w - weights[i - 1]]);}}}return dp[n][capacity];}}💡 How to use these templates:Step 1 — Identify which pattern your problem fits into. Step 2 — Define what dp[i] or dp[i][j] means in plain English before writing any code. Step 3 — Write your recurrence relation on paper first. Step 4 — Plug it into the matching template above. Step 5 — Handle your specific base cases carefully.🎥 Visual Learning Resource — Watch This Before Moving ForwardIf you prefer learning by watching before reading, this free full-length course by freeCodeCamp is one of the best Dynamic Programming resources on the internet. Watch it alongside this guide for maximum understanding.Credit: freeCodeCamp — a free, nonprofit coding education platform.How to Recognize a Dynamic Programming ProblemAsk yourself these four questions:1. Can I define the problem in terms of smaller versions of itself? If you can write a recursive formula (recurrence relation), DP might apply.2. Do the subproblems overlap? If a naive recursive solution would recompute the same thing many times, DP is the right tool.3. Is there an optimal substructure? Is the best answer to the big problem made up of best answers to smaller problems?4. Are you looking for a count, minimum, maximum, or yes/no answer? DP problems often ask: "What is the minimum cost?", "How many ways?", "Can we achieve X?"Red flag words in problem statements: minimum, maximum, shortest, longest, count the number of ways, can we reach, is it possible, fewest steps.The Core DP Patterns You Must LearnMastering DP is really about recognizing patterns. Here are the most important ones:Pattern 1 — 1D DP (Linear) Problems where the state depends on previous elements in a single sequence. Examples: Fibonacci, Climbing Stairs, House Robber.Pattern 2 — 2D DP (Grid / Two-sequence) Problems with two dimensions of state, often grids or two strings. Examples: Longest Common Subsequence, Edit Distance, Unique Paths.Pattern 3 — Interval DP You consider all possible intervals or subarrays and build solutions from them. Examples: Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning.Pattern 4 — Knapsack DP (0/1 and Unbounded) You decide whether to include or exclude items under a capacity constraint. Examples: 0/1 Knapsack, Coin Change, Partition Equal Subset Sum.Pattern 5 — DP on Trees State is defined per node; you combine results from children. Examples: Diameter of Binary Tree, House Robber III, Maximum Path Sum.Pattern 6 — DP on Subsets / Bitmask DP State includes a bitmask representing which elements have been chosen. Examples: Travelling Salesman Problem, Shortest Superstring.Pattern 7 — DP on Strings Matching, editing, or counting arrangements within strings. Examples: Longest Palindromic Subsequence, Regular Expression Matching, Wildcard Matching.Top LeetCode Problems to Practice Dynamic Programming (With Links)Here are the essential problems, organized by difficulty and pattern. Solve them in this order.Beginner — Warm UpProblemPatternLinkClimbing Stairs1D DPhttps://leetcode.com/problems/climbing-stairs/Fibonacci Number1D DPhttps://leetcode.com/problems/fibonacci-number/House Robber1D DPhttps://leetcode.com/problems/house-robber/Min Cost Climbing Stairs1D DPhttps://leetcode.com/problems/min-cost-climbing-stairs/Best Time to Buy and Sell Stock1D DPhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock/Intermediate — Core PatternsProblemPatternLinkCoin ChangeKnapsackhttps://leetcode.com/problems/coin-change/Longest Increasing Subsequence1D DPhttps://leetcode.com/problems/longest-increasing-subsequence/Longest Common Subsequence2D DPhttps://leetcode.com/problems/longest-common-subsequence/0/1 Knapsack (via Subset Sum)Knapsackhttps://leetcode.com/problems/partition-equal-subset-sum/Unique Paths2D Grid DPhttps://leetcode.com/problems/unique-paths/Jump Game1D DP / Greedyhttps://leetcode.com/problems/jump-game/Word BreakString DPhttps://leetcode.com/problems/word-break/Decode Ways1D DPhttps://leetcode.com/problems/decode-ways/Edit Distance2D String DPhttps://leetcode.com/problems/edit-distance/Triangle2D DPhttps://leetcode.com/problems/triangle/Advanced — Interview LevelProblemPatternLinkBurst BalloonsInterval DPhttps://leetcode.com/problems/burst-balloons/Regular Expression MatchingString DPhttps://leetcode.com/problems/regular-expression-matching/Wildcard MatchingString DPhttps://leetcode.com/problems/wildcard-matching/Palindrome Partitioning IIInterval DPhttps://leetcode.com/problems/palindrome-partitioning-ii/Maximum Profit in Job SchedulingDP + Binary Searchhttps://leetcode.com/problems/maximum-profit-in-job-scheduling/Distinct Subsequences2D DPhttps://leetcode.com/problems/distinct-subsequences/Cherry Pickup3D DPhttps://leetcode.com/problems/cherry-pickup/Real-World Use Cases of Dynamic ProgrammingDP is not just for coding interviews. It is deeply embedded in the technology you use every day.1. Google Maps & Navigation (Shortest Path) The routing engines behind GPS apps use DP-based algorithms like Dijkstra and Bellman-Ford to find the shortest or fastest path between two points across millions of nodes.2. Spell Checkers & Autocorrect (Edit Distance) When your phone corrects "teh" to "the," it is computing Edit Distance — a classic DP problem — between what you typed and every word in the dictionary.3. DNA Sequence Alignment (Bioinformatics) Researchers use the Needleman-Wunsch and Smith-Waterman algorithms — both DP — to align DNA and protein sequences and find similarities between species or identify mutations.4. Video Compression (MPEG, H.264) Modern video codecs use DP to determine the most efficient way to encode video frames, deciding which frames to store as full images and which to store as differences from the previous frame.5. Financial Portfolio Optimization Investment algorithms use DP to find the optimal allocation of assets under risk constraints — essentially a variant of the knapsack problem.6. Natural Language Processing (NLP) The Viterbi algorithm — used in speech recognition, part-of-speech tagging, and machine translation — is a DP algorithm. Every time Siri or Google Assistant understands your sentence, DP played a role.7. Game AI (Chess, Checkers) Game trees and minimax algorithms with memoization use DP to evaluate board positions and find the best move without recomputing already-seen positions.8. Compiler Optimization Compilers use DP to decide the optimal order of operations and instruction scheduling to generate the most efficient machine code.9. Text Justification (Word Processors) Microsoft Word and LaTeX use DP to optimally break paragraphs into lines — minimizing raggedness and maximizing visual appeal.10. Resource Scheduling in Cloud Computing AWS, Google Cloud, and Azure use DP-based scheduling to assign computational tasks to servers in the most cost-efficient way possible.Time Complexity Analysis of Common DP ProblemsUnderstanding the time complexity of DP is critical for interviews and for building scalable systems.ProblemTime ComplexitySpace ComplexityNotesFibonacci (naive recursion)O(2ⁿ)O(n)Exponential — terribleFibonacci (DP)O(n)O(1) with optimizationLinear — excellentLongest Common SubsequenceO(m × n)O(m × n)m, n = lengths of two stringsEdit DistanceO(m × n)O(m × n)Can optimize space to O(n)0/1 KnapsackO(n × W)O(n × W)n = items, W = capacityCoin ChangeO(n × amount)O(amount)Classic tabulationLongest Increasing SubsequenceO(n²) or O(n log n)O(n)Binary search version is fasterMatrix Chain MultiplicationO(n³)O(n²)Interval DPTravelling Salesman (bitmask)O(2ⁿ × n²)O(2ⁿ × n)Still exponential but manageable for small nThe general rule: DP trades time for space. You use memory to avoid recomputation. The time complexity equals the number of unique states multiplied by the work done per state.How to Learn and Master Dynamic Programming — Step by StepHere is an honest, structured path to mastery:Step 1 — Get recursion absolutely solid first. DP is memoized recursion at its core. If you cannot write clean recursive solutions confidently, DP will remain confusing. Practice at least 20 pure recursion problems first.Step 2 — Start with the classics. Fibonacci → Climbing Stairs → House Robber → Coin Change. These teach you the core pattern of defining state and transition without overwhelming you.Step 3 — Learn to define state explicitly. Before writing any code, ask: "What does dp[i] represent?" Write it in plain English. "dp[i] = the minimum cost to reach step i." This single habit separates good DP thinkers from struggling ones.Step 4 — Write the recurrence relation before coding. On paper or in a comment. Example: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). If you can write the recurrence, the code writes itself.Step 5 — Master one pattern at a time. Don't jump between knapsack and interval DP in the same week. Spend a few days on each pattern until it feels intuitive.Step 6 — Solve the same problem both ways. Top-down and bottom-up. This builds deep understanding of what DP is actually doing.Step 7 — Optimize space after getting correctness. Many 2D DP solutions can use a single row instead of a full matrix. Learn this optimization after you understand the full solution.Step 8 — Do timed practice under interview conditions. Give yourself 35 minutes per problem. Review what you got wrong. DP is a muscle — it builds with reps.Common Mistakes in Dynamic Programming (And How to Avoid Them)Mistake 1 — Jumping to code before defining state. The most common DP error. Always define what dp[i] or dp[i][j] means before writing a single line of code.Mistake 2 — Wrong base cases. A single wrong base case corrupts every answer built on top of it. Trace through your base cases manually on a tiny example before running code.Mistake 3 — Off-by-one errors in indexing. Whether your dp array is 0-indexed or 1-indexed must be 100% consistent throughout. This causes more bugs in DP than almost anything else.Mistake 4 — Confusing top-down with bottom-up state order. In bottom-up DP, you must ensure that when you compute dp[i], all values it depends on are already filled. If you compute in the wrong order, you get garbage answers.Mistake 5 — Memoizing in the wrong dimension. In 2D problems, some people cache only one dimension when the state actually requires two. Always identify all variables that affect the outcome.Mistake 6 — Using global mutable state in recursion. If you use a shared array and don't clear it between test cases, you'll get wrong answers on subsequent inputs. Always scope your cache correctly.Mistake 7 — Not considering the full state space. In problems like Knapsack, forgetting that the state is (item index, remaining capacity) — not just item index — leads to fundamentally wrong solutions.Mistake 8 — Giving up after not recognizing the pattern immediately. DP problems don't announce themselves. The skill is learning to ask "is there overlapping subproblems here?" on every problem. This takes time. Don't mistake unfamiliarity for inability.Frequently Asked Questions About Dynamic ProgrammingQ: Is Dynamic Programming the same as recursion? Not exactly. Recursion is a technique for breaking problems into smaller pieces. DP is recursion plus memoization — or iterative tabulation. All DP can be written recursively, but not all recursion is DP.Q: What is the difference between DP and Divide and Conquer? Divide and Conquer (like Merge Sort) breaks problems into non-overlapping subproblems. DP is used when subproblems overlap — meaning the same subproblem is solved multiple times in a naive approach.Q: How do I know when NOT to use DP? If the subproblems don't overlap (no repeated computation), greedy or divide-and-conquer may be better. If the problem has no optimal substructure, DP won't give a correct answer.Q: Do I need to memorize DP solutions for interviews? No. You need to recognize patterns and be able to derive the recurrence relation. Memorizing solutions without understanding them will fail you in interviews. Focus on the thinking process.Q: How long does it take to get good at DP? Most people start to feel genuinely comfortable after solving 40–60 varied DP problems with deliberate practice. The first 10 feel impossible. The next 20 feel hard. After 50, patterns start feeling obvious.Q: What programming language is best for DP? Any language works. Python is often used for learning because its dictionaries make memoization trivial. C++ is preferred in competitive programming for its speed. For interviews, use whatever language you're most comfortable in.Q: What is space optimization in DP? Many DP problems only look back one or two rows to compute the current row. In those cases, you can replace an n×m table with just two arrays (or even one), reducing space complexity from O(n×m) to O(m). This is called space optimization or rolling array technique.Q: Can DP be applied to graph problems? Absolutely. Shortest path algorithms like Bellman-Ford are DP. Longest path in a DAG is DP. DP on trees is a rich subfield. Anywhere you have states and transitions, DP can potentially apply.Q: Is Greedy a type of Dynamic Programming? Greedy is related but distinct. Greedy makes locally optimal choices without reconsidering. DP considers all choices and picks the globally optimal one. Some DP solutions reduce to greedy when the structure allows, but they are different techniques.Q: What resources should I use to learn DP? For structured learning: Neetcode.io (organized problem list), Striver's DP Series on YouTube, and the book "Introduction to Algorithms" (CLRS) for theoretical depth. For practice: LeetCode's Dynamic Programming study plan and Codeforces for competitive DP.Final Thoughts — Dynamic Programming Is a SuperpowerDynamic Programming is genuinely one of the most powerful ideas in computer science. It shows up in your GPS, your autocorrect, your streaming video, your bank's risk models, and the AI assistants you talk to daily.The path to mastering it is not memorization. It is developing the habit of asking: can I break this into smaller problems that overlap? And then learning to define state clearly, write the recurrence, and trust the process.Start with Climbing Stairs. Write dp[i] in plain English before every problem. Solve everything twice — top-down and bottom-up. Do 50 problems with genuine reflection, not just accepted solutions.The click moment will come. And when it does, you'll wonder why it ever felt hard.

Dynamic ProgrammingMemoizationTabulationJavaOrigin StoryRichard Bellman

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/odd-even-linked-list/Problem Description (In Very Simple Words)You are given the head of a linked list.Your task is:👉 Rearrange the list such that:All nodes at odd positions come firstFollowed by all nodes at even positionsImportant Clarification❗ This problem is about positions (indices), NOT values.1st node → Odd2nd node → Even3rd node → Odd4th node → EvenExample WalkthroughExample 1Input:[1,2,3,4,5]Positions:1(odd), 2(even), 3(odd), 4(even), 5(odd)Output:[1,3,5,2,4]Example 2Input:[2,1,3,5,6,4,7]Output:[2,3,6,7,1,5,4]Constraints0 <= number of nodes <= 10^4-10^6 <= Node.val <= 10^6Core Idea of the ProblemWe need to:Separate nodes into two groups:Odd index nodesEven index nodesMaintain their original orderFinally:👉 Attach even list after odd listThinking About Different ApproachesWhen solving this problem, multiple approaches may come to mind:Approach 1: Create New ListsIdeaTraverse the listCreate new nodes for odd and even positionsBuild two separate listsMerge themProblem with This Approach❌ Uses extra space❌ Not optimal (violates O(1) space requirement)❌ Code becomes messy and harder to maintainYour approach is logically correct, but:👉 It is not optimal and can be simplified a lot.Approach 2: Brute Force Using Array/ListIdeaStore nodes in an arrayRearrange based on indicesRebuild linked listComplexityTime: O(n)Space: O(n) ❌ (Not allowed)Approach 3: Optimal In-Place Approach (Best Solution)This is the cleanest and most important approach.Optimal Approach: Two Pointer Technique (In-Place)IdeaInstead of creating new nodes:👉 We rearrange the existing nodesWe maintain:odd → points to odd nodeseven → points to even nodesevenHead → stores start of even listVisualizationInput:1 → 2 → 3 → 4 → 5We separate into:Odd: 1 → 3 → 5Even: 2 → 4Final:1 → 3 → 5 → 2 → 4Step-by-Step LogicStep 1: Initialize pointersodd = headeven = head.nextevenHead = head.nextStep 2: Traverse the listWhile:even != null && even.next != nullUpdate:odd.next = odd.next.nexteven.next = even.next.nextMove pointers forward:odd = odd.nexteven = even.nextStep 3: Mergeodd.next = evenHeadClean Java Implementation (Optimal)class Solution { public ListNode oddEvenList(ListNode head) { // Edge case if(head == null || head.next == null) return head; // Initialize pointers ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; // Rearranging nodes while(even != null && even.next != null){ odd.next = odd.next.next; // Link next odd even.next = even.next.next; // Link next even odd = odd.next; even = even.next; } // Attach even list after odd list odd.next = evenHead; return head; }}Dry Run (Important)Input:1 → 2 → 3 → 4 → 5Steps:Iteration 1:odd → 1, even → 2Link:1 → 32 → 4Iteration 2:odd → 3, even → 4Link:3 → 54 → nullFinal connection:5 → 2Result:1 → 3 → 5 → 2 → 4Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why This Approach is BestFeatureResultExtra Space❌ NoneClean Code✅ YesEfficient✅ O(n)Interview Friendly✅ HighlyCommon Mistakes❌ Confusing values with positions❌ Creating new nodes unnecessarily❌ Forgetting to connect even list at the end❌ Breaking the list accidentallyKey LearningThis problem teaches:In-place linked list manipulationPointer handlingList partitioningFinal ThoughtsThe Odd Even Linked List problem is a classic example of how powerful pointer manipulation can be.Even though creating new nodes might seem easier at first, the in-place approach is:👉 Faster👉 Cleaner👉 Interview optimized👉 Tip: Whenever you are asked to rearrange a linked list, always think:"Can I solve this by just changing pointers instead of creating new nodes?"That’s the key to mastering linked list problems 🚀

Linked ListPointer ManipulationIn-Place AlgorithmTwo PointersLeetCode Medium