Sum of Subarray Minimums Algorithm in O(n) Time Complexity

🔥 Day 85 of #100DaysOfCode Today’s challenge: LeetCode: Sliding Window Maximum 🪟📈 📌 Problem Summary Given an integer array nums and a window size k, return the maximum value in each sliding window of size k. Example: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output → [3,3,5,5,6,7] 🧠 Approach: Monotonic Deque (Optimal Solution) Instead of recalculating the max for every window (which would be slow), we maintain a deque that stores indices in decreasing order of values. ⚙️ Key Steps: Remove elements from the back of deque → if they are smaller than the current element (because they’ll never be maximum again). Add current index to the deque. Remove front index → if it is outside the current window. The front of deque always contains ✅ the maximum element of the window. 🚀 Why This Works The deque always maintains elements in decreasing order, so the largest element is always at the front. ⏱ Time Complexity: O(n) Each element is added and removed at most once. 💾 Space Complexity: O(k) ⚡ Performance Runtime: 30 ms Better than ~70% submissions. 💡 What I Learned When you need max/min in a sliding window → think Monotonic Queue. Removing useless elements early keeps solution efficient. Advanced data structure knowledge gives huge performance gains. Two Pointers → Sliding Window → Monotonic Queue The progression is real. 🔥 On to Day 86 🚀 #100DaysOfCode #LeetCode #SlidingWindow #Deque #Java #DSA #InterviewPrep

𝐋𝐞𝐞𝐭𝐂𝐨𝐝𝐞 𝐃𝐚𝐢𝐥𝐲 𝐂𝐡𝐚𝐥𝐥𝐞𝐧𝐠𝐞: 1784.Check if Binary String Has At Most One Segment of Ones Today’s challenge was a short but insightful problem that demonstrates how recognizing patterns in a binary string can lead to an extremely elegant solution. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐮𝐦𝐦𝐚𝐫𝐲: We are given a binary string s consisting only of '0' and '1'. The task is to determine whether the string contains at most one continuous segment of '1'. In other words, once a '0' appears after a '1', there should not be another '1' later in the string. If there is more than one segment of '1', return false. Otherwise, return true. 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: The key observation is very simple. If a binary string has more than one segment of '1', the pattern "01" must appear somewhere in the string. Why? A valid string with only one segment of ones looks like: 0001111000 But an invalid string with multiple segments would look like: 11100111 Notice the transition "01" which indicates that ones started again after a zero. Therefore, the entire problem reduces to checking whether the substring "01" exists. If "01" is present → there are multiple segments of '1'. If "01" is absent → there is at most one segment. This allows us to solve the problem in a single line using the built-in string function. 𝐂𝐨𝐝𝐞 𝐒𝐧𝐢𝐩𝐩𝐞𝐭 (Java): class Solution { public boolean checkOnesSegment(String s) { return !s.contains("01"); } } 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 𝐀𝐧𝐚𝐥𝐲𝐬𝐢𝐬: Time Complexity: O(n) Space Complexity: O(1) We scan the string once to check if the pattern "01" exists. 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬: Sometimes the best solution is identifying a simple pattern instead of simulating the entire process. Understanding how transitions occur in binary strings can simplify many problems. Leveraging built-in string functions can make solutions both clean and efficient. A great reminder that even small problems can reinforce strong pattern-recognition skills. #LeetCode #DSA #Java #ProblemSolving #Algorithms #BinaryStrings #CodingPractice #Consistency #100DaysOfCode #LearningJourney

