Lowest Common Ancestor of a Binary Search Tree in BST

Day 77/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Binary Search Tree to Greater Sum Tree A clean and elegant BST transformation problem. Problem idea: Convert a BST so that each node’s value becomes the sum of all values greater than or equal to it. Key idea: Reverse inorder traversal (Right → Root → Left). Why? • In a BST, inorder gives sorted order • Reverse inorder processes nodes from largest to smallest • Maintain a running sum while traversing How it works: • Start from the rightmost node (largest value) • Keep a cumulative sum variable • Add current node value to sum • Update node value with sum • Move to left subtree Time Complexity: O(n) Space Complexity: O(h) (stack / recursion depth) Big takeaway: Whenever you need greater values accumulation in BST, think of reverse inorder traversal. 🔥 This pattern is very useful in BST transformation problems. Day 77 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #BinarySearchTree #Trees #Recursion #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

Day 71/100 🚀 | #100DaysOfDSA Solved LeetCode 67 – Add Binary today. The problem was to add two binary strings and return their sum as a binary string. Approach: Simulated the manual binary addition process. • Used two pointers starting from the end of both strings • Maintained a carry variable • At each step: Added corresponding bits from both strings and the carry Appended (sum % 2) to the result Updated carry = sum / 2 • Continued until both strings are fully traversed and carry becomes 0 • Reversed the result at the end to get the correct order Time Complexity: O(max(n, m)) Space Complexity: O(max(n, m)) Key takeaway: Whenever dealing with number operations on strings, think in terms of digit-by-digit simulation from right to left, just like manual addition. #100DaysOfDSA #LeetCode #DSA #Java #Strings #Math #ProblemSolving #Consistency

Day 91/100 🚀 | #100DaysOfDSA Solved LeetCode 400 – Nth Digit today. This problem was about finding the n-th digit in the infinite sequence: 1, 2, 3, ..., 10, 11, 12, ... Approach: Used a digit range-based approach instead of generating the sequence. • Numbers are grouped by digit length: 1-digit → 1–9 (9 numbers) 2-digit → 10–99 (90 numbers) 3-digit → 100–999 (900 numbers) • Subtracted counts block by block until reaching the correct range • Identified the exact number using: start + (n-1)/digit • Found the required digit inside that number This avoids brute force and works efficiently even for large n. Time Complexity: O(log n) Space Complexity: O(1) Key takeaway: When dealing with sequences formed by patterns of numbers, think in terms of ranges/groups instead of generating elements one by one. #100DaysOfDSA #LeetCode #DSA #Java #Math #BinarySearch #ProblemSolving #Consistency

Day 65/100 | #100DaysOfDSA 🧩🚀 Today’s problem: N-Queens A classic hard backtracking problem. Problem idea: Place N queens on an N×N chessboard such that no two queens attack each other. Key idea: Use backtracking with efficient conflict checking. Why? • We must explore all valid board configurations • Reject placements that cause conflicts • Continue building only valid states How it works: • Place one queen per row • Track columns, diagonals, anti-diagonals • Use bit masking for faster checks ⚡ • Try placing → recurse → backtrack Optimization: Using bitmasks drastically reduces time compared to naive checking. Time Complexity: Exponential (but optimized with pruning) Space Complexity: O(n) recursion depth Big takeaway: Efficient state tracking (cols + diagonals) turns a brute-force problem into a much faster solution. 🔥 One of the most important backtracking problems to master! Day 65 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #Backtracking #Recursion #BitManipulation #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

🧠 Day 206 — Minimum Distance to Target 🎯📍 Today solved a simple yet important problem and did some revision alongside. 📌 Problem Goal Given an array, a target value, and a starting index: ✔️ Find the minimum distance between the start index and any index where the target exists 🔹 Core Idea Traverse the array and: ✔️ Check if current element matches the target ✔️ Calculate distance from the start index ✔️ Keep updating the minimum distance 🔹 Key Observation ✔️ Only indices with the target matter ✔️ Distance = absolute difference between indices ✔️ Simple linear scan gives optimal solution 🧠 Key Learning ✔️ Even easy problems strengthen fundamentals ✔️ Brute-force with clarity > overthinking ✔️ Absolute difference patterns are very common in arrays 💡 Today’s Realization Not every day needs to be a hard problem. Consistency with simple + revision days builds stronger intuition. 🚀 Momentum Status: Staying consistent and sharpening basics. On to Day 207. #DSA #Arrays #ProblemSolving #LeetCode #Java #CodingJourney #ConsistencyWins

Day 69/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Reverse Nodes in k-Group A challenging linked list problem focused on reversing nodes in fixed-size groups. Problem idea: Reverse nodes of a linked list in groups of size k, while keeping remaining nodes as it is. Key idea: Linked list manipulation + iterative reversal in segments. Why? • We need to reverse nodes in chunks, not the whole list • Careful pointer handling is required • Must preserve connections between groups How it works: • Use a dummy node for easier handling of head • Identify the k-th node from current position • Reverse nodes between current and k-th node • Connect reversed group back to the list • Move to next group and repeat • Stop if remaining nodes are less than k Time Complexity: O(n) Space Complexity: O(1) Big takeaway: Mastering pointer manipulation in linked lists is key to solving advanced problems efficiently. This problem is a great example of combining reversal logic with structural control. 🔥 Day 69 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #LinkedList #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

Day 85/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Populating Next Right Pointers in Each Node A clean pointer-manipulation problem that strengthens tree traversal intuition without extra space. Problem idea: Given a perfect binary tree, connect each node to its next right node using a next pointer. Key idea: Level-by-level traversal using already established next pointers (no queue needed). Why? • The tree is perfect → every level is fully filled • We can use existing next links to move horizontally • This avoids extra space (unlike BFS with a queue) How it works: • Start from the leftmost node of each level • Connect left child → right child • If a next node exists, connect right child → next node’s left child • Move across the level using next pointers • Then go down to the next level Time Complexity: O(n) Space Complexity: O(1) Big takeaway: When a tree is perfect, you can often avoid extra space by cleverly using existing structure (like next pointers). 🔥 This is a powerful pattern for constant-space tree traversal problems. Day 85 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #BinaryTree #Pointers #TreeTraversal #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

Day 76/100 | #100DaysOfDSA 🧩🚀 Today’s problem: Lowest Common Ancestor of a Binary Tree A fundamental tree problem that builds strong recursion intuition. Problem idea: Find the lowest node in the tree that has both given nodes as descendants. Key idea: DFS + recursion (bottom-up approach). Why? • Each subtree can independently tell if it contains p or q • Combine results while backtracking • First node where both sides return non-null → answer How it works: • If current node is null / p / q → return it • Recursively search left and right subtree • If both left & right are non-null → current node is LCA • Else return the non-null side Time Complexity: O(n) Space Complexity: O(h) (recursion stack) Big takeaway: Tree problems often rely on post-order traversal + combining child results. Understanding this pattern unlocks many binary tree problems. 🔥 Day 76 done. 🚀 #100DaysOfCode #LeetCode #DSA #Algorithms #BinaryTree #Recursion #DFS #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

#Day362 of #1001DaysOfCode 📘 LeetCode Daily Challenge Problem: XOR After Queries 💡 Approach: Optimized the brute-force simulation using sqrt decomposition. Large step queries were processed directly Small step queries were grouped and batch-processed efficiently Used modular exponentiation + grouped progression updates to reduce time complexity significantly. ⏱ Optimized Time Complexity: ~O(q√n + n√n log MOD) 🧠 Space Complexity: O(n + q) A great problem for learning advanced optimization techniques 🚀 #DSA #Java #LeetCode #ProblemSolving #Algorithms #Coding

Day 68/100 🚀 | #100DaysOfDSA Solved LeetCode 374 – Guess Number Higher or Lower today. The problem was to find a hidden number between 1 and n using the provided guess() API, which tells whether the guessed number is too high, too low, or correct. Approach: Used Binary Search to efficiently find the target number. • Initialized left = 0 and right = n. • Repeatedly calculated mid = left + (right - left) / 2. • Called the guess(mid) API: If it returns 0, found the number → return mid. If it returns 1, the number is higher → move left = mid + 1. If it returns -1, the number is lower → move right = mid - 1. • Continued until the correct number is found. Time Complexity: O(log n) Space Complexity: O(1) Key takeaway: Whenever the search space is sorted or bounded with a condition, Binary Search is the most optimal approach to reduce time complexity drastically. #100DaysOfDSA #LeetCode #DSA #Java #BinarySearch #ProblemSolving #Consistency