Merge k Sorted Linked Lists into One Sorted List

Day - 93 Binary Tree Right Side View The problem - Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Essentially, return the rightmost node at each level. Brute Force - Perform a complete level-order traversal storing all nodes at each level, then extract only the last node from each level. This gives O(n) time but stores all nodes unnecessarily, wasting O(n) space when we only need one node per level. Approach Used - •) Create result = new ArrayList<>(). •) If root == null, return empty result. •) Create queue = new LinkedList<>(). •) Add root to queue. •) While queue is not empty, 1 - Get current level size, size = queue.size(). 2 - For i = 0 to size - 1, - Poll node from queue, node = que.poll(). - ⁠If i == size - 1, add to result: result.add(current.val), this is the last node at current level. - ⁠If current.left != null, add to queue: queue.offer(current.left). - ⁠If current.right != null, add to queue: queue.offer(current.right). •) Return result. Complexity - Time - O(n), where n is number of nodes. Space - O(w), where w is maximum width of tree. Note - Use level-order BFS to traverse the tree level by level. By tracking the current level size, we can identify the last node processed in each level—this is the rightmost visible node. We only store this last node from each level, efficiently building the right side view in a single traversal. #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 - 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

🧠 Problem: Count Frequency of Each Number in an Array 📌 Given: An integer array: int[] arr = {12,54,8,7,12,32,12,54}; 📌 Task: Count how many times each number appears in the array. 📌 Expected Output: [12=3,54=2,8=1,7=1,32=1] NOTE : WITHOUT HASHMAP public class NumberCount2D { public static void main(String[] args) { int[] arr = {12,54,8,7,12,32,12,54}; // 2D array // Column 0 → number // Column 1 → count int[][] ansArr = new int[arr.length][2]; int size = 0; // tracks how many unique elements we stored // Traverse original array for (int num : arr) { boolean found = false; // Check if number already exists in ansArr for (int i = 0; i < size; i++) { // If number matches existing number if (ansArr[i][0] == num) { ansArr[i][1]++; // increase count found = true; break; // stop checking } } // If number not found, store it with count = 1 if (!found) { ansArr[size][0] = num; // store number ansArr[size][1] = 1; // first occurrence size++; // move to next row } } // Print result for (int i = 0; i < size; i++) { System.out.println(ansArr[i][0] + " = " + ansArr[i][1]); } } } #java #springboot #dsa #leetcode

After exploring path-based recursion, I moved to generating all subsets of a string. This introduced a very clean pattern - For every element, you either include it or exclude it. That’s it. But that “either-or” creates a full decision tree. What became clear here: - Every element creates two branches. - Total subsets = 2ⁿ (tree expansion becomes visible). - Recursion can systematically explore combinations. - The structure is more important than the syntax. Core logic : if (index == str.length()) {   System.out.println(current);   return; } subset(index + 1, current + str.charAt(index)); // include subset(index + 1, current);  // exclude This is where recursion started feeling predictable. Once the pattern is seen, similar problems start looking connected. #recursion #java #dsajourney #backtracking #problemSolving

Day - 103 Construct Binary Search Tree from Preorder Traversal The problem - Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root. It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases. Brute Force - Sort the preorder array to get inorder traversal, then use both preorder and inorder arrays to reconstruct the BST (like standard tree construction). This gives O(n log n) time due to sorting, which is inefficient when BST properties can guide direct construction. Approach Used - •) If preorder.length == 0, return null (empty tree). •) Create root with first element, root = new TreeNode(preorder[0]). •) For i = 1 to preorder.length - 1, insert each element, insert(root, preorder[i]). •) Return root. Helper Function - insert(TreeNode root, int val) •) If val < root.val, insert in left subtree, - If root.left == null, create node, root.left = new TreeNode(val). - Else, recurse left, insert(root.left, val). •) Else (when val > root.val), insert in right subtree, - If root.right == null, create node, root.right = new TreeNode(val) - Else, recurse right, insert(root.right, val). Complexity - Time - O(n x h), where h = height of tree, n is number of nodes. Space - O(h), recursion stack depth. Note - Preorder traversal's first element is always the root. By leveraging BST insertion rules (smaller values go left, larger go right), we can sequentially insert each element from the preorder array. Each insertion automatically finds the correct position, building the BST without needing inorder traversal or sorting. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

LeetCode 83 — Remove Duplicates from Sorted List This problem gives the head of a sorted linked list and asks to remove all duplicate values so that each element appears only once. Since the list is already sorted, duplicate values always appear next to each other. The task is simply to skip repeated nodes while keeping the original order of the list. Example : Input : 1 → 1 → 2 → 3 → 3 Output : 1 → 2 → 3 Approach used — Single Pass Pointer Traversal Because the list is sorted, the solution can be done in one traversal. Two pointers are used during traversal : - One pointer (a) keeps track of the last unique node. - Another pointer (b) scans the list forward. When both nodes have the same value, the duplicate node is skipped. When a new value appears, the unique node is connected to it. At the end, the last node’s next pointer is set to null to ensure the list ends correctly. This approach works in O(n) time and O(1) extra space. #leetcode #datastructures #linkedlist #java #problemSolving

Day - 104 Recover Binary Search Tree The problem - You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant O(1) space solution? Brute Force - Perform inorder traversal to collect all values in an array, identify the two swapped elements, store their positions, traverse the tree again to find and swap them back. This gives O(n) time and O(n) space for storing all node values. Approach Used - •) Declare first (first swapped node), second (second swapped node), prev (previous node in inorder traversal). •) Call helper function, helper(root). •) Swap the values, temp = first.val, first.val = second.val, second.val = temp. Helper Function - helper(TreeNode node) •) If node == null, return. •) Traverse left subtree, helper(node.left). •) If prev != null AND prev.val > node.val, - If first == null, set first = prev. - ⁠Set, second = node. •) Update, prev = node. •) Traverse right subtree, helper(node.right). Complexity - Time - O(n), where n is number of nodes. Space - O(h), recursion stack depth. Note - In a valid BST, inorder traversal produces a sorted sequence. When two nodes are swapped, it creates violations where prev.val > current.val. For adjacent swaps, there's one violation; for non-adjacent swaps, there are two. By tracking the first and second violating nodes during inorder traversal, we identify the swapped pair. The algorithm handles both cases by always updating second and only setting first once. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

LeetCode 1593 – Split a String Into the Max Number of Unique Substrings An ideal problem to understand Backtracking. The task is simple but tricky: Split a string into substrings such that all substrings are unique, and maximize the number of splits. 🚀 Approach (Backtracking) 1. Start from index i and try every possible substring s[i...j]. 2. If the substring is not already used (checked using a HashSet), we: add it to the set recursively explore the remaining string starting from j + 1 3. Each recursive call increases the current split count. 4. When we reach the end of the string (i >= length), we update the maximum number of unique splits. 5. After recursion, we remove the substring from the set (backtrack) so other possibilities can be explored. # Core Backtracking Pattern Choose → Explore → Undo Choose: Add substring to the set Explore: Recurse for the remaining string Undo: Remove substring to try other partitions Backtracking explores all possible partitions, but the HashSet ensures no substring repeats, giving the maximum valid split. Perfect example of how recursion + state tracking can systematically search the solution space. #LeetCode #Backtracking #Java #DSA #CodingInterview #Recursion

Day - 99 Insert into a Binary Search Tree The problem - Given the root node of a binary search tree (BST) and a value to insert into the tree, return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. Brute Force - Perform inorder traversal to collect all values, add the new value, sort the array, then rebuild the BST from the sorted array. This gives O(n log n) time complexity due to sorting and is unnecessarily complex since BST properties allow direct insertion. Approach Used - •) If root == null, return new TreeNode(val), found the insertion position. •) If root.val > val, value is smaller, insert in left subtree, root.left = insertIntoBST(root.left, val). •) Else (when root.val < val), value is larger, insert in right subtree, root.right = insertIntoBST(root.right, val). •) Return root. Complexity - Time - O(h), where h = height of tree. Space - O(h), recursion stack depth. Note - BST insertion leverages the binary search property: compare the value with current node, go left if smaller, right if larger. Recursively traverse until finding an empty position (null), then create and return the new node. The recursion naturally updates parent pointers as it backtracks, maintaining tree structure without explicit parent tracking. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving