Solved: Sliding Window + Prefix Sum Problem

🚀 Day 414 of #500DaysOfCode 🔢 LeetCode 2536: Increment Submatrices by One (Medium) Today I worked on an interesting matrix manipulation problem that teaches an important optimization idea — 2D Difference Arrays. 🧠 Problem Summary We are given an n x n matrix initialized with zeros and a list of queries. Each query represents a submatrix, and we need to increment every element inside that submatrix by 1. A brute-force solution would update each cell for every query, which becomes inefficient when the matrix and number of queries grow. ⚡ Key Insight Instead of updating all cells directly, we use a 2D prefix / difference matrix technique: Update only the corners of each submatrix Convert the difference matrix into the final matrix using prefix sums Achieve O(n² + q) performance instead of O(q · n²) A neat trick that’s extremely useful for range update problems! ✅ Takeaways Difference arrays are not just for 1D — they scale beautifully to 2D Matrix prefix sums simplify many complex update operations Thinking in terms of range operations often leads to faster algorithms 💻 Tech Used Java 2D prefix sum optimization Matrix manipulation Another day, another concept mastered. On to the next challenge! 💪🔥 #coding #leetcode #java #programming #dsa #matrix #problemsolving #500DaysOfCode #Day414

🔥 Day 207 - Daily DSA Challenge! 🔥 Problem: 🧩 Longest Substring Without Repeating Characters Given a string s, find the length of the longest substring without repeating characters. 💡 Key Insights: 🔹 This is a classic Sliding Window problem. 🔹 We maintain a window of unique characters using a HashSet. 🔹 When a duplicate character appears, we shrink the window from the left until the substring becomes valid again. 🔹 Keep track of the maximum window size throughout. ⚡ Optimized Plan: ✅ Use two pointers (left, right) to form a dynamic window. ✅ Expand the right pointer to add characters. ✅ When a duplicate is found, move the left pointer until it’s removed. ✅ Update the max length after every expansion. ✅ Time Complexity: O(n) ✅ Space Complexity: O(k), where k = number of unique characters. 💬 Challenge for you: 1️⃣ Can you modify it to also return the substring itself instead of just its length? 2️⃣ How would you handle Unicode characters efficiently? #DSA #SlidingWindow #LeetCode #CodingChallenge #ProblemSolving #Java #100DaysOfCode

📌 Day 161 of Coding - Minimum Number of Increments on Subarrays to Form a Target Array (LeetCode - Hard) 🎯 Goal: Find the minimum number of operations required to form a target array starting from an array of zeros, where each operation increments all elements of a chosen subarray by 1. 💡Approach & Debugging: Used a difference-based greedy approach to count only the necessary increments. Steps: Initialize sum with the first element, representing the increments needed for the first number. Traverse the array: Whenever target[i] > target[i - 1], it means additional increments are needed. Add the difference (target[i] - target[i - 1]) to sum. The total sum gives the minimum number of operations required. ✔️ Time Complexity: O(N) - single pass through the array. ✔️ Space Complexity: O(1) - constant extra space. 🧠Key Takeaways: A classic prefix difference trick, focus on the increase, not the absolute value. Greedy approaches often emerge naturally in array transformation problems. #Day161 #LeetCode #GreedyAlgorithm #ArrayProblems #Java #ProblemSolving #DSA #Algorithms #CodingChallenge #InterviewPrep #100DaysOfCode #SoftwareEngineering #CodeNewbie #ProgrammersLife

Day 87/100 of DSA & LeetCode grind 🔥 Today's problem: 3318. Find X-Sum of All K-Long Subarrays I What I learned: • It's not always about prefix sums or classic sliding window. • Sometimes the real game is frequency + ordering logic. • For every window of size k, we: Count freq of each number Keep only the top x most frequent values (tie-break by bigger value 😮) Sum value * freq for those Key skills practiced: ✅ HashMap for freq tracking ✅ Sliding window add/remove in O(1) ✅ Custom sorting rule (by freq desc, value desc) ✅ Turning the problem statement into steps that code can actually do Why I liked this problem: This is the type of question that looks like brute force, but teaches you how to maintain state while the window moves. That's super important for real interviews. Mindset: DSA is not just solving one question. It's building patterns you can reuse. Still going. Still consistent. 🚀 #Day87 #LeetCode #DSA #100DaysOfCode #Java #SlidingWindow #ProblemSolving #Consistency

🚀 Day 392 of #500DaysOfCode Today I solved LeetCode 661: Image Smoother 🖼️ This problem was all about applying a 3x3 smoothing filter on an image (represented as a 2D matrix). For each pixel, we calculate the average value of the surrounding pixels — considering only the valid neighbors — and take the floor of the result. It’s a great exercise for mastering matrix traversal and boundary condition handling in Java! 💡 🔍 Key Learnings: How to navigate a 2D grid using directional arrays. Handling edge cells carefully (like corners and borders). Efficiently applying averaging filters using nested loops. 🧠 Example: Input: [[100,200,100],[200,50,200],[100,200,100]] Output: [[137,141,137],[141,138,141],[137,141,137]] 💻 Language: Java 🔹 Difficulty: Easy Every problem like this strengthens my fundamentals in array manipulation and spatial algorithms — one step closer to writing cleaner, more efficient code. #Day392 #LeetCode #Java #CodingChallenge #100DaysOfCode #500DaysOfCode #ProblemSolving #SoftwareEngineering #MatrixAlgorithms

📌 Day 12/100 – 100 Days of Code Challenge 🚀 Today’s LeetCode challenge: “Trapping Rain Water” (LeetCode #42) – one of the most popular Hard-level problems that strengthens logic building and array manipulation skills. 🔹 Approach: Used precomputed leftMax and rightMax arrays to determine how much water each bar can trap. For every index, the trapped water = min(leftMax[i], rightMax[i]) - height[i]. 🔹 Key Learnings: Improved understanding of prefix and suffix computations. Reinforced problem-solving using array-based preprocessing. Time Complexity: O(n) Space Complexity: O(n) #100DaysOfCode #LeetCode #Java #DSA #Arrays #TwoPointer #ProblemSolving #CodingJourney #DynamicProgramming #DailyChallenge

✅ Day 59 of LeetCode Medium/Hard Edition Today’s challenge was “Maximum Alternating Subsequence Sum” — a beautifully balanced dynamic programming problem that turns simple addition into an elegant alternation of signs ⚖️➕➖ 📦 Problem: Given an integer array nums, you need to choose a subsequence (not necessarily contiguous) that maximizes its alternating sum, defined as the sum of elements at even indices minus the sum of elements at odd indices. For example: nums = [4,2,5,3] → optimal subsequence [4,2,5,3] gives (4 + 5) - (2 + 3) = 4. 🔗 Problem Link: https://lnkd.in/g5M-iugB ✅ My Submission: https://lnkd.in/gUmnEyUU 💡 Thought Process: At each index, we have two choices — either include the current element (flipping the sign based on its position in the subsequence) or skip it. This naturally forms a two-state dynamic programming model: turn = 0 → we add the number (even position) turn = 1 → we subtract the number (odd position) The recurrence relation becomes: dp[i][turn] = max( (turn == 0 ? +nums[i] : -nums[i]) + dp[i+1][1-turn], dp[i+1][turn] ) Using memoization, we ensure that overlapping subproblems are efficiently reused. ⚙️ Complexity: ⏱ Time: O(n) 💾 Space: O(n) (can be optimized to O(1)) ✨ Key Insight: What makes this problem elegant is how a simple alternation pattern translates into a strategic inclusion/exclusion decision — showing the beauty of dynamic programming in managing state transitions efficiently. #LeetCodeMediumHardEdition #100DaysChallenge #DynamicProgramming #Recursion #ProblemSolving #Java #LeetCode #CodingChallenge

📌 Day 160 of Coding - Reconstruct a 2-Row Binary Matrix (LeetCode - Medium) 🎯 Goal: Reconstruct a 2-row binary matrix given the sums of each column (colsum), and total ones allowed in the upper and lower rows (upper, lower). 💡Approach & Debugging: Used a greedy approach to fill the matrix step by step while maintaining constraints. Steps: Traverse all columns: If colsum[i] == 2, both rows must have 1. Decrease both upper and lower. Traverse again for colsum[i] == 1: Assign 1 to the row with remaining quota (upper first, else lower). If any quota (upper or lower) remains after processing, return an empty list (invalid configuration). Otherwise, return the constructed matrix. ✔️ Time Complexity: O(N) - single traversal of the array. ✔️ Space Complexity: O(N) - to store the two rows. #Day160 #LeetCode #GreedyAlgorithm #Matrix #ProblemSolving #Java #CodingChallenge #DSA #Algorithms #100DaysOfCode #InterviewPrep #SoftwareEngineering #DataStructures #CodeNewbie #ProgrammersLife

🎯 LeetCode Problem Solved: Spiral Matrix (Problem #54) Just wrapped up another fun challenge — printing all elements of a matrix in spiral order 🌀 At first glance, it looks simple, but managing the boundaries (top, bottom, left, right) while looping through the matrix really puts your logic skills to the test. 💪 Through this problem, I learned how important it is to handle edge cases and loop conditions carefully — a small mistake can easily break the spiral! 👨💻 Language: Java 🔢 Concepts Used: Arrays, Loops, Boundary Management Here’s a quick peek at my solution ⬇️ (Screenshot attached) #LeetCode #Java #CodingJourney #ProblemSolving #DataStructures #ComputerScience