Next Greater Element II in Circular Array

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

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

Most people would return this answer: [2, 2] But the correct answer is: [2] Why? 🚀 Day 64/365 — DSA Challenge Solved: Intersection of Two Arrays The task: Given two arrays, return their intersection. But there are two conditions: • The element must exist in both arrays • The result must contain only unique values Example: nums1 = [1,2,2,1] nums2 = [2,2] Output: [2] Even though 2 appears multiple times, it should appear only once in the result. 💡 My Approach (Simple Logic) Step 1 Loop through every element of nums1. Step 2 Check if that number exists in nums2. Step 3 Before adding it to the result, make sure it hasn't already been added. To keep the code clean, I used three methods: intersection() Main method that loops through nums1 and builds the result. existsInArray(num, arr) Checks if a number exists in another array. existsInArray(num, arr, length) Checks duplicates only inside the filled part of the result array. Example walkthrough: 1 -> not in nums2 -> skip 2 -> exists -> add 2 -> already added -> skip 1 -> skip Final output: [2] ⏱ Time Complexity: O(n × m) 📦 Space Complexity: O(n) Day 64/365 complete. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #LearningInPublic #ProblemSolving #Consistency

𝐃𝐚𝐲 𝟑𝟐 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on efficiently merging two sorted arrays in-place. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Merge Sorted Array 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 • Used three pointers to merge arrays from the end • i → last element of nums1 • j → last element of nums2 • k → last position of merged array Steps: • Compare nums1[i] and nums2[j] • Place the larger value at nums1[k] • Move the corresponding pointer backward • Continue until one array is exhausted • Copy remaining elements if needed This approach avoids sorting and works in-place. 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Working from the end prevents overwriting values • Two-pointer / three-pointer techniques simplify merge problems • Using sorted properties reduces time complexity • In-place operations improve space efficiency 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Time: O(m + n) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Sometimes the best solution is to process elements from the back rather than the front. 32 days consistent 🚀 On to Day 33. #DSA #Arrays #TwoPointers #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

📌 LeetCode Daily Challenge — Day 16 Problem: 1878. Biggest Three Rhombus Sums in a Grid Topic: Array, Matrix, Sorting, Simulation   📌 Quick Problem Sense: You're given an m × n integer grid. A rhombus is a square rotated 45°, you sum only its border cells, not the inside. Find the top 3 distinct rhombus sums across all valid sizes and positions in descending order. A rhombus of size 0 is just a single cell, every cell counts!   🧠 Approach (Simple Thinking): 🔹 Every cell (i, j) can be the center of a rhombus of size r = 0, 1, 2, ... 🔹 Size 0 = just the cell itself, add it directly 🔹 For size r ≥ 1, walk the 4 diagonal sides of the rhombus border 🔹 Start at the top tip (i-r, j) and walk with directions: (+1,+1), (+1,-1), (-1,-1), (-1,+1) 🔹 Each side has exactly r steps, skip the last cell to avoid double counting corners 🔹 Use a TreeSet capped at size 3 to track top 3 distinct sums automatically 🔹 TreeSet handles sorting + deduplication, just poll the top 3 at the end!   ⏱️ Time Complexity: Iterating all centers and sizes → O(m × n × min(m,n)²) Manageable for given constraints!   📦 Space Complexity: TreeSet holds at most 3 values → O(1) No extra matrix or prefix array needed!   I wrote a full breakdown with dry run, real-life analogy, and step-by-step code walkthrough here 👇 https://lnkd.in/ggewfAsx If you solved it using diagonal prefix sums or a different top-K trick, drop it in the comments, always curious to see how others think about it 💬 See you in the next problem 👋 #Java #ProblemSolving #DSA #CodingInterview

🔥 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

🔥 Day 349 – Daily DSA Challenge! 🔥 Problem: 🧱 Pyramid Transition Matrix You are stacking blocks to form a pyramid. Each block is represented by a letter. Given a bottom row and a list of allowed triples "ABC" meaning: A B → C Return true if you can build the pyramid to the top. 💡 Key Insight — Bitmask + DFS Instead of storing allowed transitions as lists, we encode them using bitmasks. For each pair (A, B) we store possible top blocks using a bitmask. Conceptually: Example: ABC ABD mask[A][B] = {C, D} stored as bits. 🧠 Recursive Construction We build the pyramid row by row: 1️⃣ Current row → cur 2️⃣ Generate next row → next 3️⃣ For each adjacent pair (cur[i], cur[i+1]) check all possible blocks above 4️⃣ Recursively continue until: length = 1 → pyramid complete ⚡ Optimization Trick To extract possible blocks from bitmask: bit = m & -m This isolates the lowest set bit, letting us iterate through candidates efficiently. ⚙️ Complexity Let n be bottom length. ✅ Time Complexity: ~ O(7ⁿ) worst-case (pruned heavily) ✅ Space Complexity: O(n) recursion stack But pruning via allowed transitions keeps it practical. 💬 Challenge for you 1️⃣ Why does using bitmasks make transitions faster than lists? 2️⃣ How would you add memoization to avoid recomputing rows? 3️⃣ Can you solve this using DP with states instead of DFS? #DSA #Day349 #LeetCode #DFS #Bitmask #Backtracking #Java #ProblemSolving #KeepCoding

Problem Solved: Product of Array Except Self (O(n) | No Division) Today I tackled a classic interview question where for each index we must return the product of all other elements — without using division and in linear time. 🔍 Key Insight Instead of recomputing products repeatedly: Store prefix product (left side) Multiply with suffix product (right side) So for every index: Product = (elements before it) × (elements after it) ⚙️ Approach 1️⃣ First pass → build prefix products 2️⃣ Second pass → multiply suffix products 3️⃣ Done in O(n) time & O(1) extra space ✨ Best part: Even arrays containing zero automatically work — no special handling required. 📌 Takeaway Many “hard” problems are actually about pre-computing information smartly rather than brute force recalculation. #DSA #Algorithms #CodingInterview #Java #ProblemSolving

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

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