Optimizing 2D Prefix Sum for Range Queries

#PostLog135 ✅Range Sum Query 2D – Immutable (LeetCode 304) I worked on a problem where we need to find the sum of numbers inside a rectangle in a 2D matrix — and we need to answer many such queries efficiently. If we calculate the sum every time by looping through the rectangle, it will be slow. So instead, Use a smart technique called 2D Prefix Sum. 💡 What to do: 1.First, precompute a prefix sum matrix. 2.This stores cumulative sums so we don’t need to recalculate again and again. 3.After preprocessing, each query can be answered in O(1) time. ⏱ Time Complexity: Preprocessing: O(n × m) Each query: O(1) 🚀 What I Learned: How to extend 1D prefix sum to 2D. How preprocessing can make repeated queries extremely fast. Importance of avoiding double counting in matrix problems. Small optimizations like this make a huge difference in performance. Slowly getting better at identifying patterns in DSA problems 💪 #LeetCode #DSA #Java #ProblemSolving #CodingJourney

🔥 Day 83 of #100DaysOfCode Today’s problem: LeetCode: Minimum Size Subarray Sum 🎯 📌 Problem Summary Given: An integer target An array nums Return the minimum length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists → return 0. Example: target = 7 nums = [2,3,1,2,4,3] Output → 2 (because [4,3] = 7) 🧠 Approach: Sliding Window (Two Pointers) This is a classic variable-size sliding window problem. ⚙️ Strategy: Use two pointers: l (left) and r (right) Expand window by moving r Keep adding to total When total >= target: Update result Shrink window from left Subtract from total 🔁 Core Logic: for each r: total += nums[r] while total >= target: update min length total -= nums[l] l++ ⏱ Time Complexity: O(n) 💾 Space Complexity: O(1) 💡 What I Learned Sliding window is extremely powerful for subarray problems. The key is knowing when to expand and when to shrink. Many medium/hard problems are just variations of this pattern. Today’s runtime: ⚡ 1ms (99% faster) Consistency builds mastery. On to Day 84 🚀 #100DaysOfCode #LeetCode #SlidingWindow #Java #DSA #InterviewPrep #CodingJourney

Day 33 / #100DaysOfCode LeetCode 3013 — Divide an Array Into Subarrays With Minimum Cost II (Hard) Problem (short): Given an array nums, divide it into k subarrays such that: - The first subarray must start at index 0 - The distance between the start of the 2nd and kth subarray is at most dist - The total cost (sum of starting elements of all subarrays) is minimized This is the Hard follow-up of Part I, and the constraints make brute force impossible. Key Challenge: Once k becomes variable, we are no longer choosing just 2 elements. We must dynamically maintain the minimum sum of (k-2) valid starting elements inside a moving window. This is where simple sorting or greedy breaks. Core Idea / Observation: - nums[0] is always included - For each possible ending index, we need: • the smallest (k-2) elements from a sliding window • fast insertion and deletion • fast access to the smallest elements This naturally leads to a two-multiset (two TreeMap) strategy. Approach: 1. Fix nums[0] as the first subarray 2. Use two TreeMaps: • st1: stores the smallest (k-2) elements (contributes to sum) • st2: stores the remaining elements 3. Maintain balance using: • automatic shifting between maps • invariant: st1 always contains exactly (k-2) smallest elements 4. Slide the window while respecting the dist constraint 5. At each step: • compute current cost = nums[0] + sum(st1) + current element • update minimum I did take help from the editorial here — to understand how to maintain the invariant correctly. This problem is more about data-structure discipline than raw logic. Complexity: - Time: O(n log n) - Space: O(k) (due to TreeMaps) #Leetcode #DSA #Java

Day 2 – DSA Journey | Arrays 🚀 Continuing my daily DSA practice with two problems that focus on pointer movement and string comparison logic. ✅ Problems Solved 📌 Container With Most Water 📌 Longest Common Prefix 🔹 Container With Most Water Approach: Used the Two Pointer technique by starting from both ends of the array. At every step: Calculate the area using the shorter height Move the pointer pointing to the smaller height inward This works because moving the taller line cannot increase the area when the width decreases. What I Learned: ✅ Two pointers can replace nested loops ✅ Greedy pointer movement improves efficiency Complexity: ⏱ Time: O(n) 📦 Space: O(1) 🔹 Longest Common Prefix Approach: Started with the first string as the initial prefix and gradually reduced it. For each string: Compare the current prefix with the substring Shrink the prefix until it matches If the prefix becomes empty, return immediately. What I Learned: ✅ String problems need careful boundary handling ✅ Early exits help avoid unnecessary work Complexity: ⏱ Time: O(n × m) (n = number of strings, m = prefix length) 📦 Space: O(1) 🧠 Takeaway Efficiency often comes from smart pointer movement and early stopping, not complex code. On to Day 3 — staying consistent 🔁🚀 #DSA #Arrays #Strings #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

📅 Day 107 of #160DaysOfDSA 🔐 Decode the String ✅ Today’s problem helped me understand how stacks simplify decoding nested string patterns in an clean and structured way. 🧠 Problem in Short Given an encoded string of the form: k[encoded_string] ▪️ The substring inside [] must be repeated k times ▪️ Nested encodings are allowed 🔹 Example: Input: 3[b2[ca]] Output: bcacabcacabcaca 🚀 Core Idea We decode the string by traversing it character by character and using two stacks: 🔸 Count Stack → stores repetition numbers 🔸 String Stack → stores previous partial strings 🔁 Execution Flow ✔️ If digit → build the number ✔️ If [ → save current state (number + string) ✔️ If ] →     • repeat current string     • attach it to the previous string ✔️ If alphabet → append to the current string ⏱️ Complexity Time: O(n × k) Space: O(n) #DSA #Stack #DecodeString #GeeksForGeeks #ProblemSolving #Java #CodingJourney  #GFG #Day107 #StringBuilder

LeetCode POTD #3013 - Divide an Array Into Subarrays With Minimum Cost II (02 February 2026) This one looks messy at first glance, but the trick is how you frame it. The first subarray is forced to start at index 0. So the real decision is where the last subarray starts. Fix the starting index of the last subarray at i. Now the constraint i(k-1) - i1 <= dist forces the remaining k-2 subarrays to start inside the window: [i - dist, i - 1] At that point, the problem becomes clean: From a sliding window of length dist, continuously maintain the smallest k-2 values. To do this efficiently: -> Use two ordered sets -> One keeps the k-2 smallest elements -> The other holds the rest -> Maintain the sum while the window slides Total cost for each i: nums[0] + nums[i] + sum_of_k-2_smallest Minimum across all valid i is the answer. Key takeaway: Hard problems usually aren’t about complex code -> they’re about choosing the right perspective. Time Complexity -> O(n log n) Space Complexity -> O(n) #LeetCode #POTD #HardProblems #DataStructures #SlidingWindow #Java #ProblemSolving

Day 51/100 – LeetCode Challenge ✅ Problem: #3634 Minimum Removals to Balance Array Difficulty: Medium Language: Java Approach: Sorting + Sliding Window Time Complexity: O(n log n) Space Complexity: O(1) Key Insight: After sorting, valid subarray must satisfy nums[j] ≤ nums[i] × k for all elements. Find longest valid subarray using sliding window, then minimum removals = n - maxLen. Solution Brief: Sorted array to bring comparable values together. Used two pointers: expand j, shrink i when condition fails. Tracked maximum window length where nums[j] ≤ nums[i] × k. Result = total elements - longest valid subarray length. #LeetCode #Day51 #100DaysOfCode #SlidingWindow #Sorting #Java #Algorithm #CodingChallenge #ProblemSolving #MinimumRemovals #MediumProblem #Array #TwoPointers #DSA

🔥 Day 309 – Daily DSA Challenge! 🔥 Problem: 🔁 Permutations II Given an array nums that may contain duplicate numbers, return all unique permutations in any order. 💡 Key Insights: 🔹 This is a backtracking problem with an extra twist — duplicates. 🔹 Sorting the array upfront is the key to handling duplicates cleanly. 🔹 Use a used[] boolean array to track which elements are already in the current permutation. 🔹 The golden rule to skip duplicates 👇     👉 If the current number is the same as the previous one and the previous one is not used, skip it. 🔹 This ensures we only generate unique permutations. ⚡ Optimized Plan: ✅ Sort the input array ✅ Use backtracking to build permutations ✅ Track used elements with a boolean array ✅ Add permutation to result when its size equals nums.length ✅ Skip duplicates using:     if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; ✅ Backtrack after each recursive call ✅ Time Complexity: O(n! × n) (due to copying permutations) ✅ Space Complexity: O(n) (recursion stack + used array) 💬 Challenge for you: 1️⃣ Why does the condition !used[i - 1] matter for avoiding duplicates? 2️⃣ How would this solution change if all numbers were unique? 3️⃣ Can you generate permutations iteratively instead of using recursion? #DSA #Day309 #LeetCode #Permutations #Backtracking #Recursion #Java #ProblemSolving #KeepCoding #100DaysOfCode

𝗗𝗮𝘆 𝟯𝟲/𝟭𝟬𝟬 | 𝗠𝗲𝗿𝗴𝗲 𝗧𝘄𝗼 𝗦𝗼𝗿𝘁𝗲𝗱 𝗟𝗶𝘀𝘁𝘀 Day 36 ✅ — Recursion over iteration. 𝗧𝗼𝗱𝗮𝘆'𝘀 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: ✅ 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 #𝟮𝟭: Merge Two Sorted Lists (Easy) 𝗪𝗵𝗮𝘁 𝗖𝗹𝗶𝗰𝗸𝗲𝗱: Merge two sorted linked lists. Instead of the iterative dummy node approach, I used 𝗿𝗲𝗰𝘂𝗿𝘀𝗶𝗼𝗻. Compare the heads. Attach the smaller one, then recursively merge the rest. Base case: if one list is empty, return the other. Elegant. Three lines of logic. 𝗠𝘆 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵: 👉 Base cases: if l1 is null, return l2 (and vice versa) 👉 Compare l1.val and l2.val 👉 Attach smaller node and recurse with remaining lists Time: O(n + m), Space: O(n + m) for recursion stack 𝗠𝘆 𝗥𝗲𝗮𝗹𝗶𝘇𝗮𝘁𝗶𝗼𝗻: Seven linked list problems, and recursion just made this one cleaner than iteration. Sometimes the simplest code is the most powerful. 𝗖𝗼𝗱𝗲:🔗 https://lnkd.in/g4f4_B69 𝗗𝗮𝘆 𝟯𝟲/𝟭𝟬𝟬 ✅ | 𝟲𝟰 𝗺𝗼𝗿𝗲 𝘁𝗼 𝗴𝗼! #100DaysOfCode #LeetCode #LinkedList #Recursion #DataStructures #CodingInterview #SoftwareEngineer #Java #Algorithms #Programming

Day 38: Efficiency through String Balancing! ⚖️ Problem 1653: Minimum Deletions to Make String Balanced Today’s challenge was to find the minimum deletions needed to ensure no 'b' comes before an 'a' in a string. It’s a classic problem that tests your ability to think about state transitions across a sequence. I implemented a prefix/suffix counting strategy. Instead of brute-forcing every deletion possibility, I pre-calculated the total count of 'a's and then iterated through the string while keeping a running count of 'b's. At each position, the sum of 'b's seen so far (to be deleted if they stay) and 'a's remaining (to be deleted if they appear later) gave me the cost to balance at that specific "split point." By tracking the minimum sum across all possible split points, I achieved a clean O(n) solution with just two passes. It’s a great reminder that sometimes "balancing" a problem is just about counting what’s on either side of the fence! #LeetCode #Java #StringAlgorithms #Optimization #CodingChallenge #ProblemSolving #Algorithms