Counting Subarrays with Exactly k Odd Numbers

Not all sliding window problems are about sums — sometimes the constraint is on the product, but the pattern still applies. 🚀 Day 103/365 — DSA Challenge Solved: Subarray Product Less Than K Problem idea: We need to count the number of subarrays where the product of all elements is strictly less than k. Efficient approach: Use a sliding window that maintains a valid product. Steps: 1. Expand the window by multiplying the current element 2. If product becomes ≥ k, shrink the window from the left 3. Keep dividing until product < k 4. Count all valid subarrays ending at each index This works because all numbers are positive, so the window can be adjusted greedily. ⏱ Time: O(n) 📦 Space: O(1) Day 103/365 complete. 💻 262 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #SlidingWindow #LeetCode #LearningInPublic

“Most people try to overcomplicate this one… but the simplest approach wins.” Day 69 — LeetCode Progress Problem: Height Checker Required: Given an array of student heights, return the number of indices where the heights are not in the expected non-decreasing order. Idea: If we sort the array, we get the expected order. Now just compare the original array with the sorted version — mismatches are the answer. Approach: Create a copy of the original array Sort the copied array Traverse both arrays: Compare elements at each index If they differ → increment count Return the count Time Complexity: O(n log n) Space Complexity: O(n) #LeetCode #DSA #Java #Arrays #Sorting #ProblemSolving #CodingJourney

Day 65/75 — Count Pairs Whose Sum is Less than Target Today’s problem was a clean application of sorting + two pointers. Approach: • Sort the array • Use two pointers (i at start, j at end) • If nums[i] + nums[j] < target → all pairs between i and j are valid • Add (j - i) to count and move i forward • Otherwise, move j backward Key idea: if(nums.get(i) + nums.get(j) < target)  count += (j - i); Time Complexity: O(n log n) (sorting) Space Complexity: O(1) This pattern shows up a lot in pair-based problems — very important to master. 65/75 🔥 #Day65 #DSA #TwoPointers #Sorting #Java #LeetCode

Some subarray counting problems become much easier when we transform them into “at most” problems. 🚀 Day 101/365 — DSA Challenge Solved: Binary Subarrays With Sum Problem idea: We need to count the number of subarrays whose sum equals a given goal in a binary array. Efficient approach: Instead of directly counting subarrays with exact sum, we use a trick: subarrays with sum = goal = subarrays with sum ≤ goal − subarrays with sum ≤ (goal − 1) Steps: 1. Create a helper function to count subarrays with sum at most k 2. Use a sliding window to maintain a valid window where sum ≤ k 3. Add the number of valid subarrays ending at each index 4. Subtract results to get the exact count for the goal This converts the problem into an efficient sliding window solution. ⏱ Time: O(n) 📦 Space: O(1) Day 101/365 complete. 💻 264 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #SlidingWindow #LeetCode #LearningInPublic

Some problems break the standard sliding window pattern — especially when negative numbers are involved. 🚀 Day 104/365 — DSA Challenge Solved: Shortest Subarray with Sum at Least K Problem idea: We need to find the length of the shortest subarray whose sum is at least k. The challenge is that the array can contain negative numbers, so normal sliding window won't work. Efficient approach: Use Prefix Sum + Monotonic Deque. Steps: 1. Build a prefix sum array 2. Use a deque to store indices of useful prefix sums 3. While current sum − smallest prefix ≥ k → update answer 4. Maintain increasing order in deque by removing larger prefix sums from the back 5. This ensures we always get the shortest valid subarray This approach efficiently handles negative numbers while keeping optimal time complexity. ⏱ Time: O(n) 📦 Space: O(n) Day 104/365 complete. 💻 261 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #SlidingWindow #Deque #PrefixSum #LeetCode #LearningInPublic

Some problems become much easier when you reframe the question. 🚀 Day 107/365 — DSA Challenge Solved: Minimum Operations to Reduce X to Zero Problem idea: We need to remove elements from the left or right so that their sum equals x, with minimum operations. Efficient approach: Instead of removing elements, think in reverse: 👉 Find the longest subarray with sum = totalSum − x Steps: 1. Calculate total sum of the array 2. Set target = totalSum − x 3. Find the longest subarray with sum = target using sliding window 4. Result = total length − longest subarray length This converts the problem into a familiar sliding window problem. ⏱ Time: O(n) 📦 Space: O(1) Day 107/365 complete. 💻 258 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #SlidingWindow #LeetCode #LearningInPublic

Many array problems that involve maximizing a window can be solved using the sliding window technique. 🚀 Day 98/365 — DSA Challenge Solved: Max Consecutive Ones III Problem idea: We need to find the maximum number of consecutive 1's in a binary array if we are allowed to flip at most k zeros. Efficient approach: Use a sliding window that allows at most k zeros inside the window. Steps: 1. Expand the window by moving the right pointer 2. Count how many zeros are inside the window 3. If zero count becomes greater than k, move the left pointer until zeros ≤ k 4. Track the maximum window length This keeps the window valid while maximizing the number of 1's. ⏱ Time: O(n) 📦 Space: O(1) Day 98/365 complete. 💻 267 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #SlidingWindow #LeetCode #LearningInPublic

Day 42 of Daily DSA 🚀 Solved LeetCode 921: Minimum Add to Make Parentheses Valid ✅ Problem: Given a parentheses string s, return the minimum number of moves required to make it valid. Rules: A valid string has balanced opening and closing brackets You can insert a parenthesis at any position Return the minimum additions needed Approach: Used a Stack + Counter approach to track unmatched parentheses. Steps: Traverse the string Push '(' onto stack If ')' and stack has '(' → pop Else → increment counter (unmatched closing) At the end → remaining stack size = unmatched openings Result = unmatched openings + unmatched closings ⏱ Complexity: • Time: O(n) • Space: O(n) 📊 LeetCode Stats: • Runtime: 1 ms (Beats 67.19%) ⚡ • Memory: 43.08 MB Nice extension of the Valid Parentheses problem, focusing on fixing invalid cases instead of just checking them. #DSA #LeetCode #Java #Stack #ProblemSolving #CodingJourney #Consistency

🖤 Day 44 of Solving DSA : Today, I implemented a solution to generate Pascal’s Triangle, a classic problem that helps strengthen problem-solving and array manipulation skills. 🔺 What is Pascal’s Triangle? It is a triangular array where: The first and last elements of each row are always 1 Every middle element is the sum of two elements from the previous row Example: [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] 💡 Approach I Used: 1️⃣ Initialize Result List Create a list to store all rows of the triangle. 2️⃣ Iterate for Each Row Loop from 0 to numRows - 1 to build each row. 3️⃣ Set First and Last Elements Each row starts and ends with 1. 4️⃣ Calculate Middle Elements Use values from the previous row: 👉 current[j] = prev[j-1] + prev[j] 5️⃣ Store Each Row Add the constructed row to the result list. #DSA #java #100dayschallenge #leetcode #consistency

Day 8/30 — DSA Challenge 🚀 Problem: Search a 2D Matrix II Topic: Matrix + Binary Search Pattern Difficulty: Medium Approach: Started from top-right corner of the matrix If current element == target → return true If current element < target → move down If current element > target → move left Mistake / Challenge: Initially tried applying binary search like previous problem (LeetCode 74) Realized matrix is not globally sorted, so that approach fails Fix: Used optimal “staircase search” approach Reduced time complexity efficiently Key Learning: Not all sorted matrices can be treated as 1D arrays Recognize pattern: row-wise + column-wise sorted → use pointer approach Time Taken: 45 minutes Consistency check ✅ See you on Day 9. GitHub Repo: https://lnkd.in/gHW9vKUf #DSA #LeetCode #Java #Matrix #BinarySearch #LearningInPublic