Day - 78 Next Greater Element II The problem - Given a circular integer array nums (the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number. Brute Force - For each element, traverse the array circularly (wrap around using modulo) to find the first greater element. This gives O(n²) time complexity, as for each element we potentially scan the entire array. Approach Used - •) Initialize, create Stack<Integer> to maintain elements in decreasing order, create ans[] array of size n to store results, set n = nums.length. •) For each index i = 2 × n - 1 down to i = 0, 1 - Get current element: current = nums[i % n]. 2 - While stack is not empty AND st.peek() <= current, pop from stack. 3 - If i < n: ans[i] = st.isEmpty()arr ? -1 : st.peek(). 4 - Push current onto stack. •) Return ans[] array. Complexity - Time - O(n), each element pushed and popped from stack at most once across both passes. Space - O(n), for stack and result array. Note - By traversing the array twice (2n iterations) in reverse order, we simulate the circular nature of the array. The stack maintains elements in decreasing order, and for each element, the top of the stack is the next greater element. The modulo operation i % n handles the circular indexing, and we only store results during the second half of the traversal (when i < n). #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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 - 103 Construct Binary Search Tree from Preorder Traversal The problem - Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root. It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases. Brute Force - Sort the preorder array to get inorder traversal, then use both preorder and inorder arrays to reconstruct the BST (like standard tree construction). This gives O(n log n) time due to sorting, which is inefficient when BST properties can guide direct construction. Approach Used - •) If preorder.length == 0, return null (empty tree). •) Create root with first element, root = new TreeNode(preorder[0]). •) For i = 1 to preorder.length - 1, insert each element, insert(root, preorder[i]). •) Return root. Helper Function - insert(TreeNode root, int val) •) If val < root.val, insert in left subtree, - If root.left == null, create node, root.left = new TreeNode(val). - Else, recurse left, insert(root.left, val). •) Else (when val > root.val), insert in right subtree, - If root.right == null, create node, root.right = new TreeNode(val) - Else, recurse right, insert(root.right, val). Complexity - Time - O(n x h), where h = height of tree, n is number of nodes. Space - O(h), recursion stack depth. Note - Preorder traversal's first element is always the root. By leveraging BST insertion rules (smaller values go left, larger go right), we can sequentially insert each element from the preorder array. Each insertion automatically finds the correct position, building the BST without needing inorder traversal or sorting. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

After understanding how merging works, the next step was learning the Merge Sort algorithm itself. What looked confusing at first became clearer once the idea of divide and conquer clicked. Instead of sorting the whole array directly, the approach is to keep splitting the array into smaller parts until each part contains only one element, and then merge them back in sorted order. Things that became clear : - the array is recursively divided into two halves - each half is sorted independently - the previously learned merge logic combines them - this leads to a consistent O(n log n) time complexity Main merge sort logic : static void mergesort(int[] arr) { int n = arr.length; if (n == 1) return; int[] a = new int[n / 2]; int[] b = new int[n - n / 2]; for (int i = 0; i < n / 2; i++) a[i] = arr[i]; for (int i = 0; i < n - n / 2; i++) b[i] = arr[i + n / 2]; mergesort(a); mergesort(b); merge(a, b, arr); } The biggest realization here was that sorting becomes much easier when the problem is repeatedly broken into smaller pieces, and then rebuilt using the merge step. This was the point where the whole merge process from the previous exercise finally made complete sense. #dsa #algorithms #mergesort #divideandconquer #java #learninginpublic

After working through merge-based problems, I spent some time understanding Quick Sort. Unlike Merge Sort, which splits first and merges later, Quick Sort works by placing one element (pivot) in its correct position first, and then recursively sorting the parts around it. The key part of the algorithm is the partition step, where the pivot element is moved to the position where it would appear in the final sorted array. Approach used : - choose a pivot element - count how many elements are smaller than the pivot - place the pivot at its correct index - rearrange elements so that - left side contains values ≤ pivot - right side contains values > pivot - recursively apply the same process to both sides 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 partition step controls the entire algorithm - on average Quick Sort runs in O(n log n) - the worst case can reach O(n²) when the pivot selection is poor - the recursion depth depends on how balanced the partitions are Understanding how the pivot finds its correct position made the whole algorithm much easier to follow. #dsa #algorithms #quicksort #sorting #java #learninginpublic

