Generate Parentheses Combinations with DFS

Day - 65 Letter Combinations of Phone Number The problem - Given string of digits 2-9, return all possible letter combinations that the number could represent (like old phone keypads). Example : digits = "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"] Brute Force - Generate all combinations iteratively using nested loops - works but becomes unwieldy with variable input length. Approach Used - •)Create map, 2→"abc", 3→"def", 4→"ghi", 5→"jkl", 6→"mno", 7→"pqrs", 8→"tuv", 9→"wxyz" •) Handle edge case, if digits is null or empty, return empty list. •) Initialize, call backtrack(digits, 0, new StringBuilder(), res, map). •) Backtrack(digits, idx, comb, res, map), 1 - Base Condition, if idx == digits.length, add comb to res. 2 - Recursive case, get letters for current digit, String letters = map.get(digits.charAt(idx)). 3 - For each letter, append to comb, recurse with idx+1, backtrack(digits, idx + 1, comb, res, map). Remove last character, comb.deleteCharAt(comb.length() - 1). Complexity - Time - O(4^n × n), max 4 letters per digit, n to build each string. Space - O(n), recursion depth. Note - Use map for digit→letters. For each digit, try all its letters, recurse to next digit. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 63 Combination Sum III The problem - Find all combinations of k numbers that sum to n, using only numbers 1-9, each number used at most once. Example : k = 3, n = 7 → [[1,2,4]] Brute Force - Generate all C(9, k) combinations, check each sum, still needs to enumerate all combinations. Approach Used - •) Initialize: Call findCombination(k, 1, n, new ArrayList<>(), ans) (start with number 1). •) findCombination(k, num, target, lst, ans), •) If (target == 0 && k == 0), found valid combination, add new ArrayList(lst) to ans and return. •) Recursive case, for num to 9, 1 - If i > target || k <= 0, break. 2 - Add i to lst. 3 - Recurse with k - 1 (need one less number), i + 1 (next number to try), target - i (remaining sum). 4 - Backtrack: remove i from lst. Complexity - Time - O(C(9, k) × k), C(9,k) combinations, k time to copy each. Space - O(k), recursion depth. Note - Loop from 1-9, add number, recurse with k-1 and target-num. Backtrack when target == 0 && k == 0! #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 90 Binary Tree Maximum Path Sum The problem - Given the root of a binary tree, return the maximum path sum of any non-empty path. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. The path sum is the sum of the node values in the path. Brute Force - For each node, consider all possible paths starting from that node using DFS, calculate their sums, and track the maximum. This gives O(n²) time complexity as we explore multiple paths from each node with redundant calculations. Approach Used - •) Declare res = {root.val}. •) Call helper function: dfs(root , res). •) Return res[0]. Helper Function - dfs( Treenode node , int[] res) •) If node == null, return 0 (no contribution from null node). •) leftSum = Math.max(0, dfs(node.left, res)), taking max with 0 to ignore negative paths. •) rightSum = Math.max(0, dfs(node.right, res)), taking max with 0 to ignore negative paths. •) Update maximum sum, res[0] = Math.max(res[0], leftSum + rightSum + node.val), this considers path through current node connecting both subtrees. •) Return Math.max(leftSum, rightSum) + node.val, parent can use only one branch left or right. Complexity - Time - O(n), where n = number of nodes. Space - O(h), where h = height of tree. Note - At each node, we consider two scenarios: (1) the maximum path passing through this node (connecting both subtrees), which updates the global maximum, and (2) the maximum path extending from this node to its parent (using only one subtree), which is returned. We use Math.max(0, childSum) to ignore negative contributions, as excluding negative paths yields better sums. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 75 Next Greater Element I The problem - Given two arrays nums1 and nums2 where nums1 is a subset of nums2, for each element in nums1, find the next greater element in nums2. The next greater element is the first greater element to the right. If it doesn't exist, return -1. Brute Force - For each element in nums1, find its position in nums2, then scan right to find the first greater element. This gives O(n × m) time complexity where n = length of nums1 and m = length of nums2. Approach Used - •) Create array nextGreater[10001] to store next greater element for each number and a Stack<Integer> for tracking elements. •) Traverse nums2 from right to left (i = length-1 to 0), 1 - While stack is not empty && stack.peek() ≤ nums2[i], pop from stack. 2 - If stack is empty, nextGreater[nums2[i]] = -1, else nextGreater[nums2[i]] = stack.peek(). 3 - Push nums2[i] onto stack. •) For each element in nums1, replace it with nextGreater[nums1[i]], return nums1. Complexity - Time - O(n + m) where n = nums1.length, m = nums2.length. Space - O(m), for stack and nextGreater array. Note - Using a monotonic decreasing stack while traversing right to left allows us to efficiently find the next greater element. Elements smaller than current are popped (they can't be next greater for anyone), and the remaining top element is the answer. The array acts as a lookup table for O(1) retrieval. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day 49 Problem statement: You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13. For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers. The test cases are generated so that the answer fits in a 32-bits integer Example: For the tree [1,0,1,0,1,0,1] Paths formed: 100 → 4 101 → 5 110 → 6 111 → 7 Total = 22 Approach: While traversing the tree using DFS, we build the binary number step by step. At each node: val = 2 * val + root.val Why multiply by 2? Because in binary: Left shift = multiply by 2 Then add current bit This simulates constructing a binary number as we move down the tree. Approach: Use DFS (Preorder traversal) Carry the current binary value When we reach a leaf → return the computed number Sum left and right subtree results Java code class Solution { public int dfs(TreeNode root, int val){ if(root == null) return 0; val = 2 * val + root.val; if(root.left == null && root.right == null){ return val; } return dfs(root.left, val) + dfs(root.right, val); } public int sumRootToLeaf(TreeNode root) { return dfs(root, 0); } } #HappyCoding #DSA #Trees #LeetCode #DSA #BinaryTree #Algorithms #Java #ProblemSolving #CodingJourney #InterviewPreparation #SoftwareEngineering #CareerGrowth

Most backtracking solutions are accidentally quadratic in memory — and nobody talks about it. We obsess over time complexity (O(kⁿ)). But here’s the part experts often overlook: ✨ The real hidden cost of backtracking is state copying. 🔹 If you pass a new ArrayList<>(current) at every recursive step, you’re not just exploring paths — you’re cloning memory repeatedly. 🔹 That means your algorithm is doing: Backtracking cost × Copy cost Which quietly increases runtime far beyond the theoretical branching factor. 🔹 In permutation problems, copying a list of size n at every leaf adds an extra O(n) factor per solution. 🔹 Elite solutions avoid this by: Using a single mutable structure Adding → exploring → removing (true in-place reversal) Only copying when storing the final answer 🔹 In high-performance competitive programming, even copying a boolean[] can be the difference between AC and TLE. 💡 Backtracking isn’t just about pruning search space. It’s about minimizing state mutation overhead. Most slow solutions aren’t slow because of recursion. They’re slow because of careless memory duplication. #Algorithms #Backtracking #Performance #Java #DSA #CodingInterviews #ComputerScience

Day - 78 Next Greater Element II The problem - Given a circular integer array nums (the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number. Brute Force - For each element, traverse the array circularly (wrap around using modulo) to find the first greater element. This gives O(n²) time complexity, as for each element we potentially scan the entire array. Approach Used - •) Initialize, create Stack<Integer> to maintain elements in decreasing order, create ans[] array of size n to store results, set n = nums.length. •) For each index i = 2 × n - 1 down to i = 0, 1 - Get current element: current = nums[i % n]. 2 - While stack is not empty AND st.peek() <= current, pop from stack. 3 - If i < n: ans[i] = st.isEmpty()arr ? -1 : st.peek(). 4 - Push current onto stack. •) Return ans[] array. Complexity - Time - O(n), each element pushed and popped from stack at most once across both passes. Space - O(n), for stack and result array. Note - By traversing the array twice (2n iterations) in reverse order, we simulate the circular nature of the array. The stack maintains elements in decreasing order, and for each element, the top of the stack is the next greater element. The modulo operation i % n handles the circular indexing, and we only store results during the second half of the traversal (when i < n). #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🔥 Day 309 – Daily DSA Challenge! 🔥 Problem: 🔁 Permutations II Given an array nums that may contain duplicate numbers, return all unique permutations in any order. 💡 Key Insights: 🔹 This is a backtracking problem with an extra twist — duplicates. 🔹 Sorting the array upfront is the key to handling duplicates cleanly. 🔹 Use a used[] boolean array to track which elements are already in the current permutation. 🔹 The golden rule to skip duplicates 👇     👉 If the current number is the same as the previous one and the previous one is not used, skip it. 🔹 This ensures we only generate unique permutations. ⚡ Optimized Plan: ✅ Sort the input array ✅ Use backtracking to build permutations ✅ Track used elements with a boolean array ✅ Add permutation to result when its size equals nums.length ✅ Skip duplicates using:     if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; ✅ Backtrack after each recursive call ✅ Time Complexity: O(n! × n) (due to copying permutations) ✅ Space Complexity: O(n) (recursion stack + used array) 💬 Challenge for you: 1️⃣ Why does the condition !used[i - 1] matter for avoiding duplicates? 2️⃣ How would this solution change if all numbers were unique? 3️⃣ Can you generate permutations iteratively instead of using recursion? #DSA #Day309 #LeetCode #Permutations #Backtracking #Recursion #Java #ProblemSolving #KeepCoding #100DaysOfCode

What causes OutOfMemoryError vs StackOverflowError? Here’s the answer: Both are runtime errors, but they happen in different memory regions. OutOfMemoryError (OOME) Occurs when the JVM cannot allocate memory in the Heap. Common Causes: • Creating too many objects • Memory leaks (objects not released) • Very large collections (e.g., huge ArrayList) • Excessive class loading → Metaspace full Eg: List<int[]> list = new ArrayList<>(); while (true) { list.add(new int[1000000]); // keeps filling heap } Eventually, Heap memory is exhausted. StackOverflowError (SOE) Occurs when the Stack memory of a thread is full. Common Causes: • Infinite or deep recursion • Too many nested method calls Eg: void recurse() { recurse(); // no exit condition } Each method call adds a frame to the stack → stack limit exceeded. OutOfMemoryError happens when Heap memory is exhausted, usually due to too many objects or leaks, while StackOverflowError occurs when the thread’s stack memory is full, typically due to deep or infinite recursion. Follow Supriya Singh for more such interesting and helpful posts. #Java #Programming #InterviewPrep #JavaDeveloper

𝐃𝐚𝐲 𝟔 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problems were all about 𝐛𝐢𝐧𝐚𝐫𝐲 𝐬𝐞𝐚𝐫𝐜𝐡 𝐰𝐢𝐭𝐡 𝐜𝐨𝐧𝐝𝐢𝐭𝐢𝐨𝐧𝐬 — not just finding an element, but deciding where to search. ✅ 𝐏𝐫𝐨𝐛𝐥𝐞𝐦𝐬 𝐒𝐨𝐥𝐯𝐞𝐝 📌 Search in Rotated Sorted Array 📌 Find First and Last Position of Element in Sorted Array 🔹 𝐒𝐞𝐚𝐫𝐜𝐡 𝐢𝐧 𝐑𝐨𝐭𝐚𝐭𝐞𝐝 𝐒𝐨𝐫𝐭𝐞𝐝 𝐀𝐫𝐫𝐚𝐲 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: Used 𝐦𝐨𝐝𝐢𝐟𝐢𝐞𝐝 𝐛𝐢𝐧𝐚𝐫𝐲 𝐬𝐞𝐚𝐫𝐜𝐡 At each step, identified which half of the array was sorted Narrowed the search space based on where the target could lie 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠: ✅ Binary search is about decisions, not comparisons ✅ Understanding sorted halves simplifies rotated arrays 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲: ⏱ Time: O(log n) 📦 Space: O(1) 🔹 𝐅𝐢𝐧𝐝 𝐅𝐢𝐫𝐬𝐭 𝐚𝐧𝐝 𝐋𝐚𝐬𝐭 𝐏𝐨𝐬𝐢𝐭𝐢𝐨𝐧 𝐨𝐟 𝐄𝐥𝐞𝐦𝐞𝐧𝐭 𝐢𝐧 𝐒𝐨𝐫𝐭𝐞𝐝 𝐀𝐫𝐫𝐚𝐲 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: Performed 𝐭𝐰𝐨 𝐛𝐢𝐧𝐚𝐫𝐲 𝐬𝐞𝐚𝐫𝐜𝐡𝐞𝐬 One to find the leftmost occurrence One to find the rightmost occurrence Adjusted boundaries after finding the target 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠: ✅ One problem can require multiple binary searches ✅ Direction control helps find boundaries efficiently 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲: ⏱ Time: O(log n) 📦 Space: O(1) 🧠 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Binary search isn’t just a technique — it’s a 𝐰𝐚𝐲 𝐨𝐟 𝐭𝐡𝐢𝐧𝐤𝐢𝐧𝐠. On to 𝐃𝐚𝐲 𝟕 🔁🚀 #DSA #Arrays #BinarySearch #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper