Combination Sum III: Find Combinations of 1-9 Numbers

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 - 91 Same Tree The problem -Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. Brute Force - Perform level-order traversal on both trees, store all node values and structure in separate lists, then compare the lists. This gives O(n) time but requires O(n) extra space for storing traversal results, which is unnecessary. Approach Used - •) If both p == null AND q == null, return true, both trees are empty, hence identical. •) If p == null OR q == null OR p.val != q.val, return false, one tree is empty while other isn’t or node values differ. •) Return isSameTree(p.left, q.left) && isSameTree(p.right, q.right), recursively compare left subtrees and right subtrees, both must be true for trees to be identical. Complexity - Time - O(min(n, m)), where n and m are number of nodes. Space - O(min(h₁, h₂)), where h₁, h₂ are heights of trees. Note - Two trees are identical if and only if their current nodes match AND their left subtrees are identical AND their right subtrees are identical. By recursively checking these three conditions, we efficiently verify tree equality in a single traversal. The base cases handle structural differences (null vs non-null) while the recursive case handles value and subtree comparisons. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Continued with Arrays today and worked on finding the smallest missing positive number. This was easily the most challenging array problem I did today. It looked simple at first, but the logic required careful handling of indices and values. int[] arr = {3, 4, -1, 1}; int n = arr.length; // place each number at its correct index for (int i = 0; i < n; i++) {   while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {     int temp = arr[arr[i] - 1];     arr[arr[i] - 1] = arr[i];     arr[i] = temp;   } } // find the first index where value is incorrect int ans = n + 1; for (int i = 0; i < n; i++) {   if (arr[i] != i + 1) {     ans = i + 1;     break;   } } System.out.println(ans); // Output : 2 What this problem made clear to me: - indices can be used as a way to store information - in-place logic needs very strict conditions - ignoring negative and out-of-range values is necessary - this problem is more about positioning than searching This felt like a good checkpoint for how much array logic I can now handle. Continuing with the remaining Array & ArrayList topics today. #Java #DSA #Arrays #LearningInPublic #ProblemSolving #CodingJourney #Programming #JavaDeveloper #DeveloperJourney

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 - 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 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

I didn't expect a linked list concept in an array problem. But that's exactly what this was. 🚀 Day 59/365 — DSA Challenge Solved: Find the Duplicate Number The problem: Given n + 1 numbers Each number is in range [1, n] There is exactly one duplicate. Find it. Constraint: ❌ Can't modify array ❌ O(1) extra space only At first, this looks like an array problem. But the trick is... 👉 Treat it like a linked list 💡 Key idea: Each value points to an index nums[i] → next index This creates a cycle. And the duplicate number is the entry point of the cycle So I used: 👉 Floyd's Cycle Detection Algorithm (slow & fast pointers) Step 1: Move slow by 1 Move fast by 2 They will meet inside the cycle Step 2: Reset slow to start Move both by 1 Where they meet again = duplicate ⏱ O(n) time 📦 O(1) space This problem taught me: Sometimes the solution is not in the data structure you see... But in how you interpret it. Code 👇 https://lnkd.in/dad5sZfu #DSA #LearningInPublic #Java #LeetCode #ProblemSolving #Consistency

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 - 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 315 – Daily DSA Challenge! 🔥 Problem: 🔗 Insertion Sort List Given the head of a singly linked list, sort the list using the Insertion Sort algorithm and return the sorted list. 💡 Key Insights: 🔹 This is the linked-list version of Insertion Sort. 🔹 Unlike arrays, linked lists allow O(1) insertions once the position is found. 🔹 A dummy node simplifies edge cases (like inserting at the head). 🔹 We iteratively take nodes from the original list and insert them into the correct position in the sorted part. 🔹 At every step, the list starting from dummy remains sorted. ⚡ Optimized Plan: ✅ Create a dummy node to act as the sorted list’s head ✅ Traverse the original list node by node ✅ For each node: Find its correct position in the sorted list Insert it there ✅ Continue until all nodes are processed ✅ Return dummy.next as the sorted head ✅ Time Complexity: O(n²) (worst case, already reverse sorted) ✅ Space Complexity: O(1) (in-place sorting) 💬 Challenge for you: 1️⃣ Why is insertion sort more suitable for linked lists than arrays? 2️⃣ How does the performance change if the list is nearly sorted? 3️⃣ Can you optimize this further by tracking the last sorted node? #DSA #Day315 #LeetCode #LinkedList #Sorting #InsertionSort #Java #ProblemSolving #KeepCoding #100DaysOfCode