🔥 Day 92 of #100DaysOfCode Today’s challenge: LeetCode – Search a 2D Matrix 🧩📊 📌 Problem Summary You are given a matrix where: Each row is sorted in ascending order The first element of each row is greater than the last element of the previous row 👉 This means the entire matrix behaves like a sorted 1D array. Goal: Return true if target exists, otherwise false. 🧠 Approach: Double Binary Search Instead of scanning row by row, we use Binary Search twice. Step 1️⃣: Find the Correct Row Binary search on rows: If target > last element of row → move down If target < first element of row → move up Otherwise → target must be inside this row Step 2️⃣: Binary Search Inside That Row 💡 Why This Works? Because: Rows are sorted Row ranges don’t overlap It behaves like a flattened sorted array. ⏱ Time Complexity: O(log m + log n) 💾 Space Complexity: O(1) 🚀 Performance Runtime: 0 ms Beats 100% submissions Memory: Very efficient 🔥 🧠 Key Learning Whenever: Data looks 2D But ordering behaves like 1D 👉 Think Binary Search Optimization Stack → Sliding Window → Queue → Binary Search → Matrix Search Patterns are connecting now 💪 On to Day 93 🚀 #100DaysOfCode #LeetCode #BinarySearch #Matrix #Java #DSA #InterviewPrep

Pass by Value — But Why Does My Array Change? 🤔 While implementing in-place matrix rotation (Leetcode 48: Rotate Image), I revisited a fundamental concept that often causes confusion: How does modifying an array inside a method change the original array without returning it? The answer lies in parameter passing. "Java is strictly pass by value" However, for objects (including arrays), the value being passed is a copy of the reference. That phrase — “copy of the reference” — is the key. -> What This Actually Means - When we pass an array to a method: - The array itself lives in the heap. - The variable (reference) lives in the stack. - The method receives a copy of that reference value. - Both references now point to the same heap object. --> Case 1: Modifying the Object arr[0] = 100; - Both variables point to the same heap memory. - The object is modified. - So the original array changes. - Modifying the object affects the original. --> Case 2: Reassigning the Reference arr = new int[]{...}; - A new array is created in the heap. - The local reference now points to this new memory. - The original reference outside the method remains unchanged. - Reassigning the parameter does NOT affect the caller. Understanding this removes a lot of hidden confusion around debugging and memory behavior. Sometimes, while solving DSA problems, you end up strengthening language fundamentals as well. That’s the real benefit of consistent practice. Let me know in the comments section about more such interesting topics . #LearnInPublic #Java #MemoryModel #StackAndHeap #OOP #JavaConcepts

Day - 87 Binary Tree Level Order Traversal The problem - Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Each level should be represented as a separate list. Brute Force - Use recursive DFS to traverse the tree while tracking depth. Store nodes at each depth level in separate lists. This gives O(n) time but requires complex depth tracking and is less intuitive than an iterative approach. Approach Used - •) Create res = new ArrayList<>(), queue = new ArrayDeque<>(). •) If root == null, return empty res. •) Add root to queue. •) While queue is not empty, 1 - Get current level size: size = queue.size(). 2 - Create list = new ArrayList<>(). 3 - While size > 0, - Poll node from queue, node = queue.poll(). - ⁠If node.left != null, add to queue: queue.add(node.left). - ⁠If node.right != null, add to queue: queue.add(node.right). - ⁠Add node value to current level: list.add(node.val). - ⁠Decrement size—. 4 - Add current level to result, res.add(list). •) Return res. Complexity - Time - O(n), where n = number of nodes. Space - O(w), where w = maximum width of tree. Note - Use BFS with a queue to traverse level by level. By capturing the queue size at the start of each iteration, we know exactly how many nodes belong to the current level. Process all nodes in that level, adding their children to the queue for the next level. This naturally groups nodes by level without needing depth tracking. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving