Binary Tree Maximum Path Sum Problem Solution

𝐃𝐚𝐲 𝟐𝟗 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on applying binary search in a rotated sorted array with duplicates. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Search in Rotated Sorted Array II 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Used modified binary search • Calculated mid index in each iteration • Identified which half of the array was sorted • Narrowed the search range accordingly To handle duplicates: • If nums[left] == nums[mid] == nums[right], shrink the search space by moving both pointers. 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Rotated arrays require identifying the sorted half • Duplicate values can hide the sorted structure • Shrinking the search space helps handle ambiguous cases • Binary search logic often needs small adjustments for edge cases 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Average Time: O(log n) • Worst Case Time: O(n) (due to duplicates) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Binary search is not just about dividing the array — it's about understanding the structure of the data. 29 days consistent. On to Day 30 🚀 #DSA #Arrays #BinarySearch #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

Yesterday's problem was about searching in a rotated array. Today's challenge was slightly different: What if we just needed to find the smallest number in that rotated array? 🚀 Day 76/365 — DSA Challenge Solved: Find Minimum in Rotated Sorted Array The Problem You're given a sorted array that has been rotated at some unknown pivot. 💡 My Approach This problem can be solved using Binary Search. Key observation: In a rotated sorted array, the smallest element is where the rotation happened. Steps: 1️⃣ Find the middle element 2️⃣ Compare it with the right element: nums[mid] > nums[right] 3️⃣ If true → the minimum must be in the right half 4️⃣ Otherwise → the minimum is in the left half (including mid) Complexity ⏱ Time: O(log n) 📦 Space: O(1) Day 76/365 complete. 💻 289 days to go. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #BinarySearch #Algorithms #LearningInPublic

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 - 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 26/30 — #30DaysDSAChallenge Today I revisited one of the simplest sorting algorithms: Selection Sort. This is the first intuitive solution that comes to mind when I think of sorting. The idea is simple: 1️⃣ Find the smallest element in the array 2️⃣ Swap it with the first position 3️⃣ Repeat the same process for the remaining elements Example: Input: [64, 25, 12, 22, 11] Step 1 → Find the smallest (11) → swap with first Array becomes: [11, 25, 12, 22, 64] Step 2 → Find the smallest in the remaining array (12) Array becomes: [11, 12, 25, 22, 64] And the process continues until the array is sorted. ⚙️ Complexity ⏱ Time Complexity: O(n²) 💾 Space Complexity: O(1) (in-place sorting) One interesting thing is that Selection Sort always performs the same number of comparisons, regardless of whether the array is already sorted or not. 🧠 What I learned today Even though Selection Sort isn't efficient for large datasets, understanding these basic algorithms builds the foundation for more advanced sorting techniques. Are there any algorithms you revisited recently that made more sense the second time? #DSA #Java #Algorithms #ProblemSolving #Day26 #ConsistencyCurve

🔥 Day 353 – Daily DSA Challenge! 🔥 Problem: 🔍 Single Element in a Sorted Array Given a sorted array where every element appears twice except one, find that single element in O(log n) time. 💡 Key Insight — Binary Search on Pairs In a perfect paired array: Pairs start at even indices Pattern breaks at the single element We use binary search to detect where this pattern breaks. 🧠 Core Observation Before the single element: pairs → (even, odd) After the single element: pairs shift → (odd, even) So we normalize mid: if mid is odd → make it even ⚡ Algorithm Logic ✅ Find mid ✅ Make mid even ✅ Compare: If nums[mid] == nums[mid+1] → move right Else → move left This narrows down to the single element. ⚙️ Complexity ✅ Time Complexity: O(log n) ✅ Space Complexity: O(1) 💬 Challenge for you 1️⃣ Why do we force mid to be even? 2️⃣ How would you solve this using XOR in O(n)? 3️⃣ What if elements appear thrice except one? #DSA #Day353 #LeetCode #BinarySearch #Arrays #Optimization #Java #ProblemSolving #KeepCoding

🔥 Day 96 of #100DaysOfCode Today’s problem: LeetCode – Find Minimum in Rotated Sorted Array 🔄📉 📌 Problem Summary You are given a sorted array that has been rotated at some pivot. Example: Sorted array → [1,2,3,4,5] Rotated → [3,4,5,1,2] Goal 👉 Find the minimum element in the array. Example: Input: [3,4,5,1,2] Output: 1 🧠 Approach: Binary Search Since the array was originally sorted, we can use Binary Search to locate the rotation point. Key observation: If nums[l] < nums[r] → Subarray is already sorted → Minimum is nums[l] Otherwise: Compute middle index Compare with left boundary to decide which half to search ⚙️ Decision Logic 1️⃣ If left part is sorted → Minimum must be in right half 2️⃣ If left part is not sorted → Minimum is in left half 💡 Key Idea We are essentially searching for the rotation pivot, which contains the smallest value. ⏱ Time Complexity: O(log n) 💾 Space Complexity: O(1) 🚀 Performance Runtime: 0 ms Beats 100% submissions 🔥 Memory: 43.8 MB 🧠 Pattern Insight Common Binary Search variants: Search in Rotated Sorted Array Find Minimum in Rotated Array Peak Element Binary Search on Answer Recognizing these patterns makes solving them much faster. Only 4 days left to complete #100DaysOfCode 🚀 Consistency paying off every day. On to Day 97 🔥 #100DaysOfCode #LeetCode #BinarySearch #RotatedArray #Java #DSA #InterviewPrep

Started the Merge Sort section today. Before understanding the full algorithm, the first thing was learning how to merge two already sorted arrays into one sorted array. This small piece of logic is actually the core operation behind Merge Sort. Things that became clear : - using two pointers to traverse both arrays - always placing the smaller element first - continuing until both arrays are fully processed - overall time complexity becomes O(m + n) Main merge logic : static void merge(int[] a, int[] b, int[] c) { int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < a.length) c[k++] = a[i++]; while (j < b.length) c[k++] = b[j++]; } What seemed like a small helper function is actually the heart of Merge Sort, because the entire algorithm depends on merging smaller sorted pieces correctly. Understanding this step made the later recursion part much easier to follow. Continuing deeper into Merge Sort and divide-and-conquer next. #dsa #algorithms #mergesort #sorting #java #learninginpublic

Day 41/75 — Binary Tree Postorder Traversal Today’s problem was about performing postorder traversal of a binary tree. Traversal Order: • Left • Right • Root Approach: • Use recursion • Traverse left subtree • Traverse right subtree • Add current node value Key logic: postorder(root.left); postorder(root.right); res.add(root.val); Time Complexity: O(n) Space Complexity: O(h) (recursion stack, h = height of tree) Key Insight: Tree problems become much simpler when you clearly understand traversal orders. Postorder is especially useful when you need to process children before the parent. 41/75 🚀 #Day41 #DSA #BinaryTree #Recursion #Java #Algorithms #LeetCode

Day 39/75 — Permutations Today’s problem was about generating all possible permutations of a distinct integer array. Approach: • Use backtracking • Maintain a used[] array to track picked elements • Build permutation step by step • Backtrack after exploring each path Key logic: if (used[i]) continue; current.add(nums[i]); used[i] = true; func(nums, ans, current, used); current.remove(current.size() - 1); used[i] = false; Time Complexity: O(n! × n) Space Complexity: O(n) recursion stack Key Insight: Permutation problems follow a clear pattern: 👉 Choose → Explore → Backtrack Understanding this flow makes solving similar problems much easier. 39/75 🚀 #Day39 #DSA #Backtracking #Java #Algorithms #LeetCode