Combination Sum II: Unique Combinations with Duplicates

Day - 77 Sum of Subarray Minimums The problem - Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7. Brute Force - Generate all possible subarrays, find the minimum element in each subarray, and sum them up. This gives O(n³) time complexity, O(n²) to generate subarrays and O(n) to find minimum in each. Approach Used - •) Initialize, create Stack<int[]> to store pairs of [value, index], create res[] array to store cumulative contributions at each position. •) For each index i from 0 to arr.length - 1, 1 - While stack is not empty AND stack.peek()[0] >= arr[i], pop from stack. 2 - j = stack.isEmpty() ? -1 : stack.peek()[1]. 3 - If stack is empty: res[i] = arr[i] × (i + 1) (all subarrays from start), else res[i] = res[j] + arr[i] × (i - j) (add new subarrays). 4 - Push [arr[i], i] onto stack. •) Initialize ans = 0 and MOD = 10^9 + 7, sum all values in res[] with modulo operation. •) Return result as integer Complexity - Time - O(n), each element pushed and popped from stack at most once. Space - O(n), for stack and result array. Note - By maintaining a monotonic increasing stack, we efficiently determine for each element how many subarrays it serves as the minimum. The res[] array accumulates contributions dynamically: res[i] = res[j] + arr[i] × (i - j) where j is the index of the previous smaller element. This avoids recalculating minimums for overlapping subarrays. #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 - 87 Binary Tree Level Order Traversal The problem - Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Each level should be represented as a separate list. Brute Force - Use recursive DFS to traverse the tree while tracking depth. Store nodes at each depth level in separate lists. This gives O(n) time but requires complex depth tracking and is less intuitive than an iterative approach. Approach Used - •) Create res = new ArrayList<>(), queue = new ArrayDeque<>(). •) If root == null, return empty res. •) Add root to queue. •) While queue is not empty, 1 - Get current level size: size = queue.size(). 2 - Create list = new ArrayList<>(). 3 - While size > 0, - Poll node from queue, node = queue.poll(). - ⁠If node.left != null, add to queue: queue.add(node.left). - ⁠If node.right != null, add to queue: queue.add(node.right). - ⁠Add node value to current level: list.add(node.val). - ⁠Decrement size—. 4 - Add current level to result, res.add(list). •) Return res. Complexity - Time - O(n), where n = number of nodes. Space - O(w), where w = maximum width of tree. Note - Use BFS with a queue to traverse level by level. By capturing the queue size at the start of each iteration, we know exactly how many nodes belong to the current level. Process all nodes in that level, adding their children to the queue for the next level. This naturally groups nodes by level without needing depth tracking. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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 - 86 Binary Tree Preorder Traversal The problem - Given the root of a binary tree, return the preorder traversal of its nodes' values. In preorder traversal, we visit nodes in the order: Root → Left → Right. Brute Force - Store all nodes in an array using level-order traversal, then manually rearrange them in preorder sequence. This gives O(n²) time complexity due to repeated searching and rearranging, which is highly inefficient. Approach Used - •) Initialize ans = new ArrayList<>(). •) If root == null, return empty ans. •) Call helper function - preorder(root, ans). •) Return ans. Helper Function - •) If root != null, 1 - Add current node value: ans.add(root.val). 2 - Recursively traverse left subtree, preorder(root.left, ans). 3 - Recursively traverse right subtree, preorder(root.right, ans). Complexity - Time - O(n), where n = number of nodes. Space - O(h), where h = height of tree. Note - Preorder traversal naturally follows a recursive pattern: process the current node (Root), then recursively process the left subtree (Left), and finally the right subtree (Right). The recursion stack implicitly handles backtracking, making the implementation clean and straightforward. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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 - 61 Subsets II The problem - Given array that may contain duplicates, return all possible unique subsets. Example : candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6],[1,2,5],[1,7],[2,6]] Brute Force - Generate all combinations iteratively, still exponential, but less elegant than recursion. Approach Used - •) Sort the nums array.nums.lengthcktrack(0, nums, subset, res). •) Base case, if i == nums.length, reached end, add new ArrayList(subset) to res and return. •) Recursive First case, include nums[i], add to subset, recurse with i+1, backtrack (remove). •) Recursive Second case, exclude nums[i], recurse with i+1 (don't add). Complexity - Time - O(2^n), each element include/exclude. Space - O(n), recursion depth. Note - Sort array. After excluding an element, skip all duplicates before next recursion to avoid duplicate subsets. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 73 Valid Parentheses The problem - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: open brackets are closed by the same type of brackets, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket. Brute Force - Repeatedly scan the string and remove valid pairs like "()", "{}", "[]" until no more pairs can be removed. If the string becomes empty, it's valid. This gives O(n²) time complexity due to multiple passes and string manipulation. Approach Used - •) Create a Stack<Character> to track opening brackets •) Create a HashMap<Character, Character> to map closing to opening brackets, ')' → '(' , '}' → '{' and ']' → ‘[‘. •) Process each character, Iterate through each character c in the string, 1 - If c is an opening bracket, push it onto the stack. 2 - If c is a closing bracket, - Check if stack is empty, return false. - ⁠Pop from stack and check if it matches mapping.get(c), if mismatch → return false. •) Final Validation, 1 - After processing all characters, check if stack is empty. 2 - Empty stack means all brackets matched correctly. 3 - Non-empty stack means unmatched opening brackets remain. Complexity - Time - O(n), single pass through the string, each character processed once and stack operations (push/pop) are O(1). Space - O(n), stack can hold up to n/2 opening brackets in worst case. Note - Stack naturally handles nested structures with LIFO (Last-In-First-Out) behavior. Each closing bracket must match the most recent unmatched opening bracket. HashMap enables O(1) lookup for matching pairs, making validation efficient. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🔥 Day 304 – Daily DSA Challenge! 🔥 Problem: 🎯 Combination Sum II Given an array of candidate numbers (with possible duplicates) and a target value, return all unique combinations where the chosen numbers sum to the target. 👉 Each number can be used at most once in a combination. 💡 Key Insights: 🔹 This is a classic backtracking + pruning problem. 🔹 Sorting the array is crucial to handle duplicates efficiently. 🔹 Skip repeated elements at the same recursion level to avoid duplicate combinations. 🔹 Once a number exceeds the remaining target, we can stop early (thanks to sorting). 🔹 Always move to i + 1 since each element can be used only once. ⚡ Optimized Plan: ✅ Sort the candidates array ✅ Use backtracking to explore all valid combinations ✅ Maintain a temporary list (cur) for the current path ✅ Add the path to result when target == 0 ✅ Skip duplicates using if (i > idx && a[i] == a[i - 1]) ✅ Backtrack after each recursive call ✅ Time Complexity: O(2ⁿ) in the worst case ✅ Space Complexity: O(n) (recursion stack + current combination) 💬 Challenge for you: 1️⃣ What happens if we remove sorting — how do duplicates affect the output? 2️⃣ How is this problem different from Combination Sum I? 3️⃣ Can you convert this recursive solution into an iterative one? #DSA #LeetCode #Backtracking #Recursion #ProblemSolving #Java #KeepCoding

Day 20 of DSA Consistency – LeetCode 15 (3Sum) Today I solved the classic 3Sum problem. Problem: Find all unique triplets in an array such that a + b + c = 0. At first glance, brute force looks easy (O(n³)), but that’s useless for interviews. It will timeout. The correct approach is: • Sort the array • Fix one number • Use Two Pointers (2Sum technique) • Skip duplicates carefully This reduces the complexity to O(n²). Key learning: Most “hard” problems are just combinations of simpler patterns. 3Sum = Sorting + Two Pointers + Duplicate handling. Patterns > memorizing solutions. Code (Java): class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < 0) left++; else right--; } } return res; } } Time Complexity: O(n²) Space Complexity: O(1) Consistency matters more than speed. 20 days done. No breaks. #DSA #LeetCode #Java #ProblemSolving #CodingInterview #SoftwareEngineering #100DaysOfCode