Search Blogs

Showing results for "Permutations"

Found 15 results

Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG

IntroductionThe Permutation with Spaces problem is a classic recursion question that helps build a strong understanding of decision-making and backtracking patterns.Instead of generating permutations by rearranging characters, this problem focuses on inserting spaces between characters in all possible ways.What makes this problem powerful is its decision tree structure, which you’ve already visualized perfectly. In this article, we will directly connect that intuition with code.Link of Problem: GeeksforGeeks – Permutation with SpacesProblem StatementGiven a string s, generate all possible strings by placing:Either a spaceOr no spacebetween every pair of characters.Return all results in sorted order.ExampleInput:s = "ABC"Output:A B CA BCAB CABCUnderstanding Your Decision Tree (Very Important)Two Choices at Each Step:❌ Do NOT add space before the character✔️ Add space before the characterMapping TreeFrom diagram:At B:"AB" → no space"A B" → spaceAt C:From "AB":"ABC""AB C"From "A B":"A BC""A B C"Final Output (Leaf Nodes)As shown in your diagram:ABC, AB C, A BC, A B C📌 This is exactly what recursion generates.Key InsightAt every index (except first), we have:2 choices → space OR no spaceSo total combinations:2^(n-1)Approach: Recursion + Decision MakingIdeaFix the first characterFor every next character:Add space + characterAdd character directlyContinue recursivelyJava Code with Detailed Commentsimport java.util.*;class Solution { // List to store all results ArrayList<String> lis = new ArrayList<>(); void solve(String s, int ind, String curr) { // Base case: // If index reaches end of string, // we have formed one valid permutation if (ind == s.length()) { lis.add(curr); // store the result return; } // Choice 1: Add SPACE before current character // Example: "A" → "A B" solve(s, ind + 1, curr + " " + s.charAt(ind)); // Choice 2: Do NOT add space // Example: "A" → "AB" solve(s, ind + 1, curr + s.charAt(ind)); } ArrayList<String> permutation(String s) { // Start with first character (no space before it) String curr = "" + s.charAt(0); // Start recursion from index 1 solve(s, 1, curr); // Sort results as required in problem Collections.sort(lis); return lis; }}Step-by-Step Execution (Using Your Tree)For "ABC":Start → "A"At "B":"AB""A B"At "C":"ABC", "AB C""A BC", "A B C"Exactly matches your decision tree leaf nodes ✅Complexity AnalysisTime Complexity: O(2ⁿ)Space Complexity: O(2ⁿ)Why This Approach WorksRecursion explores every possible choiceEach level = one characterEach branch = decision (space / no space)Leaf nodes = final answersKey TakeawaysThis is a binary decision recursion problemAlways identify:ChoicesBase conditionYour decision tree = direct blueprint of recursionSame pattern applies to:SubsetsBinary choices problemsConclusionThe Permutation with Spaces problem becomes extremely simple once the decision tree is understood—and your diagram already captures that perfectly.The recursion directly follows the same structure:Every branch = one decisionEvery leaf = one answerMaster this pattern, and you’ll find many recursion problems much easier to solve.

MediumGeeksforGeeksRecursionJava

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 784 Letter Case Permutation | Recursion & Backtracking Java Solution

IntroductionThe Letter Case Permutation problem is a classic example of recursion and backtracking, often asked in coding interviews and frequently searched by learners preparing for platforms like LeetCode.This problem helps in understanding:Decision-making at each stepRecursive branchingString manipulationIn this article, we’ll break down the intuition, visualize the decision process using your decision tree, and implement an efficient Java solution.🔗 Problem LinkLeetCode: Letter Case PermutationProblem StatementGiven a string s, you can transform each alphabet character into:LowercaseUppercaseDigits remain unchanged.👉 Return all possible strings formed by these transformations.ExamplesExample 1Input:s = "a1b2"Output:["a1b2","a1B2","A1b2","A1B2"]Example 2Input:s = "3z4"Output:["3z4","3Z4"]Key InsightAt each character:If it's a digit → only one choiceIf it's a letter → two choices:lowercase OR uppercaseSo total combinations:2^(number of letters)Intuition (Using Your Decision Tree)For input: "a1b2"Start from index 0: "" / \ "a" "A" | | "a1" "A1" / \ / \ "a1b" "a1B" "A1b" "A1B" | | | | "a1b2" "a1B2" "A1b2" "A1B2"Understanding the TreeAt 'a' → branch into 'a' and 'A''1' → no branching (digit)'b' → again branching'2' → no branching📌 Leaf nodes = final answersApproach: Recursion + BacktrackingIdeaTraverse the string character by characterIf digit → move forwardIf letter → branch into:lowercaseuppercaseJava Codeimport java.util.*;class Solution { // List to store all results List<String> lis = new ArrayList<>(); public void solve(String s, int ind, String ans) { // Base case: reached end of string if (ind == s.length()) { lis.add(ans); // store generated string return; } char ch = s.charAt(ind); // If character is a digit → only one option if (ch >= '0' && ch <= '9') { solve(s, ind + 1, ans + ch); } else { // Choice 1: convert to lowercase solve(s, ind + 1, ans + Character.toLowerCase(ch)); // Choice 2: convert to uppercase solve(s, ind + 1, ans + Character.toUpperCase(ch)); } } public List<String> letterCasePermutation(String s) { solve(s, 0, ""); // start recursion return lis; }}Step-by-Step ExecutionFor "a1b2":Start → ""'a' → "a", "A"'1' → "a1", "A1"'b' → "a1b", "a1B", "A1b", "A1B"'2' → final stringsComplexity AnalysisTime Complexity: O(2^n)(n = number of letters)Space Complexity: O(2^n)(for storing results)Why This Approach WorksRecursion explores all possibilitiesEach letter creates a branching pointDigits pass through unchangedBacktracking ensures all combinations are generatedKey TakeawaysThis is a binary decision recursion problemLetters → 2 choicesDigits → 1 choiceDecision tree directly maps to recursionPattern similar to:SubsetsPermutations with conditionsWhen This Problem Is AskedCommon in:Coding interviewsRecursion/backtracking roundsString manipulation problemsConclusionThe Letter Case Permutation problem is a perfect example of how recursion can be used to explore all possible combinations efficiently.Once the decision tree is clear, the implementation becomes straightforward. This pattern is widely used in many advanced problems, making it essential to master.Frequently Asked Questions (FAQs)1. Why don’t digits create branches?Because they have only one valid form.2. What is the main concept used?Recursion with decision-making (backtracking).3. Can this be solved iteratively?Yes, using BFS or iterative expansion, but recursion is more intuitive.

LeetCodeMediumJavaRecursion

LeetCode 2657: Find the Prefix Common Array of Two Arrays – Java Hashing Solution Explained

IntroductionLeetCode 2657 – Find the Prefix Common Array of Two Arrays is an interesting prefix and hashing problem that tests your understanding of:Prefix processingHashingFrequency countingSet operationsArray traversalAt first glance, the problem may look confusing because of the term:Prefix Common ArrayBut once you understand the meaning of prefixes and common elements, the problem becomes straightforward.This problem is useful for improving:Prefix-based thinkingHashing intuitionOptimization skillsInterview problem-solving abilityProblem Link🔗 Find the prefix Common Array of Two ArraysProblem StatementYou are given two permutations:A and BBoth arrays contain numbers:1 to nexactly once.You need to create an array:Cwhere:C[i]represents:Count of numbers present in both arrays from index 0 to i.Understanding Prefix Common ArraySuppose:A = [1,3,2,4]B = [3,1,2,4]Prefix at Index 0A Prefix = [1]B Prefix = [3]Common numbers:NoneSo:C[0] = 0Prefix at Index 1A Prefix = [1,3]B Prefix = [3,1]Common numbers:1, 3So:C[1] = 2Final Output[0,2,3,4]Key ObservationBoth arrays are permutations.This means:Every number appears exactly once.Once a number appears in both prefixes, it remains common forever.This simplifies the logic significantly.Brute Force ApproachIntuitionFor every index:Build prefixesCompare elementsCount common numbersBrute Force AlgorithmFor each index:Traverse all previous elementsCheck whether numbers exist in both prefixesCount matchesBrute Force ComplexityTime ComplexityO(N²)because for every index we may scan previous elements.Space ComplexityO(N)Understanding ApproachThis approach uses:HashMapPrefix trackingCounting common valuesThe idea is:Store prefix elements from BTraverse A prefixCount matching numbersThis works because prefixes gradually expand.Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int j = 0; int[] ans = new int[A.length]; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < A.length; i++) { map.put(B[i], i); int counter = 0; int c = 0; for(int a : map.keySet()) { if(map.containsKey(A[c])) { counter++; } c++; } ans[j] = counter; j++; } return ans; }}Better Optimized ApproachWe can solve this more cleanly using:HashSetor frequency counting.Optimized IntuitionAt every index:Add A[i]Add B[i]Track which numbers appearedIf a number appears in both arrays, increase common countBest Optimized Approach Using Frequency ArrayBecause values are from:1 to nwe can use a frequency array.Optimized Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; int[] ans = new int[n]; int[] freq = new int[n + 1]; int common = 0; for(int i = 0; i < n; i++) { freq[A[i]]++; if(freq[A[i]] == 2) common++; freq[B[i]]++; if(freq[B[i]] == 2) common++; ans[i] = common; } return ans; }}Why Does This Work?Every number appears once in A and once in B.So:First appearance → frequency becomes 1Second appearance → frequency becomes 2When frequency becomes:2it means the number has appeared in both prefixes.So we increase:commonDry RunInputA = [1,3,2,4]B = [3,1,2,4]Step 1Index:0Add:1 and 3Frequencies:1 → 13 → 1No common elements.ans[0] = 0Step 2Add:3 and 1Frequencies:1 → 23 → 2Two common elements found.ans[1] = 2Step 3Add:2 and 2Frequency:2 → 2Common becomes:3ans[2] = 3Step 4Add:4 and 4Frequency:4 → 2Common becomes:4ans[3] = 4Final Output[0,2,3,4]Time Complexity AnalysisTime ComplexityO(N²)Nested traversal inside loop.Space ComplexityO(N)Optimized Frequency ApproachTime ComplexityO(N)Single traversal.Space ComplexityO(N)Frequency array.HashMap vs Frequency ArrayApproachTime ComplexitySpace ComplexityHashMapO(N²)O(N)Frequency ArrayO(N)O(N)Interview ExplanationIn interviews, explain:Since both arrays are permutations, every number appears exactly twice overall — once in A and once in B. Using frequency counting, whenever a number’s frequency becomes 2, it means it has appeared in both prefixes.This demonstrates:Prefix understandingOptimization thinkingHashing skillsCommon Mistakes1. Recalculating Common Elements Every TimeThis causes:O(N²)complexity.2. Forgetting Arrays Are PermutationsThis special condition allows frequency optimization.3. Incorrect Prefix LogicRemember:Prefix means elements from 0 to i.FAQsQ1. Why is this called Prefix Common Array?Because:C[i]stores common elements between prefixes ending at index:iQ2. Why does frequency 2 mean common?Because every number appears once in each array.Q3. Which approach is best?Frequency array approach is the most optimized.Q4. Is this problem important for interviews?Yes.It tests:Prefix logicHashingOptimizationArray traversalRelated ProblemsAfter mastering this problem, practice:Intersection of Two ArraysIntersection of Two Arrays IIContains DuplicateSubarray Sum Equals KPrefix SumFind the Difference of Two ArraysConclusionLeetCode 2657 is an excellent prefix and hashing problem.It teaches:Prefix processingFrequency countingOptimization techniquesHashing fundamentalsThe key insight is:A number becomes common exactly when its frequency becomes 2.Once you understand this observation, the optimized solution becomes very simple and efficient.

LeetCodePrefix Common ArrayJavaHashMapHashSetArrayPrefixArrayMedium

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

IntroductionThe Subsets problem (LeetCode 78) is one of the most fundamental and frequently asked questions in coding interviews. It introduces the concept of generating a power set, which is a core idea in recursion, backtracking, and combinatorics.Mastering this problem helps in solving a wide range of advanced problems like combinations, permutations, and decision-based recursion.In this article, we will explore:Intuition behind subsetsRecursive (backtracking) approachIterative (loop-based) approachBit manipulation approachTime and space complexity analysisProblem StatementGiven an integer array nums of unique elements, return all possible subsets (the power set).Key PointsEach element can either be included or excludedNo duplicate subsetsReturn subsets in any orderExamplesExample 1Input:nums = [1, 2, 3]Output:[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Example 2Input:nums = [0]Output:[[], [0]]Key InsightFor each element, there are two choices:Include it OR Exclude itSo total subsets:2^nThis makes it a binary decision tree problem, very similar to:Permutation with SpacesBinary choices recursionBacktracking problemsApproach 1: Recursion + Backtracking (Most Important)IntuitionAt each index:Skip the elementInclude the elementBuild subsets step by step and backtrack.Java Code (With Explanation)import java.util.*;class Solution { List<List<Integer>> liss = new ArrayList<>(); void solve(int[] an, int ind, List<Integer> lis) { // Base case: reached end → one subset formed if (ind == an.length) { liss.add(new ArrayList<>(lis)); // store copy return; } // Choice 1: Do NOT include current element solve(an, ind + 1, lis); // Choice 2: Include current element lis.add(an[ind]); solve(an, ind + 1, lis); // Backtrack: remove last added element lis.remove(lis.size() - 1); } public List<List<Integer>> subsets(int[] nums) { List<Integer> lis = new ArrayList<>(); solve(nums, 0, lis); return liss; }}Dry Run (nums = [1,2])Start: [] → skip 1 → [] → skip 2 → [] → take 2 → [2] → take 1 → [1] → skip 2 → [1] → take 2 → [1,2]Final Output:[], [2], [1], [1,2]Approach 2: Iterative (Loop-Based)IntuitionStart with an empty subset:[ [] ]For each element:Add it to all existing subsetsCodeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); for (int num : nums) { int size = result.size(); for (int i = 0; i < size; i++) { List<Integer> temp = new ArrayList<>(result.get(i)); temp.add(num); result.add(temp); } } return result; }}How It WorksFor [1,2,3]:Start: [[]]Add 1 → [[], [1]]Add 2 → [[], [1], [2], [1,2]]Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Approach 3: Bit ManipulationIntuitionEach subset can be represented using a binary number:For n = 3:000 → []001 → [1]010 → [2]011 → [1,2]...Codeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; int total = 1 << n; // 2^n for (int i = 0; i < total; i++) { List<Integer> subset = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { subset.add(nums[j]); } } result.add(subset); } return result; }}Complexity AnalysisApproachTime ComplexitySpace ComplexityRecursionO(2^n)O(n) stackIterativeO(2^n)O(2^n)Bit ManipulationO(2^n)O(2^n)Why All Approaches Are O(2ⁿ)Because:Total subsets = 2ⁿEach subset takes up to O(n) to constructWhen to Use Which ApproachRecursion / Backtracking → Best for interviews (easy to explain)Iterative → Clean and beginner-friendlyBit Manipulation → Best for optimization & advanced understandingKey TakeawaysSubsets = power set problemEvery element → 2 choicesThink in terms of decision treesBacktracking = build + undo (add/remove)Common Interview VariationsSubsets with duplicatesCombination sumPermutationsK-sized subsetsConclusionThe Subsets problem is a foundational DSA concept that appears across many interview questions. Understanding all approaches—especially recursion and iterative expansion—gives a strong base for solving complex backtracking problems.If you master this pattern, you unlock a whole category of problems in recursion and combinatorics.Frequently Asked Questions (FAQs)1. Why are there 2ⁿ subsets?Because each element has 2 choices: include or exclude.2. Which approach is best for interviews?Recursion + backtracking is the most preferred.3. Is bit manipulation important?Yes, it helps in optimizing and understanding binary patterns.

LeetCodeMediumJavaRecursionBacktracking

LeetCode 3483: Unique 3-Digit Even Numbers – Java Backtracking Solution

IntroductionWhat happens when a small collection of digits needs to be arranged into valid three-digit numbers?There are several conditions to satisfy at the same time:The number must contain exactly three digits.The first digit cannot be 0.The number must be even.A digit can only be used as many times as it appears in the input.Duplicate numbers should be counted only once.Because the input contains at most 10 digits, backtracking is a natural approach. Every possible arrangement can be generated, checked, and stored in a HashSet to ensure that only distinct numbers are counted.Question LinkLeetCode 3483 – Unique 3-Digit Even NumbersApproachThe idea is to build the number one digit at a time.A recursive function maintains:curr — the number currently being constructed.boo[] — tracks which positions of the input array have already been used.ms — a HashSet containing all valid three-digit numbers.At every recursion level, each unused digit is selected and appended to curr.Once three digits have been selected, three checks are performed:Leading zero012is not a valid three-digit number, so it is rejected.Even numberThe generated number must be divisible by 2.DistinctnessThe generated number is inserted into a HashSet, which automatically removes duplicates.Why Track Indices Instead of Digits?Consider:digits = [0, 2, 2]The digit 2 appears twice.Therefore, a valid number such as:220must be allowed.The boolean array tracks positions, not just digit values:Index: 0 1 2Digit: 0 2 2The two copies of 2 are therefore treated as two separate usable elements.The HashSet handles the other side of the problem: different index selections can produce the same number, but the final answer should count that number only once.Java Implementationclass Solution { // Stores every distinct valid three-digit number. HashSet<String> ms = new HashSet<>(); public void sol(int[] dig, String curr, boolean[] boo) { // Once three digits are selected, // check whether the generated number is valid. if (curr.length() == 3) { // A three-digit number cannot start with zero. if (curr.charAt(0) == '0') { return; } // Check whether the number is even. // HashSet automatically handles duplicates. if (ch(curr) && !ms.contains(curr)) { ms.add(curr); } return; } // Try every digit that has not been used yet. for (int i = 0; i < dig.length; i++) { // Skip the current digit if its array position // has already been used in this number. if (boo[i]) continue; String vl = String.valueOf(dig[i]); // Mark this position as used. boo[i] = true; // Add the digit to the current number // and continue building the number. sol(dig, curr + vl, boo); // Backtrack: make this position available // for another possible arrangement. boo[i] = false; } } // Checks whether the generated number is even. public boolean ch(String s) { int n = Integer.valueOf(s); return n % 2 == 0 ? true : false; } public int totalNumbers(int[] digits) { // Tracks which positions of the input array // are currently being used. boolean[] boo = new boolean[digits.length]; // Start generating numbers from an empty string. sol(digits, "", boo); // HashSet contains only distinct valid numbers. return ms.size(); }}Backtracking in ActionConsider:digits = [1, 2, 3, 4]The recursion starts with an empty string:""Choose 1:"1"Then choose 2:"12"Then choose 3:"123"The number has three digits, but 123 is odd, so it is rejected.Backtracking returns to:"12"and tries 4:"124"This number is three digits, does not start with zero, and is even.Therefore:124 → validThe recursion continues exploring other arrangements.Handling Duplicate DigitsConsider:digits = [0, 2, 2]The two 2s have different indices.Some recursion branches may therefore generate the same number:202from different copies of 2.Without a HashSet, these would be counted multiple times.With:HashSet<String> msonly one copy remains.The valid numbers are:202220Therefore:Answer = 2Dry RunConsider:digits = [1, 2, 3, 4]Some of the generated permutations include:123 → odd → reject124 → even → add132 → even → add134 → even → add142 → even → addThe recursion continues for all possible selections.Eventually, the set contains:124132134142214234312314324342412432So:ms.size() = 12The final answer is:12Why a HashSet Is UsefulThere are two separate concerns in this problem.Generating valid arrangementsBacktracking ensures that every possible selection of three positions is explored.Removing duplicatesThe HashSet ensures that identical numbers generated through different index choices are counted only once.This combination is especially useful when the input contains duplicate values.Complexity AnalysisLet n be the number of digits.At most 10 digits are given, and only three positions are selected.The number of possible index arrangements is:P(n, 3) = n × (n - 1) × (n - 2)Therefore, the number of generated arrangements is O(n³).For each completed arrangement, converting/checking the three-digit number takes constant time because the number always has exactly three digits.Time ComplexityO(n³)With n ≤ 10, this is very small in practice.Space ComplexityThe recursion depth is at most 3, while the HashSet stores the distinct valid numbers.So the auxiliary recursion space is O(1), excluding the result set.The result set contains at most a constant number of three-digit numbers because there are only 900 possible three-digit numbers.A Simpler ObservationThere is another way to think about the problem.A three-digit even number has the structure:Hundreds → Tens → UnitsThe units digit must be one of:0, 2, 4, 6, 8The hundreds digit cannot be zero.The tens digit can be any remaining available digit.This means the problem could also be solved by directly choosing:first digitsecond digitthird digitand checking whether the resulting number is valid.The backtracking solution generalizes this idea nicely because it systematically explores all possibilities.Interview TipWhen a problem asks to create numbers, strings, or arrangements from a small collection of elements, look for permutation/backtracking patterns.A useful checklist is:What is being built?↓How many elements are needed?↓Can an element be reused?↓How are duplicates handled?↓What makes a completed arrangement valid?For this problem:Build → 3-digit numberReuse → No, each copy onceDuplicates → HashSetValidity → No leading zero + evenThat immediately points toward a small backtracking solution.ConclusionLeetCode 3483 is a good introduction to combining backtracking with duplicate handling.The recursive function explores every possible three-digit arrangement while the boolean array ensures that each input position is used at most once. Once a number is completed, it is checked for the leading-zero and even-number conditions.Finally, a HashSet guarantees that duplicate numbers are counted only once.With at most 10 input digits and only three positions to fill, the brute-force search remains highly efficient and easy to understand.

LeetCodeJavaBacktrackingRecursionHashSetArraysPermutationsStringEasy

LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

IntroductionLeetCode 2784 – Check if Array is Good is a beginner-friendly array and hashing problem that tests your understanding of:Frequency countingHashMap usageArray validationPermutation logicEdge case handlingAlthough the problem looks simple initially, many candidates fail because they misunderstand the exact structure of the required array.This problem is commonly asked to test:Attention to detailLogical validationCounting techniquesHashing fundamentalsProblem Link🔗 https://leetcode.com/problems/check-if-array-is-good/Problem StatementAn array is considered good if it is a permutation of:base[n] = [1, 2, 3, ..., n-1, n, n]Meaning:Numbers from:1 to n-1appear exactly once.Number:nappears exactly twice.You need to return:trueif the given array is good, otherwise:falseUnderstanding the PatternA valid good array must follow:[1, 2, 3, ..., n-1, n, n]Examples:[1,1][1,2,3,3][1,2,3,4,4]Invalid examples:[1,2,2][1,2,4,4][1,1,2,2]Key ObservationsObservation 1The maximum element determines:nObservation 2Array size must be:n + 1because:1 to n-1 => n-1 elementsn appears twice => 2 elementsTotal = n + 1Observation 3Frequency conditions:NumberFrequency1 to n-1Exactly 1nExactly 2Brute Force ApproachIdeaSort arrayCompare with expected arrayReturn resultBrute Force AlgorithmStep 1Find maximum element:nStep 2Create expected array:[1,2,3,...,n,n]Step 3Sort both arrays and compare.Brute Force ComplexityTime ComplexityO(N log N)due to sorting.Space ComplexityO(N)Optimized HashMap ApproachInstead of sorting:Count frequencies directlyValidate conditionsThis makes the solution faster and cleaner.Intuition Behind HashMap SolutionWe store frequency of every number.Then verify:Maximum element appears twiceEvery other number appears onceArray length equals:max + 1Java HashMap Solutionclass Solution { public boolean isGood(int[] nums) { if(nums.length == 1) return false; int maxElement = Integer.MIN_VALUE; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { map.put(nums[i], map.getOrDefault(nums[i], 0) + 1); maxElement = Math.max(maxElement, nums[i]); } int n = maxElement; if(nums.length != n + 1) { return false; } for(int i = 1; i <= n; i++) { if(!map.containsKey(i)) { return false; } if(i == n) { if(map.get(i) != 2) return false; } else { if(map.get(i) != 1) return false; } } return true; }}Dry RunInputnums = [1,3,3,2]Step 1 – Find MaximumMaximum element:3So:n = 3Step 2 – Length CheckExpected length:n + 1 = 4Actual length:4Valid.Step 3 – Frequency CountFrequency map:NumberCount112132Step 4 – Validate ConditionsNumbers 1 and 2 appear once ✅Number 3 appears twice ✅Return:trueEdge CasesCase 1[1]Invalid because:base[1] = [1,1]Case 2[1,1]Valid.Case 3[1,2,2]Invalid because:n = 2Expected:[1,2,2]Actually valid.Case 4[3,4,4,1,2,1]Invalid because:length != max + 1Optimized Alternative Using SortingAnother clean solution:Sort arrayVerify:nums[i] == i + 1for all except last.Last two elements should be equal.Java Sorting Solutionclass Solution { public boolean isGood(int[] nums) { Arrays.sort(nums); int n = nums.length - 1; for(int i = 0; i < n; i++) { if(nums[i] != i + 1) return false; } return nums[n] == n; }}Time Complexity AnalysisHashMap SolutionTime ComplexityO(N)Space ComplexityO(N)Sorting SolutionTime ComplexityO(N log N)Space ComplexityO(1)excluding sorting overhead.HashMap vs SortingApproachTime ComplexitySpace ComplexityHashMapO(N)O(N)SortingO(N log N)O(1)Interview ExplanationIn interviews, explain:A good array must follow the exact pattern [1,2,3,...,n,n]. The maximum element determines n, and frequency counting helps verify whether all required numbers appear correctly.This demonstrates strong understanding of:Frequency countingValidation logicEdge case handlingCommon Mistakes1. Forgetting Length CheckAlways verify:length == max + 12. Ignoring Missing NumbersArray must contain:1 to ncompletely.3. Wrong Frequency ValidationOnly maximum element should appear twice.All others must appear once.FAQsQ1. Why does maximum element determine n?Because:base[n]always ends with:n,nQ2. Why should array size be n + 1?Because:1 to n-1 => n-1 elementsn repeated twice => 2 elementsTotal = n+1Q3. Which approach is better?HashMap solution is faster.Sorting solution is simpler.Q4. Is this problem important for interviews?Yes.It tests:HashingValidation logicEdge case thinkingRelated ProblemsAfter mastering this problem, practice:Contains DuplicateFind All Duplicates in an ArrayValid AnagramConclusionLeetCode 2784 is a great beginner-friendly hashing problem.It teaches:Frequency countingValidation logicHashMap usageEdge case handlingThe key insight is:A good array must exactly match the structure [1,2,3,...,n,n].Once you understand this pattern, the problem becomes straightforward and easy to implement.

LeetCodeJavaHashMapArrayFrequency CountEasy

Recursion in Java - Complete Guide With Examples and Practice Problems

IntroductionIf there is one topic in programming that confuses beginners more than anything else, it is recursion. Most people read the definition, nod their head, and then immediately freeze when they have to write recursive code themselves.The problem is not that recursion is genuinely hard. The problem is that most explanations start with code before building the right mental model. Once you have the right mental model, recursion clicks permanently and you start seeing it everywhere — in tree problems, graph problems, backtracking, dynamic programming, divide and conquer, and more.This guide covers everything from the ground up. What recursion is, how the call stack works, how to identify base cases and recursive cases, every type of recursion, common patterns, time and space complexity analysis, the most common mistakes, and the top LeetCode problems to practice.By the end of this article, recursion will not feel like magic anymore. It will feel like a natural tool you reach for confidently.What Is Recursion?Recursion is when a function calls itself to solve a smaller version of the same problem.That is the complete definition. But let us make it concrete.Imagine you want to count down from 5 to 1. One way is a loop. Another way is — print 5, then solve the exact same problem for counting down from 4 to 1. Then print 4, solve for 3. And so on until you reach the base — there is nothing left to count down.void countDown(int n) { if (n == 0) return; // stop here System.out.println(n); countDown(n - 1); // solve the smaller version}The function countDown calls itself with a smaller input each time. Eventually it reaches 0 and stops. That stopping condition is the most important part of any recursive function — the base case.The Two Parts Every Recursive Function Must HaveEvery correctly written recursive function has exactly two parts. Without both, the function either gives wrong answers or runs forever.Part 1: Base CaseThe base case is the condition under which the function stops calling itself and returns a direct answer. It is the smallest version of the problem that you can solve without any further recursion.Without a base case, recursion never stops and you get a StackOverflowError — Java's way of telling you the call stack ran out of memory.Part 2: Recursive CaseThe recursive case is where the function calls itself with a smaller or simpler input — moving closer to the base case with each call. If your recursive case does not make the problem smaller, you have an infinite loop.Think of it like a staircase. The base case is the ground floor. The recursive case is each step going down. Every step must genuinely bring you one level closer to the ground.How Recursion Works — The Call StackThis is the mental model that most explanations skip, and it is the reason recursion confuses people.Every time a function is called in Java, a new stack frame is created and pushed onto the call stack. This frame stores the function's local variables, parameters, and where to return to when the function finishes.When a recursive function calls itself, a new frame is pushed on top. When that call finishes, its frame is popped and execution returns to the previous frame.Let us trace countDown(3) through the call stack:countDown(3) called → frame pushed prints 3 calls countDown(2) → frame pushed prints 2 calls countDown(1) → frame pushed prints 1 calls countDown(0) → frame pushed n == 0, return → frame popped back in countDown(1), return → frame popped back in countDown(2), return → frame popped back in countDown(3), return → frame poppedOutput: 3, 2, 1The call stack grows as calls go deeper, then shrinks as calls return. This is why recursion uses O(n) space for n levels deep — each level occupies one stack frame in memory.Your First Real Recursive Function — FactorialFactorial is the classic first recursion example. n! = n × (n-1) × (n-2) × ... × 1Notice the pattern — n! = n × (n-1)!. The factorial of n is n times the factorial of n-1. That recursive structure makes it perfect for recursion.public int factorial(int n) { // base case if (n == 0 || n == 1) return 1; // recursive case return n * factorial(n - 1);}Dry Run — factorial(4)factorial(4)= 4 * factorial(3)= 4 * 3 * factorial(2)= 4 * 3 * 2 * factorial(1)= 4 * 3 * 2 * 1= 24The call stack builds up going in, then multiplications happen coming back out. This "coming back out" phase is called the return phase or unwinding of the stack.Time Complexity: O(n) — n recursive calls Space Complexity: O(n) — n frames on the call stackThe Two Phases of RecursionEvery recursive function has two phases and understanding both is critical.Phase 1: The Call Phase (Going In)This happens as the function keeps calling itself with smaller inputs. Things you do before the recursive call happen in this phase — in order from the outermost call to the innermost.Phase 2: The Return Phase (Coming Back Out)This happens as each call finishes and returns to its caller. Things you do after the recursive call happen in this phase — in reverse order, from the innermost call back to the outermost.This distinction explains why the output order can be surprising:void printBothPhases(int n) { if (n == 0) return; System.out.println("Going in: " + n); // call phase printBothPhases(n - 1); System.out.println("Coming out: " + n); // return phase}For printBothPhases(3):Going in: 3Going in: 2Going in: 1Coming out: 1Coming out: 2Coming out: 3This two-phase understanding is what makes problems like reversing a string or printing a linked list backwards via recursion feel natural.Types of RecursionRecursion is not one-size-fits-all. There are several distinct types and knowing which type applies to a problem shapes how you write the solution.1. Direct RecursionThe function calls itself directly. This is the most common type — what we have seen so far.void direct(int n) { if (n == 0) return; direct(n - 1); // calls itself}2. Indirect RecursionFunction A calls Function B which calls Function A. They form a cycle.void funcA(int n) { if (n <= 0) return; System.out.println("A: " + n); funcB(n - 1);}void funcB(int n) { if (n <= 0) return; System.out.println("B: " + n); funcA(n - 1);}Used in: state machines, mutual recursion in parsers, certain mathematical sequences.3. Tail RecursionThe recursive call is the last operation in the function. Nothing happens after the recursive call returns — no multiplication, no addition, nothing.// NOT tail recursive — multiplication happens after returnint factorial(int n) { if (n == 1) return 1; return n * factorial(n - 1); // multiply after return — not tail}// Tail recursive — recursive call is the last thingint factorialTail(int n, int accumulator) { if (n == 1) return accumulator; return factorialTail(n - 1, n * accumulator); // last operation}Why does tail recursion matter? In languages that support tail call optimization (like Scala, Kotlin, and many functional languages), tail recursive functions can be converted to iteration internally — no stack frame accumulation, O(1) space. Java does NOT perform tail call optimization, but understanding tail recursion is still important for interviews and functional programming concepts.4. Head RecursionThe recursive call happens first, before any other processing. All processing happens in the return phase.void headRecursion(int n) { if (n == 0) return; headRecursion(n - 1); // call first System.out.println(n); // process after}// Output: 1 2 3 4 5 (processes in reverse order of calls)5. Tree RecursionThe function makes more than one recursive call per invocation. This creates a tree of calls rather than a linear chain. Fibonacci is the classic example.int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // TWO recursive calls}The call tree for fibonacci(4): fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0)Time Complexity: O(2ⁿ) — exponential! Each call spawns two more. Space Complexity: O(n) — maximum depth of the call treeThis is why memoization (caching results) is so important for tree recursion — it converts O(2ⁿ) to O(n) by never recomputing the same subproblem twice.6. Mutual RecursionA specific form of indirect recursion where two functions call each other alternately to solve a problem. Different from indirect recursion in that the mutual calls are the core mechanism of the solution.// Check if a number is even or odd using mutual recursionboolean isEven(int n) { if (n == 0) return true; return isOdd(n - 1);}boolean isOdd(int n) { if (n == 0) return false; return isEven(n - 1);}Common Recursion Patterns in DSAThese are the patterns you will see over and over in interview problems. Recognizing them is more important than memorizing solutions.Pattern 1: Linear Recursion (Do Something, Recurse on Rest)Process the current element, then recurse on the remaining problem.// Sum of arrayint arraySum(int[] arr, int index) { if (index == arr.length) return 0; // base case return arr[index] + arraySum(arr, index + 1); // current + rest}Pattern 2: Divide and Conquer (Split Into Two Halves)Split the problem into two halves, solve each recursively, combine results.// Merge Sortvoid mergeSort(int[] arr, int left, int right) { if (left >= right) return; // base case — single element int mid = (left + right) / 2; mergeSort(arr, left, mid); // sort left half mergeSort(arr, mid + 1, right); // sort right half merge(arr, left, mid, right); // combine}Pattern 3: Backtracking (Try, Recurse, Undo)Try a choice, recurse to explore it, undo the choice when backtracking.// Generate all subsetsvoid subsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { if (index == nums.length) { result.add(new ArrayList<>(current)); return; } // Choice 1: include nums[index] current.add(nums[index]); subsets(nums, index + 1, current, result); current.remove(current.size() - 1); // undo // Choice 2: exclude nums[index] subsets(nums, index + 1, current, result);}Pattern 4: Tree Recursion (Left, Right, Combine)Recurse on left subtree, recurse on right subtree, combine or process results.// Height of binary treeint height(TreeNode root) { if (root == null) return 0; // base case int leftHeight = height(root.left); // solve left int rightHeight = height(root.right); // solve right return 1 + Math.max(leftHeight, rightHeight); // combine}Pattern 5: Memoization (Cache Recursive Results)Store results of recursive calls so the same subproblem is never solved twice.Map<Integer, Integer> memo = new HashMap<>();int fibonacci(int n) { if (n <= 1) return n; if (memo.containsKey(n)) return memo.get(n); // return cached int result = fibonacci(n - 1) + fibonacci(n - 2); memo.put(n, result); // cache before returning return result;}This converts Fibonacci from O(2ⁿ) to O(n) time with O(n) space — a massive improvement.Recursion vs Iteration — When to Use WhichThis is one of the most common interview questions about recursion. Here is a clear breakdown:Use Recursion when:The problem has a naturally recursive structure (trees, graphs, divide and conquer)The solution is significantly cleaner and easier to understand recursivelyThe problem involves exploring multiple paths or choices (backtracking)The depth of recursion is manageable (not too deep to cause stack overflow)Use Iteration when:The problem is linear and a loop is equally clearMemory is a concern (iteration uses O(1) stack space vs O(n) for recursion)Performance is critical and function call overhead mattersJava's stack size limit could be hit (default around 500-1000 frames for deep recursion)The key rule: Every recursive solution can be converted to an iterative one (usually using an explicit stack). But recursive solutions for tree and graph problems are almost always cleaner to write and understand.Time and Space Complexity of Recursive FunctionsAnalyzing complexity for recursive functions requires a specific approach.The Recurrence Relation MethodExpress the time complexity as a recurrence relation and solve it.Factorial:T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) = T(1) + n×O(1) = O(n)Fibonacci (naive):T(n) = T(n-1) + T(n-2) + O(1) ≈ 2×T(n-1) = O(2ⁿ)Binary Search:T(n) = T(n/2) + O(1) = O(log n) [by Master Theorem]Merge Sort:T(n) = 2×T(n/2) + O(n) = O(n log n) [by Master Theorem]Space Complexity Rule for RecursionSpace complexity of a recursive function = maximum depth of the call stack × space per frameLinear recursion (factorial, sum): O(n) spaceBinary recursion (Fibonacci naive): O(n) space (maximum depth, not number of nodes)Divide and conquer (merge sort): O(log n) space (depth of recursion tree)Memoized Fibonacci: O(n) space (memo table + call stack)Classic Recursive Problems With SolutionsProblem 1: Reverse a StringString reverse(String s) { if (s.length() <= 1) return s; // base case // last char + reverse of everything before last char return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));}Dry run for "hello":reverse("hello") = 'o' + reverse("hell")reverse("hell") = 'l' + reverse("hel")reverse("hel") = 'l' + reverse("he")reverse("he") = 'e' + reverse("h")reverse("h") = "h"Unwinding: "h" → "he" → "leh" → "lleh" → "olleh" ✅Problem 2: Power Function (x^n)double power(double x, int n) { if (n == 0) return 1; // base case if (n < 0) return 1.0 / power(x, -n); // handle negative if (n % 2 == 0) { double half = power(x, n / 2); return half * half; // x^n = (x^(n/2))^2 } else { return x * power(x, n - 1); }}This is the fast power algorithm — O(log n) time instead of O(n).Problem 3: Fibonacci With Memoizationint[] memo = new int[100];Arrays.fill(memo, -1);int fib(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib(n - 1) + fib(n - 2); return memo[n];}Time: O(n) — each value computed once Space: O(n) — memo array + call stackProblem 4: Tower of HanoiThe classic recursion teaching problem. Move n disks from source to destination using a helper rod.void hanoi(int n, char source, char destination, char helper) { if (n == 1) { System.out.println("Move disk 1 from " + source + " to " + destination); return; } // Move n-1 disks from source to helper hanoi(n - 1, source, helper, destination); // Move the largest disk from source to destination System.out.println("Move disk " + n + " from " + source + " to " + destination); // Move n-1 disks from helper to destination hanoi(n - 1, helper, destination, source);}Time Complexity: O(2ⁿ) — minimum moves required is 2ⁿ - 1 Space Complexity: O(n) — call stack depthProblem 5: Generate All Subsets (Power Set)void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { result.add(new ArrayList<>(current)); // add current subset for (int i = index; i < nums.length; i++) { current.add(nums[i]); // include generateSubsets(nums, i + 1, current, result); // recurse current.remove(current.size() - 1); // exclude (backtrack) }}For [1, 2, 3] — generates all 8 subsets: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]Time: O(2ⁿ) — 2ⁿ subsets Space: O(n) — recursion depthProblem 6: Binary Search Recursivelyint binarySearch(int[] arr, int target, int left, int right) { if (left > right) return -1; // base case — not found int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right); else return binarySearch(arr, target, left, mid - 1);}Time: O(log n) — halving the search space each time Space: O(log n) — log n frames on the call stackRecursion on Trees — The Natural HabitatTrees are where recursion truly shines. Every tree problem becomes elegant with recursion because a tree is itself a recursive structure — each node's left and right children are trees themselves.// Maximum depth of binary treeint maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}// Check if tree is symmetricboolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);}// Path sum — does any root-to-leaf path sum to target?boolean hasPathSum(TreeNode root, int target) { if (root == null) return false; if (root.left == null && root.right == null) return root.val == target; return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);}Notice the pattern in all three — base case handles null, recursive case handles left and right subtrees, result combines both.How to Think About Any Recursive Problem — Step by StepThis is the framework you should apply to every new recursive problem you encounter:Step 1 — Identify the base case What is the smallest input where you know the answer directly without any recursion? For arrays it is usually empty array or single element. For trees it is null node. For numbers it is 0 or 1.Step 2 — Trust the recursive call Assume your function already works correctly for smaller inputs. Do not trace through the entire recursion mentally — just trust it. This is the Leap of Faith and it is what makes recursion feel natural.Step 3 — Express the current problem in terms of smaller problems How does the answer for size n relate to the answer for size n-1 (or n/2, or subtrees)? This relationship is your recursive case.Step 4 — Make sure each call moves toward the base case The input must become strictly smaller with each call. If it does not, you have infinite recursion.Step 5 — Write the base case first, then the recursive case Always. Writing the recursive case first leads to bugs because you have not defined when to stop.Common Mistakes and How to Avoid ThemMistake 1: Missing or wrong base case The most common mistake. Missing the base case causes StackOverflowError. Wrong base case causes wrong answers.Always ask — what is the simplest possible input, and what should the function return for it? Write that case first.Mistake 2: Not moving toward the base case If you call factorial(n) inside factorial(n) without reducing n, you loop forever. Every recursive call must make the problem strictly smaller.Mistake 3: Trusting your brain to trace deep recursion Do not try to trace 10 levels of recursion in your head. Trust the recursive call, verify the base case, and check that each call reduces the problem. That is all you need.Mistake 4: Forgetting to return the recursive result// WRONG — result is computed but not returnedint sum(int n) { if (n == 0) return 0; sum(n - 1) + n; // computed but discarded!}// CORRECTint sum(int n) { if (n == 0) return 0; return sum(n - 1) + n;}Mistake 5: Modifying shared state without backtracking In backtracking problems, if you add something to a list before a recursive call, you must remove it after the call returns. Forgetting to backtrack leads to incorrect results and is one of the trickiest bugs to find.Mistake 6: Recomputing the same subproblems Naive Fibonacci computes fib(3) multiple times when computing fib(5). Use memoization whenever you notice overlapping subproblems in your recursion tree.Top LeetCode Problems on RecursionThese are organized by pattern — work through them in this order for maximum learning:Pure Recursion Basics:509. Fibonacci Number — Easy — start here, implement with and without memoization344. Reverse String — Easy — recursion on arrays206. Reverse Linked List — Easy — recursion on linked list50. Pow(x, n) — Medium — fast power with recursionTree Recursion (Most Important):104. Maximum Depth of Binary Tree — Easy — simplest tree recursion112. Path Sum — Easy — decision recursion on tree101. Symmetric Tree — Easy — mutual recursion on tree110. Balanced Binary Tree — Easy — bottom-up recursion236. Lowest Common Ancestor of a Binary Tree — Medium — classic tree recursion124. Binary Tree Maximum Path Sum — Hard — advanced tree recursionDivide and Conquer:148. Sort List — Medium — merge sort on linked list240. Search a 2D Matrix II — Medium — divide and conquerBacktracking:78. Subsets — Medium — generate all subsets46. Permutations — Medium — generate all permutations77. Combinations — Medium — generate combinations79. Word Search — Medium — backtracking on grid51. N-Queens — Hard — classic backtrackingMemoization / Dynamic Programming:70. Climbing Stairs — Easy — Fibonacci variant with memoization322. Coin Change — Medium — recursion with memoization to DP139. Word Break — Medium — memoized recursionRecursion Cheat Sheet// Linear recursion templatereturnType solve(input) { if (baseCase) return directAnswer; // process current return solve(smallerInput);}// Tree recursion templatereturnType solve(TreeNode root) { if (root == null) return baseValue; returnType left = solve(root.left); returnType right = solve(root.right); return combine(left, right, root.val);}// Backtracking templatevoid backtrack(choices, current, result) { if (goalReached) { result.add(copy of current); return; } for (choice : choices) { make(choice); // add to current backtrack(...); // recurse undo(choice); // remove from current }}// Memoization templateMap<Input, Output> memo = new HashMap<>();returnType solve(input) { if (baseCase) return directAnswer; if (memo.containsKey(input)) return memo.get(input); returnType result = solve(smallerInput); memo.put(input, result); return result;}FAQs — People Also AskQ1. What is recursion in Java with a simple example? Recursion is when a function calls itself to solve a smaller version of the same problem. A simple example is factorial — factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) and so on until factorial(1) returns 1 directly.Q2. What is the difference between recursion and iteration? Iteration uses loops (for, while) and runs in O(1) space. Recursion uses function calls and uses O(n) stack space for n levels deep. Recursion is often cleaner for tree and graph problems. Iteration is better when memory is a concern or the problem is inherently linear.Q3. What causes StackOverflowError in Java recursion? StackOverflowError happens when recursion goes too deep — too many frames accumulate on the call stack before any of them return. This is caused by missing base case, wrong base case, or input too large for Java's default stack size limit.Q4. What is the difference between recursion and dynamic programming? Recursion solves a problem by breaking it into subproblems. Dynamic programming is recursion plus memoization — storing results of subproblems so they are never computed twice. DP converts exponential recursive solutions into polynomial ones by eliminating redundant computation.Q5. What is tail recursion and does Java support tail call optimization? Tail recursion is when the recursive call is the absolute last operation in the function. Java does NOT support tail call optimization — Java always creates a new stack frame for each call even if it is tail recursive. Languages like Scala and Kotlin (on the JVM) do support it with the tailrec keyword.Q6. How do you convert recursion to iteration? Every recursive solution can be converted to iterative using an explicit stack data structure. The call stack's behavior is replicated manually — push the initial call, loop while stack is not empty, pop, process, and push sub-calls. Tree traversals are a common example of this conversion.ConclusionRecursion is not magic. It is a systematic way of solving problems by expressing them in terms of smaller versions of themselves. Once you internalize the two parts (base case and recursive case), understand the call stack mentally, and learn to trust the recursive call rather than trace it completely, everything clicks.The learning path from here is clear — start with simple problems like Fibonacci and array sum. Move to tree problems where recursion is most natural. Then tackle backtracking. Finally add memoization to bridge into dynamic programming.Every hour you spend understanding recursion deeply pays dividends across the entire rest of your DSA journey. Trees, graphs, divide and conquer, backtracking, dynamic programming — all of them build on this foundation.

RecursionJavaBase CaseCall StackBacktrackingDynamic Programming

LeetCode 2126: Destroying Asteroids – Java Greedy Algorithm Solution with Dry Run

IntroductionLeetCode 2126 – Destroying Asteroids is a classic greedy algorithm problem that tests your ability to:Recognize optimal orderingUse sorting effectivelyApply greedy decision-makingHandle large integer growthUnderstand simulation problemsThis is a very interview-friendly problem because the optimal strategy is not immediately obvious.Problem Link🔗 https://leetcode.com/problems/destroying-asteroids/Problem StatementYou are given:An integer mass representing the planet’s initial massAn array asteroidsRules:If planet mass ≥ asteroid mass → asteroid is destroyedPlanet gains asteroid massOtherwise → planet gets destroyedReturn:true -> if all asteroids can be destroyedfalse -> otherwiseExampleInputmass = 10asteroids = [3,9,19,5,21]OutputtrueKey ObservationThe most important insight:Destroy smaller asteroids first.Why?Because every destroyed asteroid increases planet mass.So destroying smaller asteroids early helps you grow enough to destroy larger ones later.IntuitionSuppose:mass = 5asteroids = [100,1,2]If you attack:100 firstYou instantly lose.But if you destroy:1 → 2Your mass becomes:5 + 1 + 2 = 8Still not enough for 100.So answer remains false.This demonstrates:Ordering matters.Greedy StrategyThe optimal strategy is:Step 1Sort asteroids in ascending order.Step 2Destroy the smallest asteroid possible first.Step 3Keep increasing mass.Why Sorting WorksIf you cannot destroy the smallest remaining asteroid:You definitely cannot destroy larger asteroids either.That is why sorting guarantees the optimal greedy order.Java Solutionclass Solution { public boolean asteroidsDestroyed(int mass, int[] asteroids) { Arrays.sort(asteroids); if(mass >= asteroids[asteroids.length - 1]) { return true; } for(int i = 0; i < asteroids.length; i++) { if(mass >= asteroids[asteroids.length - 1]) { return true; } if(asteroids[i] <= mass) { mass += asteroids[i]; } if(mass < asteroids[i]) { return false; } } return true; }}Cleaner Optimized VersionOne important improvement:Use long instead of int.Why?Because mass can grow very large.Optimized Java Solutionclass Solution { public boolean asteroidsDestroyed(int mass, int[] asteroids) { Arrays.sort(asteroids); long currentMass = mass; for(int asteroid : asteroids) { if(currentMass < asteroid) { return false; } currentMass += asteroid; } return true; }}Why Use Long?Constraints allow:1 <= asteroids.length <= 1000001 <= asteroid[i] <= 100000Mass can exceed:Integer.MAX_VALUEUsing long prevents overflow issues.Dry RunInputmass = 10asteroids = [3,9,19,5,21]Step 1: Sort[3,5,9,19,21]Step 2: Destroy AsteroidsDestroy 310 >= 3mass = 13Destroy 513 >= 5mass = 18Destroy 918 >= 9mass = 27Destroy 1927 >= 19mass = 46Destroy 2146 >= 21mass = 67All asteroids destroyed.Final OutputtrueBrute Force ApproachA brute force approach would try:All possible asteroid ordersThis means:N! permutationsWhich is impossible for:N = 100000So brute force is completely infeasible.Why Greedy Is OptimalGreedy works because:Smaller asteroids are easiest to destroyThey increase massIncreased mass helps destroy bigger asteroidsThis creates a natural optimal progression.Time Complexity AnalysisSortingO(N log N)TraversalO(N)Total Time ComplexityO(N log N)Space ComplexityO(1)Ignoring sorting space.Interview ExplanationIn interviews, explain:Since destroying an asteroid increases our mass, the optimal strategy is to destroy smaller asteroids first. Sorting ensures we always maximize future growth opportunities.This demonstrates:Greedy thinkingSorting optimizationSimulation handlingProof of correctnessCommon Mistakes1. Not SortingWithout sorting:You may attempt larger asteroids too early.2. Using int Instead of longMass can overflow.Always use:long currentMass3. Brute Force PermutationsTrying all orders leads to:O(N!)which is impossible.4. Incorrect Early ReturnYour logic should only fail when:currentMass < asteroidFAQsQ1. Why is sorting necessary?Sorting guarantees we always destroy the smallest possible asteroid first.Q2. Is this a greedy problem?Yes.The optimal local decision:Destroy smallest asteroid firstleads to global optimality.Q3. Why use long?Because mass can grow beyond integer limits.Q4. Is this asked in interviews?Yes.It is a common greedy + sorting interview problem.ConclusionLeetCode 2126 is an excellent greedy problem for mastering:Sorting-based optimizationGreedy decision-makingSimulation problemsOverflow handlingInterview reasoningThe key insight is:Always destroy smaller asteroids first to maximize future mass growth.Once this greedy intuition becomes natural, many scheduling and optimization problems become easier to solve.

LeetCodeGreedy AlgorithmJavaSortingArrayMedium

LeetCode 39: Combination Sum – Java Backtracking Solution with Dry Run & Complexity

IntroductionIf you are preparing for coding interviews or improving your Data Structures and Algorithms skills, LeetCode 39 Combination Sum is one of the most important backtracking problems to learn. This problem helps you understand how recursion explores multiple possibilities and how combinations are generated efficiently. It is a foundational problem that builds strong problem-solving skills and prepares you for many advanced recursion and backtracking questions.Why Should You Solve This Problem?Combination Sum is not just another coding question — it teaches you how to think recursively and break a complex problem into smaller decisions. By solving it, you learn how to manage recursive paths, avoid duplicate combinations, and build interview-level backtracking intuition. Once you understand this pattern, problems like subsets, permutations, N-Queens, and Sudoku Solver become much easier to approach.LeetCode Problem LinkProblem Name: Combination SumProblem Link: Combination SumProblem StatementGiven an array of distinct integers called candidates and a target integer target, you need to return all unique combinations where the chosen numbers sum to the target.Important rules:You can use the same number unlimited times.Only unique combinations should be returned.Order of combinations does not matter.ExampleExample 1Input:candidates = [2,3,6,7]target = 7Output:[[2,2,3],[7]]Explanation2 + 2 + 3 = 77 itself equals targetUnderstanding the Problem in Simple WordsWe are given some numbers.We need to:Pick numbers from the arrayAdd them togetherReach the target sumUse numbers multiple times if neededAvoid duplicate combinationsThis problem belongs to the Backtracking + Recursion category.Real-Life AnalogyImagine you have coins of different values.You want to make an exact payment.You can reuse coins multiple times.You need to find every possible valid coin combination.This is exactly what Combination Sum does.Intuition Behind the SolutionAt every index, we have two choices:Pick the current numberSkip the current numberSince numbers can be reused unlimited times, when we pick a number, we stay at the same index.This creates a recursion tree.We continue until:Target becomes 0 → valid answerTarget becomes negative → invalid pathArray ends → stop recursionWhy Backtracking Works HereBacktracking helps us:Explore all possible combinationsUndo previous decisionsTry another pathIt is useful whenever we need:All combinationsAll subsetsPath explorationRecursive searchingApproach 1: Backtracking Using Pick and SkipCore IdeaAt every element:Either take itOr move to next elementJava Code (Pick and Skip Method)class Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] candidates, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}if (index == candidates.length) {return;}if (candidates[index] <= target) {current.add(candidates[index]);solve(candidates, index, target - candidates[index], current);current.remove(current.size() - 1);}solve(candidates, index + 1, target, current);}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Approach 2: Backtracking Using Loop (Optimized)This is the cleaner and more optimized version.Your code belongs to this category.Java Code (Loop-Based Backtracking)class Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] arr, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}if (index == arr.length) {return;}for (int i = index; i < arr.length; i++) {if (arr[i] > target) {continue;}current.add(arr[i]);solve(arr, i, target - arr[i], current);current.remove(current.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Dry Run of the AlgorithmInputcandidates = [2,3,6,7]target = 7Step-by-Step ExecutionStart:solve([2,3,6,7], index=0, target=7, [])Pick 2[2]target = 5Pick 2 again:[2,2]target = 3Pick 2 again:[2,2,2]target = 1No valid choice possible.Backtrack.Try 3[2,2,3]target = 0Valid answer found.Add:[2,2,3]Try 7[7]target = 0Valid answer found.Add:[7]Final Output[[2,2,3],[7]]Recursion Tree Visualization[]/ | | \2 3 6 7/2/2/3Every branch explores a different combination.Time Complexity AnalysisTime ComplexityO(2^Target)More accurately:O(N^(Target/minValue))Where:N = Number of candidatesTarget = Required sumReason:Every number can be picked multiple times.This creates many recursive branches.Space ComplexityO(Target)Reason:Recursion stack stores elements.Maximum recursion depth depends on target.Why We Pass Same Index AgainNotice this line:solve(arr, i, target - arr[i], current);We pass i, not i+1.Why?Because we can reuse the same number unlimited times.If we used i+1, we would move forward and lose repetition.Why Duplicate Combinations Are Not CreatedWe start loop from current index.This guarantees:[2,3]and[3,2]are not both generated.Order remains controlled.Common Mistakes Beginners Make1. Using i+1 Instead of iWrong:solve(arr, i+1, target-arr[i], current)This prevents reuse.2. Forgetting Backtracking StepWrong:current.remove(current.size()-1)Without removing, recursion keeps incorrect values.3. Missing Target == 0 Base CaseThis is where valid answer is stored.Important Interview InsightCombination Sum is a foundational problem.It helps build understanding for:Combination Sum IISubsetsPermutationsN-QueensWord SearchSudoku SolverThis question is frequently asked in coding interviews.Pattern RecognitionUse Backtracking when problem says:Find all combinationsGenerate all subsetsFind all pathsUse recursionExplore possibilitiesOptimized Thinking StrategyWhenever you see:Target sumRepeated selectionMultiple combinationsThink:Backtracking + DFSEdge CasesCase 1candidates = [2]target = 1Output:[]No possible answer.Case 2candidates = [1]target = 3Output:[[1,1,1]]Interview Answer in One Line“We use backtracking to recursively try all candidate numbers while reducing the target and backtrack whenever a path becomes invalid.”Final Java Codeclass Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] arr, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}for (int i = index; i < arr.length; i++) {if (arr[i] > target) {continue;}current.add(arr[i]);solve(arr, i, target - arr[i], current);current.remove(current.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Key TakeawaysCombination Sum uses Backtracking.Reuse same element by passing same index.Target becomes smaller in recursion.Backtracking removes last element.Very important for interview preparation.Frequently Asked QuestionsIs Combination Sum DP or Backtracking?It is primarily solved using Backtracking.Dynamic Programming can also solve it but recursion is more common.Why is this Medium difficulty?Because:Requires recursion understandingRequires backtracking logicRequires duplicate preventionCan we sort the array?Yes.Sorting can help with pruning.ConclusionLeetCode 39 Combination Sum is one of the best problems to learn recursion and backtracking.Once you understand this pattern, many interview problems become easier.The loop-based recursive solution is clean, optimized, and interview-friendly.If you master this question, you gain strong understanding of recursive decision trees and combination generation.

LeetcodeMediumRecursionBacktrackingJava

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

🔗 Problem LinkLeetCode 409 – Longest Palindrome 👉 https://leetcode.com/problems/longest-palindrome/IntroductionThis is one of those problems where you don’t actually need to build the palindrome.You just need to calculate the maximum possible length of a palindrome that can be formed using the given characters.The key idea here is understanding:How palindromes are structured.Once you understand that, the solution becomes straightforward and elegant.📌 Problem UnderstandingYou are given a string s containing:Lowercase lettersUppercase lettersCase-sensitive (meaning 'A' and 'a' are different)You must return:The length of the longest palindrome that can be built using those characters.You can rearrange characters in any order.Example 1Input: s = "abccccdd"Output: 7One possible palindrome:dccaccdLength = 7Example 2Input: s = "a"Output: 1🧠 Key Observation About PalindromesA palindrome:Reads the same forward and backward.Has mirror symmetry.This means:Characters must appear in pairs.At most one character can appear an odd number of times (middle character).🧠 Intuition Behind the ApproachLet’s think step by step:Count frequency of each character.For every character:If frequency is even → use all of them.If frequency is odd → use (frequency - 1).If at least one odd frequency exists → we can place one odd character in the center.That’s it.This is a greedy approach.💻 Your Codeclass Solution { public int longestPalindrome(String s) { if(s.length() == 1) return 1; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0; i < s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } int len =0; boolean odd = false; for(int a : mp.values()){ if(a%2 == 0){ len+=a; }else{ len+=a-1; odd= true; } } if(odd){ return len+1; } return len; }}🔍 Step-by-Step Explanation1️⃣ Edge Caseif(s.length() == 1) return 1;If there is only one character, the answer is 1.2️⃣ Frequency CountingHashMap<Character,Integer> mp = new HashMap<>();for(int i =0; i < s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1);}We count how many times each character appears.3️⃣ Build the Palindrome Lengthint len = 0;boolean odd = false;len → stores palindrome lengthodd → tracks whether any odd frequency exists4️⃣ Process Each Frequencyfor(int a : mp.values()){ if(a % 2 == 0){ len += a; }else{ len += a - 1; odd = true; }}If frequency is even → use all characters.If odd:Use a - 1 (which is even)Keep track that we saw an odd number5️⃣ Add Middle Character If Neededif(odd){ return len + 1;}If at least one odd frequency exists → we can place one character in the center.Otherwise → return len.🎯 Why This WorksIn a palindrome:All characters must appear in pairs (mirrored sides).Only one character can be unpaired (center).So we:Use all even counts.Use even portion of odd counts.Add one center character if possible.⏱ Complexity AnalysisTime Complexity: O(n)One pass to count frequenciesOne pass over map (max 52 characters: A–Z, a–z)Space Complexity: O(52) ≈ O(1)At most 52 distinct characters.🔥 Cleaner Optimization IdeaWe don’t even need a boolean variable.We can simply:Add a / 2 * 2 for every frequencyIf total length < original string length → add 1Example optimized version:class Solution { public int longestPalindrome(String s) { HashMap<Character,Integer> mp = new HashMap<>(); for(char ch : s.toCharArray()){ mp.put(ch, mp.getOrDefault(ch, 0) + 1); } int len = 0; for(int count : mp.values()){ len += (count / 2) * 2; } if(len < s.length()){ len += 1; } return len; }}🏁 Final ThoughtsThis problem teaches:Understanding palindrome structureFrequency countingGreedy logicHandling odd and even countsIt’s a simple but powerful pattern question.If you truly understand this, you can easily solve problems like:Palindrome PermutationLongest Palindrome by Concatenating Two Letter WordsCount Palindromic Subsequences

HashMapStringGreedyFrequency CountLeetCodeEasy

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

IntroductionThe Power Set problem for strings is a classic question in recursion and backtracking, frequently asked in coding interviews and platforms like GeeksforGeeks.In this problem, instead of numbers, we deal with strings and generate all possible subsequences (not substrings). This makes it slightly more interesting and practical for real-world applications like pattern matching, text processing, and combinatorics.In this article, we will cover:Intuition behind subsequencesRecursive (backtracking) approachSorting for lexicographical orderAlternative approachesComplexity analysisProblem StatementGiven a string s of length n, generate all non-empty subsequences of the string.RequirementsReturn only non-empty subsequencesOutput must be in lexicographically sorted orderExamplesExample 1Input:s = "abc"Output:a ab abc ac b bc cExample 2Input:s = "aa"Output:a a aaSubsequence vs Substring (Important)Substring: Continuous charactersSubsequence: Characters can be skippedExample for "abc":Subsequences → a, b, c, ab, ac, bc, abcKey InsightFor every character, we have two choices:Include it OR Exclude itSo total subsequences:2^nWe generate all and then remove the empty string.Approach 1: Recursion (Backtracking)IntuitionAt each index:Skip the characterInclude the characterBuild all combinations recursivelyJava Code (With Explanation)import java.util.*;class Solution { // List to store all subsequences List<String> a = new ArrayList<>(); void sub(String s, int ind, String curr) { // Base case: reached end of string if (ind == s.length()) { a.add(curr); // add current subsequence return; } // Choice 1: Exclude current character sub(s, ind + 1, curr); // Choice 2: Include current character sub(s, ind + 1, curr + s.charAt(ind)); } public List<String> AllPossibleStrings(String s) { // Start recursion sub(s, 0, ""); // Remove empty string (not allowed) a.remove(""); // Sort lexicographically Collections.sort(a); return a; }}Step-by-Step Dry Run (s = "abc")Start: ""→ Exclude 'a' → "" → Exclude 'b' → "" → Exclude 'c' → "" → Include 'c' → "c" → Include 'b' → "b" → Exclude 'c' → "b" → Include 'c' → "bc"→ Include 'a' → "a" → Exclude 'b' → "a" → Exclude 'c' → "a" → Include 'c' → "ac" → Include 'b' → "ab" → Exclude 'c' → "ab" → Include 'c' → "abc"Final Output (After Sorting)a ab abc ac b bc cApproach 2: Bit ManipulationIntuitionEach subsequence can be represented using binary numbers:0 → exclude1 → includeCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); int n = s.length(); int total = 1 << n; // 2^n for (int i = 1; i < total; i++) { // start from 1 to avoid empty StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { sb.append(s.charAt(j)); } } result.add(sb.toString()); } Collections.sort(result); return result; }}Approach 3: Iterative (Expanding List)IdeaStart with empty listFor each character:Add it to all existing subsequencesCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); result.add(""); for (char ch : s.toCharArray()) { int size = result.size(); for (int i = 0; i < size; i++) { result.add(result.get(i) + ch); } } result.remove(""); Collections.sort(result); return result; }}Complexity AnalysisTime Complexity: O(n × 2ⁿ)Space Complexity: O(n × 2ⁿ)Why?Total subsequences = 2ⁿEach subsequence takes O(n) to buildWhy Sorting is RequiredThe recursion generates subsequences in random order, so we sort them:Collections.sort(result);This ensures lexicographical order as required.Key TakeawaysThis is a power set problem for stringsEach character → 2 choicesRecursion = most intuitive approachBit manipulation = most optimized thinkingAlways remove empty string if requiredCommon Interview VariationsSubsets of arrayPermutations of stringCombination sumSubsequence with conditionsConclusionThe Power Set problem is a fundamental building block in recursion and combinatorics. Once you understand the include/exclude pattern, you can solve a wide range of problems efficiently.Mastering this will significantly improve your ability to tackle backtracking and decision tree problems.Frequently Asked Questions (FAQs)1. Why is the empty string removed?Because the problem requires only non-empty subsequences.2. Why is time complexity O(n × 2ⁿ)?Because there are 2ⁿ subsequences and each takes O(n) time to construct.3. Which approach is best?Recursion → best for understandingBit manipulation → best for optimization

GeeksforGeeksRecursionJavaBacktrackingMedium

LeetCode 1665: Minimum Initial Energy to Finish Tasks – Java Greedy Solution Explained

IntroductionLeetCode 1665 – Minimum Initial Energy to Finish Tasks is an important greedy algorithm problem frequently asked in coding interviews.The problem looks difficult initially because tasks can be completed in any order. The real challenge is finding the best order that minimizes the starting energy required.This problem teaches:Greedy strategyCustom sortingOptimization thinkingSimulation techniquesInterview-level problem solvingProblem Link🔗 https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks/Problem StatementYou are given an array:tasks[i] = [actuali, minimumi]Where:actuali = energy spent after completing the taskminimumi = minimum energy required to start the taskYou can complete tasks in any order.Return the minimum initial energy required to finish all tasks.ExampleInput[[1,2],[2,4],[4,8]]Output8Understanding the ProblemSuppose a task is:[4,8]This means:You need at least 8 energy to begin.After completing it, your energy decreases by 4.If your current energy is:10After finishing:10 - 4 = 6Brute Force ApproachIntuitionTry every possible order of tasks and calculate the minimum starting energy needed.Then return the smallest answer.Why Brute Force FailsIf there are N tasks:Total permutations = N!For large constraints up to 10^5, brute force becomes impossible.Brute Force ComplexityTime ComplexityO(N!)Space ComplexityO(N)Greedy IntuitionFor every task:[actual, minimum]The value:minimum - actualrepresents how restrictive the task is.Tasks with larger differences require high starting energy and should be completed earlier.Key Greedy ObservationWe should sort tasks in descending order of:minimum - actualThis minimizes the extra starting energy required later.Why This Greedy WorksSuppose we have:A = [1,10]B = [5,6]Differences:A -> 9B -> 1Task A is more restrictive.If we delay task A, we may lose too much energy before attempting it.So we perform tasks with larger (minimum - actual) first.Optimal Greedy ApproachSteps1. Sort TasksSort tasks by:(minimum - actual) in descending order2. Maintain Current Energycurr = current available energytotal = minimum initial energy required3. Add Energy When NeededIf:minimum > currAdd extra energy.4. Complete the TaskReduce current energy by actual energy spent.Java Greedy Solutionclass Solution { public int minimumEffort(int[][] tasks) { Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]) ); int total = 0; int curr = 0; for (int i = 0; i < tasks.length; i++) { if (tasks[i][1] > curr) { int diff = tasks[i][1] - curr; curr += diff; total += diff; } curr -= tasks[i][0]; } return total; }}Dry RunInput[[1,2],[2,4],[4,8]]Step 1: Sort TasksDifferences:TaskDifference[1,2]1[2,4]2[4,8]4Sorted Order:[[4,8],[2,4],[1,2]]Step 2: Process TasksTask [4,8]Need energy:8Current energy:0Add:8After completion:8 - 4 = 4Task [2,4]Already have enough energy.After completion:4 - 2 = 2Task [1,2]After completion:2 - 1 = 1Final Answer8Time Complexity AnalysisTime ComplexityO(N log N)Sorting dominates the complexity.Space ComplexityO(1)Ignoring sorting space.Interview ExplanationIn interviews, explain:Tasks with larger (minimum - actual) are more restrictive because they require high starting energy. Performing them earlier prevents us from needing larger initial energy later.This demonstrates strong greedy reasoning.Common Mistakes1. Sorting by Minimum OnlyIncorrect because actual energy consumption also matters.2. Sorting by Actual OnlyAlso incorrect.The important factor is:minimum - actual3. Forgetting to Increase Current EnergyAlways check:if(tasks[i][1] > curr)before performing the task.FAQsQ1. Why sort by (minimum - actual)?Because it measures how restrictive a task is.Q2. Is this Dynamic Programming?No.This is a Greedy + Sorting problem.Q3. Why is this problem considered hard?The greedy observation is difficult to identify.The implementation itself is straightforward.ConclusionLeetCode 1665 is an excellent greedy problem for mastering:Custom sortingGreedy intuitionTask schedulingOptimization techniquesThe key idea is sorting tasks by:minimum - actualin descending order.Once this intuition clicks, many advanced greedy interview problems become easier to solve.

LeetCodeGreedy AlgorithmJavaSortingHardArray

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

🔗 Problem LinkLeetCode 242 – Valid Anagram 👉 https://leetcode.com/problems/valid-anagram/IntroductionThis is one of the most important string frequency problems in coding interviews.The idea of checking whether two strings are anagrams appears in many variations:Group AnagramsRansom NoteFind the DifferencePermutation in StringIf you master this pattern, you unlock a whole category of problems.Let’s break it down step by step.📌 Problem UnderstandingTwo strings are anagrams if:They contain the same charactersWith the same frequenciesOrder does not matterExample 1Input: s = "anagram" t = "nagaram"Output: trueBoth contain:a → 3n → 1g → 1r → 1m → 1Example 2Input: s = "rat" t = "car"Output: falseDifferent character frequencies.🧠 IntuitionThe core idea:If two strings are anagrams, their character frequencies must match exactly.So we:Check if lengths are equal.Count frequency of characters in first string.Subtract frequencies using second string.If at any point frequency becomes negative → not anagram.💻 Your Codeclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } for(int i =0; i < t.length();i++){ if(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0){ mp.put(t.charAt(i),mp.get(t.charAt(i))-1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Length Checkif(s.length() != t.length()) return false;If lengths differ → cannot be anagrams.2️⃣ Build Frequency Mapmp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);Count occurrences of each character in s.3️⃣ Subtract Using Second Stringif(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0)If character exists and frequency is available → reduce it.Otherwise → return false immediately.🎯 Why This WorksWe treat:First string as frequency builderSecond string as frequency consumerIf all frequencies match perfectly, we return true.⏱ Complexity AnalysisTime Complexity: O(n)One pass to build mapOne pass to compareSpace Complexity: O(26) ≈ O(1)Only lowercase English letters allowed.🔥 Optimized Approach – Using Array Instead of HashMapSince the problem guarantees:s and t consist of lowercase English lettersWe can replace HashMap with an integer array of size 26.This is faster and cleaner.Optimized Versionclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; int[] freq = new int[26]; for(char c : s.toCharArray()){ freq[c - 'a']++; } for(char c : t.toCharArray()){ freq[c - 'a']--; if(freq[c - 'a'] < 0){ return false; } } return true; }}🚀 Why This Is BetterNo HashMap overheadDirect index accessCleaner codeFaster in interviews🏁 Final ThoughtsThis problem teaches:Frequency counting patternEarly exit optimizationUsing arrays instead of HashMap when character set is limitedThinking in terms of resource balanceValid Anagram is a foundation problem.Once you master it, you can easily solve:Ransom NoteFind the DifferenceGroup AnagramsCheck Equal Character Occurrences

HashMapStringFrequency CountArraysLeetCodeEasy

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

🔗 Problem LinkLeetCode 383 – Ransom Note 👉 https://leetcode.com/problems/ransom-note/IntroductionThis is a classic frequency-count problem that tests your understanding of:Character countingHashMap usageGreedy validation logicAt first glance, the problem looks very simple — but it’s a very common interview question because it checks whether you can think in terms of resource usage.Here:magazine → available resourcesransomNote → required resourcesWe must check if the available letters are sufficient to construct the ransom note.📌 Problem UnderstandingYou are given:ransomNotemagazineRules:Each letter in magazine can be used only once.Return true if ransomNote can be formed.Otherwise return false.Example 1Input: ransomNote = "a", magazine = "b"Output: falseExample 2Input: ransomNote = "aa", magazine = "ab"Output: falseExample 3Input: ransomNote = "aa", magazine = "aab"Output: true🧠 IntuitionThe logic is straightforward:Count frequency of each character in magazine.For each character in ransomNote:Check if it exists in the map.Check if its frequency is greater than 0.Reduce frequency after using it.If at any point we cannot use a character → return false.This is a greedy approach.💻 Your Codeclass Solution { public boolean canConstruct(String r, String m) { HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0 ; i < m.length();i++){ mp.put(m.charAt(i),mp.getOrDefault(m.charAt(i),0)+1); } for(int i = 0 ; i <r.length();i++){ if(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0){ mp.put(r.charAt(i),mp.get(r.charAt(i)) -1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Build Frequency Map from MagazineHashMap<Character,Integer> mp = new HashMap<>();for(int i =0 ; i < m.length();i++){ mp.put(m.charAt(i), mp.getOrDefault(m.charAt(i),0) + 1);}We count how many times each character appears in the magazine.2️⃣ Check Each Character in Ransom Notefor(int i = 0 ; i < r.length();i++){For every character in ransomNote:3️⃣ Validate Availabilityif(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0)If:Character exists in mapFrequency is still availableThen reduce its count:mp.put(r.charAt(i), mp.get(r.charAt(i)) - 1);Otherwise:return false;Immediately stop if we cannot construct.🎯 Why This WorksWe treat:magazine as supplyransomNote as demandWe reduce supply every time we use a character.If supply runs out → construction fails.⏱ Complexity AnalysisTime Complexity: O(n + m)One pass to build map from magazineOne pass to check ransomNoteSpace Complexity: O(26) ≈ O(1)Only lowercase English letters.🔥 Even Better Optimization – Using Array Instead of HashMapSince we know:Only lowercase letters are allowedWe can use an integer array of size 26.This is faster and more memory-efficient.Optimized Versionclass Solution { public boolean canConstruct(String r, String m) { int[] freq = new int[26]; for(char c : m.toCharArray()){ freq[c - 'a']++; } for(char c : r.toCharArray()){ if(freq[c - 'a'] == 0){ return false; } freq[c - 'a']--; } return true; }}This avoids HashMap overhead.🏁 Final ThoughtsThis problem reinforces:Frequency counting patternGreedy character usageEarly exit for optimizationUsing arrays instead of HashMap when character set is limitedIt’s a foundational problem that appears often in interviews.If you master this pattern, you can easily solve:Valid AnagramFind the DifferenceCheck if All Characters Have Equal OccurrencesPermutation in String

HashMapStringFrequency CountGreedyLeetCodeEasy