Max Area of Submatrix in Binary Matrix

🚀 Day 18 of 100 Days LeetCode Challenge Problem: Count Submatrices with Top-Left Element and Sum ≤ k Today’s problem is a clean application of 2D Prefix Sum (Cumulative Sum) 🔥 💡 Key Insight: All valid submatrices must: Start from the top-left corner (0,0) Extend to any cell (i, j) 👉 So instead of checking all submatrices, we just: Compute sum from (0,0) to (i,j) Check if it’s ≤ k 🔍 Core Approach: 1️⃣ Build Prefix Sum Matrix prefix[i][j] = sum of all elements from (0,0) to (i,j) 2️⃣ Iterate Through Grid For every (i, j): If prefix[i][j] ≤ k → count it ✅ 👉 That’s it! No need for complex nested submatrix checks 🚀 🔥 What I Learned Today: Constraints simplify problems → use them wisely 2D prefix sum reduces O(n⁴) → O(n²) Always check if the problem has a fixed starting point 📈 Challenge Progress: Day 18/100 ✅ Almost 20 days consistency! LeetCode, Prefix Sum, Matrix, 2D Arrays, Optimization, Algorithms, DSA Practice, Coding Challenge, Problem Solving #100DaysOfCode #LeetCode #DSA #CodingChallenge #PrefixSum #Matrix #ProblemSolving #TechJourney #ProgrammerLife #SoftwareDeveloper #CodingLife #LearnToCode #Developers #Consistency #GrowthMindset #InterviewPrep

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/gK993p-S 💡 My thought process: The main function, minAbsDiff, goes through all possible top-left positions of the k × k submatrices. For each position (i, j), it calls the helper function solve to find the result for that submatrix and stores it in the answer matrix, which has a size of (m − k + 1) × (n − k + 1). The solve function collects all elements from the k × k submatrix starting at (i, j) and puts them into a set. This automatically sorts the elements and removes duplicates. If the set has only one unique element, the function returns 0 because all values are the same. If there are multiple unique elements, the function goes through the sorted set and calculates the absolute difference between each pair of consecutive elements. Since the set is sorted, the minimum absolute difference will be between adjacent elements. The smallest difference is tracked and returned. The overall time complexity is O((m − k + 1) × (n − k + 1) × k² log(k²)) because each submatrix requires inserting k² elements into a set and iterating through it. The space complexity is O(k²) for storing elements of each submatrix. 👉 My Solution: https://lnkd.in/gj6juuUU If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

🚀 Day 19 of 100 Days LeetCode Challenge Problem: Count Submatrices With Equal Frequency of X and Y Today’s problem was a solid combination of 2D Prefix Sum + Hashing concept 🔥 💡 Key Insight: We need submatrices that: Include the top-left cell (0,0) Have equal number of 'X' and 'Y' Contain at least one 'X' 👉 Trick: Convert the grid into values: 'X' → +1 'Y' → -1 '.' → 0 🔍 Core Approach: 1️⃣ 2D Prefix Sum Transformation Build prefix sum based on above conversion 2️⃣ Check Each Submatrix (0,0 → i,j) If sum == 0 → equal number of X and Y ✅ 3️⃣ Extra Condition: Ensure at least one 'X' exists 👉 Track X count separately using another prefix matrix 🔥 What I Learned Today: Transforming problems into numbers simplifies logic Prefix sums + condition checks = powerful combo Always handle extra constraints carefully 📈 Challenge Progress: Day 19/100 ✅ Almost hitting Day 20! LeetCode, Prefix Sum, Matrix, Hashing, Problem Transformation, Algorithms, DSA Practice, Coding Challenge, Problem Solving #100DaysOfCode #LeetCode #DSA #CodingChallenge #PrefixSum #Matrix #Hashing #ProblemSolving #TechJourney #ProgrammerLife #SoftwareDeveloper #CodingLife #LearnToCode #Developers #Consistency #GrowthMindset #InterviewPrep

Day 49 on LeetCode — Defuse the Bomb 💣✅ Today’s problem focused on circular arrays and window-based summation. 🔹 Approach Used in My Solution The goal was to transform the array based on k by summing the next or previous elements in a circular manner. Key idea in the solution: • Handle three cases:   – k > 0 → sum of next k elements   – k < 0 → sum of previous k elements   – k == 0 → all values become 0 • Used modulo arithmetic (% n) to handle circular traversal • For each index, computed the sum by iterating forward/backward 🧠 Insight & Optimization Thought: Initially solved it using a brute-force sliding window idea (O(n × k)), which works perfectly fine and is intuitive. However, this can be further optimized into a true sliding window approach with O(n) by reusing the previous window sum instead of recalculating it every time. ⚡ Complexity (Current Approach): • Time Complexity: O(n × |k|) • Space Complexity: O(n) 💡 Key Takeaways: • Understood how brute-force windowing can lead to optimized sliding window solutions • Practiced handling circular arrays with modulo operations • Learned to identify opportunities to optimize from O(n × k) → O(n) #LeetCode #DSA #Algorithms #DataStructures #SlidingWindow #Arrays #CircularArray #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

Day 60 on LeetCode Range Sum Query 2D (Immutable) 🧮✅ Today’s problem was a major step forward into 2D Prefix Sum, extending the 1D concept into matrices. 🔹 Approach Used in My Solution The goal was to efficiently answer multiple submatrix sum queries. Key idea in the solution: • Precompute a 2D prefix sum matrix where each cell stores the sum of elements from (0,0) to (i,j) • While building prefix:   prefix[i][j] = matrix[i][j] + top + left - topLeft • For any query (row1, col1) to (row2, col2):   Use inclusion-exclusion:   total - top - left + topLeft This allows answering each query in constant time after preprocessing. ⚡ Complexity: • Preprocessing Time: O(m × n) • Query Time: O(1) • Space Complexity: O(m × n) 💡 Key Takeaways: • Learned how 2D prefix sums extend 1D cumulative logic • Understood inclusion-exclusion principle in matrices • Optimized multiple queries from O(n²) → O(1) per query 🔥 This unlocks powerful techniques for matrix-based problems! #LeetCode #DSA #Algorithms #DataStructures #PrefixSum #2DPrefixSum #Matrices #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

Day 51 on LeetCode — Permutation in String 🔤✅ Today’s problem was a strong application of the Sliding Window + Frequency Count technique. 🔹 Approach Used in My Solution The goal was to check if any permutation of s1 exists as a substring in s2. Key idea in the solution: • Use two frequency arrays (size 26) to track character counts • Initialize frequencies for s1 and the first window of s2 • Compare both frequency arrays — if equal, permutation exists • Slide the window across s2:   – Add incoming character   – Remove outgoing character • Check for a match at each step This ensures we efficiently check all substrings of size k without recomputing frequencies. ⚡ Complexity: • Time Complexity: O(n) • Space Complexity: O(1) 💡 Key Takeaways: • Mastered sliding window with fixed-size frequency arrays • Learned how to efficiently detect anagram/permutation patterns • Reinforced optimizing from brute force to linear-time solutions #LeetCode #DSA #Algorithms #DataStructures #SlidingWindow #Strings #Hashing #FrequencyArray #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

Day 48 on LeetCode Minimum Size Subarray Sum 🎯✅ Today’s problem was a perfect application of the Sliding Window technique for optimizing subarray problems. 🔹 Approach Used in My Solution The goal was to find the smallest subarray length whose sum is greater than or equal to the target. Key idea in the solution: • Use two pointers low and high to maintain a dynamic window • Expand the window by moving high and adding elements to currentSum • Once the sum becomes ≥ target, start shrinking the window from the left (low) • Continuously update the minimum length during this process • If no valid subarray is found, return 0 This approach avoids brute force and ensures we process each element at most twice. ⚡ Complexity: • Time Complexity: O(n) • Space Complexity: O(1) 💡 Key Takeaways: • Mastered the Sliding Window technique for variable window size • Learned how to optimize subarray problems from O(n²) to O(n) • Reinforced handling dynamic window expansion and contraction #LeetCode #DSA #Algorithms #DataStructures #SlidingWindow #Arrays #TwoPointers #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

Day 72 on LeetCode Search a 2D Matrix 🔍📊✅ Today’s problem was a great application of Binary Search in 2D, breaking it down into two efficient steps. 🔹 Approach Used in My Solution The goal was to determine whether a target exists in a sorted 2D matrix. Key idea in the solution: • First, apply binary search on rows to find the potential row where the target could exist   – Check if target lies between matrix[mid][0] and matrix[mid][cols-1] • Once the correct row is found, apply binary search within that row • Return true if found, otherwise false This avoids scanning the entire matrix and ensures efficiency. 🔹 Why This Works Because: • Each row is sorted • The first element of each row is greater than the last of the previous row So we can treat it like a two-level binary search problem. ⚡ Complexity: • Time Complexity: O(log m + log n) • Space Complexity: O(1) 💡 Key Takeaways: • Learned how to extend binary search to 2D structures • Practiced breaking problems into smaller searchable spaces • Reinforced thinking in terms of hierarchical searching 🔥 Another solid step in mastering binary search patterns! #LeetCode #DSA #Algorithms #DataStructures #BinarySearch #Matrix #2DArray #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

Day 52 on LeetCode — Minimum Recolors to Get K Consecutive Black Blocks 🧩✅ Today’s problem was another clean application of the Sliding Window technique with optimization. 🔹 Approach Used in My Solution The goal was to find the minimum number of recolors (W → B) needed to get k consecutive black blocks. Key idea in the solution: • Treat it as finding a window of size k with minimum 'W' (white blocks) • Count the number of 'W' in the first window of size k • Slide the window across the string:   – Remove the left character (if it was 'W')   – Add the new right character (if it is 'W') • Keep track of the minimum changes required This avoids recomputation and ensures an efficient linear solution. ⚡ Complexity: • Time Complexity: O(n) • Space Complexity: O(1) 💡 Key Takeaways: • Strengthened understanding of fixed-size sliding window problems • Learned how to convert problems into min/max count in a window • Reinforced optimizing from brute force to O(n) solutions #LeetCode #DSA #Algorithms #DataStructures #SlidingWindow #Strings #TwoPointers #ProblemSolving #Coding #Programming #Cpp #STL #SoftwareEngineering #ComputerScience #CodingPractice #DeveloperLife #TechJourney #CodingDaily #100DaysOfCode #BuildInPublic #AlgorithmPractice #CodingSkills #Developers #TechCommunity #SoftwareDeveloper #EngineeringJourney

🚀 Day 28/50 – LeetCode Challenge 🧩 Problem: String Compression Today’s problem focused on modifying an array in-place while compressing repeated characters — a great exercise in two pointers and string manipulation. 📌 Problem Summary: Given an array of characters, compress it by replacing consecutive repeating characters with the character followed by its count. Example: Input: ["a","a","b","b","c","c","c"] Output: ["a","2","b","2","c","3"] The compression must be done in-place without using extra space. 🔍 Approach Used ✔ Used two pointers: one for reading characters one for writing compressed result ✔ Counted consecutive repeating characters ✔ Wrote the character and its count (if > 1) ✔ Continued until the end of the array ⏱ Time Complexity: O(n) 📦 Space Complexity: O(1) 💡 Key Learning ✔ In-place array manipulation ✔ Efficient use of two pointer technique ✔ Handling counts and conversions to string ✔ Writing optimized space-efficient solutions This problem highlights how careful pointer management can lead to efficient solutions. Consistency builds strong problem-solving skills 🚀 🔗 Problem Link: https://lnkd.in/geeBTB3P #50DaysOfLeetCode #LeetCode #DSA #TwoPointers #Strings #ProblemSolving #CodingJourney #FutureAIEngineer #Consistency