Binary Tree Maximum Depth Problem Solution

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

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

𝐃𝐚𝐲 𝟐𝟗 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 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

🔥 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

While practicing Quick Sort further, I looked into the issue of pivot selection. In the basic implementation, choosing a fixed pivot (like the first element) can sometimes lead to very unbalanced partitions, especially if the array is already sorted or nearly sorted. In such cases, the time complexity can degrade to O(n²). Approach used : Instead of always choosing the same pivot position, the pivot can be selected from a different position (like the middle element or a random index) before performing the partition. The rest of the algorithm remains the same : - choose a pivot - move it to its correct position using partition logic - recursively sort the left and right parts Core Quick Sort logic : static void quickSort(int[] arr, int lo, int hi) { if (lo >= hi) return; int idx = partition(arr, lo, hi); quickSort(arr, lo, idx - 1); quickSort(arr, idx + 1, hi); } Things that became clear : - the pivot choice strongly affects performance - randomized or varied pivot selection helps avoid worst-case patterns - average time complexity remains O(n log n) - recursion stack space is typically O(log n) This made it clear that Quick Sort’s efficiency depends not only on the algorithm itself but also on how intelligently the pivot is chosen. #dsa #algorithms #quicksort #sorting #java #learninginpublic

Day 72/100 – LeetCode Challenge ✅ Problem: #7 Reverse Integer Difficulty: Medium Language: Java Approach: Digit Extraction with Overflow Check Time Complexity: O(log₁₀ x) Space Complexity: O(1) Key Insight: Reverse integer by repeatedly extracting last digit and building result. Critical: Check overflow before final cast using long to detect > Integer.MAX_VALUE or < Integer.MIN_VALUE. Solution Brief: Extracted digits using modulo 10. Built reversed number step by step in long to detect overflow. After loop, divided by 10 to remove extra multiplication. Checked if result fits in 32-bit integer range. Handled sign separately at the end. #LeetCode #Day72 #100DaysOfCode #Math #Java #Algorithm #CodingChallenge #ProblemSolving #ReverseInteger #MediumProblem #Overflow #DigitManipulation #DSA

🚀 Day 32 / 90 — DSA Challenge Today’s problem was a very interesting one: Split Array Largest Sum. At first glance, it looks like a typical array partitioning problem, but the real insight is recognizing that this problem can be solved efficiently using Binary Search on the Answer. 🔹 Problem Idea Given an array of integers and a value "k", the goal is to split the array into "k" subarrays such that the largest sum among those subarrays is minimized. Example: nums = [1,2,3,4,5], k = 2 Optimal split → "[1,2,3]" and "[4,5]" Largest sum = 9 🔹 Key Insight Instead of trying every possible split, we: 1️⃣ Use Binary Search on the possible maximum subarray sum 2️⃣ Check if we can split the array into "k" parts with that limit 3️⃣ Adjust the search range accordingly This reduces the complexity from an exponential brute force approach to an efficient O(n log(sum)) solution. 🔹 Concepts Practiced Today ✔ Binary Search on Answer ✔ Greedy partition checking ✔ Optimization problems with arrays ✔ Writing clean feasibility functions ("isPossible") 🔹 Takeaway Many array problems that ask to minimize the maximum value can often be solved using Binary Search on the Answer combined with a greedy validation function. Consistency is the real algorithm here. 32 days down, 58 more to go. #Day32 #90DaysOfDSA #DSAChallenge #LeetCode #BinarySearch #Java #ProblemSolving #SoftwareEngineering #CodingJourney Vignesh Reddy Julakanti

🚀 Day 42 of #100DaysOfCode Solved 1508. Range Sum of Sorted Subarray Sums on LeetCode 📊 🧠 Problem Insight: Given an array, we must compute the sum of all subarray sums, sort them, and return the sum of elements between indices left and right. ⚙️ Approach Used: 1️⃣ Generate all possible subarray sums using nested loops 2️⃣ Store them in an array of size n*(n+1)/2 3️⃣ Sort the subarray sums 4️⃣ Compute the sum of elements from index left-1 to right-1 5️⃣ Apply mod = 1e9 + 7 to avoid overflow This approach works well because the total number of subarrays is manageable for the given constraints. ⏱️ Time Complexity: O(n² log n) O(n²) to generate subarray sums O(n² log n) to sort them 📦 Space Complexity: O(n²) #100DaysOfCode #LeetCode #DSA #Arrays #Algorithms #Java #CodingPractice #InterviewPrep