Find Minimum in Rotated Sorted Array with Binary Search

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

🔥 Day 552 of #750DaysOfCode 🔥 🔐 LeetCode 2075: Decode the Slanted Ciphertext (Medium) Today’s problem looked tricky at first, but once the pattern clicked, it became super elegant 😄 🧠 Problem Understanding We are given an encoded string that was: Filled diagonally (↘) into a matrix Then read row-wise (→) 👉 Our task is to reverse this process and recover the original text. 💡 Key Insight If encoding is: ➡️ Fill diagonally ➡️ Read row-wise Then decoding is: ➡️ Read diagonally from row-wise string ⚙️ Approach ✅ Step 1: Calculate number of columns cols = encodedText.length() / rows; ✅ Step 2: Traverse diagonals starting from each column for (int startCol = 0; startCol < cols; startCol++) { int row = 0, col = startCol; while (row < rows && col < cols) { result.append(encodedText.charAt(row * cols + col)); row++; col++; } } ✅ Step 3: Remove trailing spaces 🚀 Complexity Time: O(n) Space: O(n) 🧠 What I Learned How to reverse matrix-based encoding patterns Converting 2D traversal → 1D index mapping Importance of pattern recognition in problems 📌 Takeaway Not every problem needs heavy logic. Sometimes, it's just about seeing the pattern correctly 👀 #LeetCode #DSA #Java #CodingJourney #ProblemSolving #Algorithms #SoftwareEngineering #100DaysOfCode #750DaysOfCode

Day 52/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Group Anagrams Classic hashing + string pattern. String properties: • Anagrams contain the same characters • Only the order of characters differs • Need to group similar character patterns together Key idea: Use character frequency as a unique key. Why? • Anagrams will always have identical character counts • This gives a consistent way to group strings • More efficient than sorting every string Approach: • Traverse each string in the array • Count frequency of each character (a–z) • Convert frequency array into a string key • Store strings in a HashMap based on this key • Return all grouped values Time Complexity: O(n * k) Space Complexity: O(n * k) Big takeaway: Hashing + frequency counting can replace sorting for better efficiency. Hashing patterns getting stronger day by day. 🔥 Day 52 done. #100DaysOfCode #LeetCode #DSA #Algorithms #HashMap #Strings #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

𝐃𝐚𝐲 𝟓𝟓 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem extended the previous one by introducing duplicates in a rotated sorted array. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Find Minimum in Rotated Sorted Array II 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Used modified binary search • Compared nums[mid] with nums[right] Logic: • If nums[mid] > nums[right] → minimum is in right half • If nums[mid] < nums[right] → minimum is in left half (including mid) • If equal → cannot decide, so shrink search space (right--) 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Duplicates can break standard binary search logic • When unsure, safely reduce the search space • Edge cases often define the complexity of the problem • Small changes in conditions can affect performance 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Average Time: O(log n) • Worst Case: O(n) (due to duplicates) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 When the data becomes ambiguous, focus on reducing the problem safely instead of forcing a decision. 55 days consistent 🚀 On to Day 56. #DSA #Arrays #BinarySearch #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

Day #8 / 100 – Data Structures & Algorithms Today’s focus was on advanced linked list problems and pointer manipulation. Problems solved: • Flatten a Multilevel Doubly Linked List • Design Browser History • Insertion in Circular Linked List • Swap Kth Nodes from End • Rotate the List • Insert Node in a Doubly Linked List • Delete Node in Doubly Linked List • Copy List with Random Pointer Key takeaway: Linked list problems heavily test pointer management and edge case handling, especially when working with structures like circular lists, multilevel lists, or random pointers. Consistent practice is helping strengthen problem-solving and implementation skills while preparing for backend engineering roles. #100DaysOfCode #DSA #LeetCode #Java #BackendDevelopment #Acciojob

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

𝐃𝐚𝐲 𝟓𝟔 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on finding a peak element using binary search. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Find Peak Element 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Used binary search instead of linear scan • Compared the middle element with its next element Logic: • If nums[mid] > nums[mid + 1] → peak lies on the left side (including mid) • Else → peak lies on the right side • Continued until left == right 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Binary search can be applied on patterns, not just sorted arrays • A peak always exists due to problem constraints • Comparing adjacent elements helps determine direction • Reducing the search space is the key idea 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Time: O(log n) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Binary search is not about sorted arrays — it’s about eliminating half of the search space using logic. 56 days consistent 🚀 On to Day 57. #DSA #Arrays #BinarySearch #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

🚀 Day 45/60 – DSA Challenge Today’s problem was about searching in a Rotated Sorted Array using Binary Search 🔍 🔍 Problem Solved: Given a rotated sorted array, efficiently find the index of a target element. 🧠 Approach I Used: Instead of directly applying binary search, I broke the problem into two steps: 1️⃣ Find the pivot (rotation point) using binary search 2️⃣ Apply binary search on the correct half of the array Left half → sorted from start to pivot-1 Right half → sorted from pivot to end ⚡ Key Insight: By identifying the pivot, the problem becomes two simple binary searches Careful boundary checks (like target >= nums[0]) ensure we search in the correct half Handling edge cases (like pivot at index 0) is crucial for correctness 📈 Complexity: Time: O(log n) Space: O(1) 🎯 What I Learned: Complex problems can often be simplified by breaking them into smaller parts Binary Search is not just about searching—it’s about understanding structure Boundary conditions can make or break your solution Debugging edge cases today made the concept even clearer 💡 #Day45 #DSAChallenge #BinarySearch #Java #ProblemSolving #Consistency

Day 97/100 – LeetCode Challenge ✅ Problem: #105 Construct Binary Tree from Preorder and Inorder Traversal Difficulty: Medium Language: Java Approach: Recursive Construction with HashMap Lookup Time Complexity: O(n) Space Complexity: O(n) for map + recursion stack Key Insight: Preorder: [root, left subtree, right subtree] Inorder: [left subtree, root, right subtree] First element in preorder is always root Root's position in inorder splits left and right subtrees Solution Brief: Built HashMap to map inorder value → index for O(1) lookups. Maintained global index to track current root in preorder. Recursively built tree: Get root value from preorder at current index Find root position in inorder Build left subtree using elements before root Build right subtree using elements after root #LeetCode #Day97 #100DaysOfCode #Tree #BinaryTree #Java #Algorithm #CodingChallenge #ProblemSolving #ConstructBinaryTree #MediumProblem #Recursion #HashMap #DSA

𝐃𝐚𝐲 𝟑𝟔 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on converting a sorted array into a height-balanced Binary Search Tree (BST). 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Convert Sorted Array to Binary Search Tree 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Since the array is sorted, the middle element naturally becomes the root • Elements on the left side form the left subtree • Elements on the right side form the right subtree • Recursively applied the same logic to both halves This ensures the tree remains height-balanced. 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Sorted arrays are perfect for constructing balanced BSTs • Choosing the middle element maintains balance • Divide-and-conquer simplifies tree construction • Recursion helps build hierarchical structures naturally 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Time: O(n) • Space: O(log n) (recursion stack) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Sometimes the structure of the input already hints at the best tree structure. 36 days consistent 🚀 On to Day 37. #DSA #Arrays #BinarySearchTree #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper