2D Prefix Sum Mastery: LeetCode Challenge

🚀 Day 535 of #750DaysOfCode 🚀 ✅ Solved: Count Submatrices with Top-Left Element and Sum ≤ k (LeetCode 3070) Today’s problem was a great example of using 2D Prefix Sum to optimize matrix queries. Instead of checking every possible submatrix, we can observe that the question only allows submatrices that include the top-left element (0,0). This means every valid submatrix is just a prefix rectangle, so we can compute the sum efficiently using prefix sums. 💡 Key Learning: Used 2D Prefix Sum technique Reduced brute force complexity to O(m × n) Learned how to handle matrix range sum problems efficiently 📌 Approach: Build prefix sum for each cell Check if sum from (0,0) to (i,j) ≤ k Count valid submatrices This problem improved my understanding of: ✔️ Prefix Sum ✔️ Matrix DP patterns ✔️ Optimization from brute force to efficient solution Consistency continues 🔥 On to Day 536 tomorrow. #leetcode #java #datastructures #algorithms #codingchallenge #prefixsum #matrix #programming #softwareengineering #750daysofcode

Day 82: Navigating Negative Products 📉 Problem 1594: Maximum Non-Negative Product in a Matrix Today’s challenge was a classic Dynamic Programming problem with a twist: negative numbers. In multiplication, two negatives make a positive, which means the "worst" path could suddenly become the "best" one. The Strategy: • Dual DP Tables: Maintained both a max and a min DP table. Why? Because a very small negative number multiplied by another negative can result in a massive positive. • Path Dependency: For every cell, I tracked four potential products (from the top and from the left, using both previous max and min values). • The Result: Finalized the maximum non-negative product at the bottom-right corner, applying the modulo as required. This problem is a great reminder that DP isn't always about just finding the "local max." Sometimes, you have to keep track of the extremes to catch those unexpected flips. 🚀 #LeetCode #Java #DynamicProgramming #Algorithms #DailyCode

🚀 Day 3 – Strings, Patterns & Optimizations! Today I dove deep into string problems and realized how much optimization matters. 💡 Highlights from Day 3: Anagram Check: Learned to map characters using frequency arrays. Why c - 'a' works now makes total sense. String Compression: Counting frequencies vs handling consecutive duplicates efficiently. Realized StringBuilder is a life-saver for performance. KMP Algorithm: Pattern searching without restarting. LPS array is the secret sauce! Learned to find patterns in O(n + m) time. 🔥 Key Lesson: It’s not just about solving a problem—it’s about solving it efficiently. Knowing the theory behind the code makes all the difference. From brute-force thinking → optimized thinking, every day I’m leveling up my coding skills. #DSA #Java #100DaysOfCode #CodingJourney #ProblemSolving #LearningDaily

Day: 73/365 📌 LeetCode POTD: Minimum Absolute Difference in Sliding Submatrix Medium Key takeaways/Learnings from this problem: 1. This problem shows how sliding window ideas extend to 2D, not just arrays, but it gets trickier to manage. 2. Maintaining a sorted structure (like multiset) helps in quickly finding min absolute differences in each window. 3. Big learning: brute force over every submatrix is too slow, so optimize by reusing previous window computations. 4. Overall, it’s a solid mix of 2D traversal + smart data structures to keep things efficient. #POTD #365DaysOfCode #DSA #Java #ProblemSolving #LearningInPublic #Consistency 🥷

Day 79: Sliding Submatrix Grinds 🔍 Problem 3567: Minimum Absolute Difference in Sliding Submatrix Today’s challenge was about finding the smallest gap between unique values within a shifting k×k window. It’s essentially a "Sliding Window" problem on a 2D scale. The Strategy: • Window Traversal: Iterated through every possible top-left coordinate where a k×k submatrix could fit. • Flatten & Sort: For each window, I gathered all elements into a list and sorted them. Sorting is the shortcut here, the minimum difference must exist between adjacent elements in a sorted list. • The "Unique" Check: Carefully calculated the absolute difference between neighboring elements, ignoring duplicates to find the true minimum gap. While the nested loops + sorting approach got the job done today, it’s a bit of a brute-force flex. It’s a solid reminder that sometimes "Make it work" is the first step before "Make it fast." 🚀 #LeetCode #Java #Algorithms #DataStructures #DailyCode

✨ Day 41 of 90 – Pattern Mastery Journey 🧠 Pattern:Reverse Alphabet Hash Pattern 💡 Approach: ✔ Used reverse looping (n → 1) to build the pattern ✔ Printed alphabets using ASCII logic `(char)('A' + i - 1)` ✔ Printed alphabet `i` times in each row ✔ Filled remaining positions with `#` using `(n - i)` ✔ Maintained proper structure and alignment 🚀 This problem helped me understand how reversing loops can change the entire pattern structure and improve control over output formatting. #PatternMasteryJourney #Java #CodingJourney #ProblemSolving

Day 55/75 — Shortest Subarray with Sum at Least K Today’s problem was a challenging one involving prefix sums and a monotonic deque. Approach: • Use prefix sum to convert subarray sum into difference of indices • Maintain a deque to keep indices in increasing order of prefix sums • Remove useless indices to keep it optimal Key logic: while (!dq.isEmpty() && ps[j] - ps[dq.peekFirst()] >= k) { minLen = Math.min(minLen, j - dq.pollFirst()); } while (!dq.isEmpty() && ps[j] <= ps[dq.peekLast()]) { dq.pollLast(); } dq.offerLast(j); Time Complexity: O(n) Space Complexity: O(n) A tough problem that builds strong intuition for prefix sums + deque optimization. 55/75 🚀 #Day55 #DSA #PrefixSum #Deque #Java #Algorithms #LeetCode

🚀 Day 50 of DSA – Minimum Absolute Difference in Sliding Submatrix Solved a matrix problem where for every k x k submatrix, we need to find the minimum absolute difference between any two distinct values. 💡 Key Insight For each submatrix: collect all values keep only distinct ones sort them the minimum absolute difference will always be between adjacent sorted values So instead of checking every pair, we can use a TreeSet to maintain sorted unique values directly. ⚡ Approach Iterate through every possible k x k window Store its elements in a TreeSet If only one distinct value exists, answer is 0 Otherwise, scan adjacent values in sorted order and compute minimum difference ⏱ Time Complexity: O((m-k+1)(n-k+1) * k² log(k²)) 💾 Space Complexity: O(k²) 📌 Lesson: Sometimes the best solution is not the most “fancy” sliding window optimization, but the one that matches the constraints cleanly and correctly. #DSA #LeetCode #Java #Algorithms #ProblemSolving

Day 44 of Daily DSA 🚀 Solved LeetCode 1572: Matrix Diagonal Sum ✅ Problem: Given a square matrix mat, return the sum of the matrix diagonals. Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal. Approach: Used a two-pointer technique to traverse both diagonals in a single pass. Steps: Initialize two pointers → start = 0, end = n-1 Traverse each row: Add mat[i][start] (primary diagonal) Add mat[i][end] (secondary diagonal) Move pointers: start++, end-- If matrix size is odd → add center element once ⏱ Complexity: • Time: O(n) • Space: O(1) 📊 LeetCode Stats: • Runtime: 0 ms (Beats 100%) ⚡ • Memory: 46.53 MB Optimizing nested loops into a single pass can make your solution both cleaner and faster 💡 #DSA #LeetCode #Java #Arrays #Matrix #CodingJourney #ProblemSolving

Day 45 of Daily DSA 🚀 Solved LeetCode 867: Transpose Matrix ✅ Problem: Given a 2D matrix, return its transpose (rows become columns and columns become rows). Approach: Created a new matrix and swapped indices while traversing. Steps: Get number of rows and columns Create a new matrix of size cols x rows Traverse original matrix Assign: trans[j][i] = matrix[i][j] Return the new matrix ⏱ Complexity: • Time: O(n × m) • Space: O(n × m) 📊 LeetCode Stats: • Runtime: 0 ms (Beats 100%) ⚡ • Memory: 46.46 MB Simple transformations like transpose build strong fundamentals for matrix-based problems 💡 #DSA #LeetCode #Java #Arrays #Matrix #CodingJourney #ProblemSolving