Prefix Sum & Sliding Window Techniques in LeetCode Challenges

📘 DSA Journey — Day 22 Today’s focus: Prefix Sum + Fixed Window optimization. Problem solved: • K Radius Subarray Averages (LeetCode 2090) Concepts used: • Prefix Sum • Fixed-size sliding window • Efficient range sum calculation Key takeaway: The goal is to calculate the average of subarrays centered at each index with radius k. A brute-force approach would recompute sums for every index, leading to O(n·k) time. Instead, using prefix sum, we can compute any subarray sum in O(1) time. For each index i, the valid window is: [i - k, i + k] If this window is within bounds, we calculate the sum using prefix sum and divide by (2k + 1). If not enough elements exist on either side, we return -1. This approach reduces the complexity to O(n) and avoids repeated calculations. This problem highlights how prefix sum helps in efficiently handling range-based queries. Continuing to strengthen fundamentals and consistency in DSA problem solving. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 28 Today’s focus: Binary Search for minimum in rotated arrays. Problem solved: • Find Minimum in Rotated Sorted Array (LeetCode 153) Concepts used: • Binary Search • Identifying unsorted half • Search space reduction Key takeaway: The goal is to find the minimum element in a rotated sorted array. Using binary search, we compare the mid element with the rightmost element: • If nums[mid] > nums[right] → minimum lies in the right half • Else → minimum lies in the left half (including mid) This works because the rotation creates one unsorted region, and the minimum always lies in that region. By narrowing the search space each time, we achieve O(log n) time complexity. This problem highlights how slight modifications in array structure still allow binary search to work efficiently with the right observations. Continuing to strengthen binary search patterns and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 11 Today’s focus: Sliding Window with distinct element constraints. Problem solved: • Subarrays with K Different Integers (LeetCode 992) Concepts used: • Sliding Window / Two-pointer technique • Frequency tracking using HashMap • Counting subarrays using window expansion Key takeaway: The goal of this problem is to count the number of subarrays that contain exactly K distinct integers. A useful trick here is to break the problem into two parts: Subarrays with exactly K distinct = Subarrays with at most K distinct − Subarrays with at most (K−1) distinct Using a sliding window, we maintain a window that contains at most K distinct elements. A frequency map keeps track of how many times each element appears in the current window. As the window expands, if the number of distinct elements exceeds K, we shrink the window from the left until the condition is satisfied again. At each step, the number of valid subarrays ending at the current index can be counted efficiently, allowing the entire problem to be solved in O(n) time. Continuing to strengthen pattern recognition and consistency in solving DSA problems. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 33 Today’s focus: Binary Search for next greater element. Problem solved: • Find Smallest Letter Greater Than Target (LeetCode 744) Concepts used: • Binary Search • Upper bound concept • Circular handling Key takeaway: The goal is to find the smallest character strictly greater than a given target in a sorted array. This is a classic upper bound problem: We use binary search to find the first element greater than the target. During search: • If letters[mid] > target, store it as a possible answer and move left • Else move right An important edge case: If no character is greater than the target, we return the first element (circular behavior). Continuing to strengthen binary search patterns and problem-solving consistency. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 35 Today’s focus: Binary Search with index patterns. Problem solved: • Single Element in a Sorted Array (LeetCode 540) Concepts used: • Binary Search • Index parity (even/odd pattern) • Search space reduction Key takeaway: The array is sorted and every element appears twice except one. A key observation: Before the single element, pairs start at even indices After the single element, this pattern breaks. Using binary search: • If mid is even and nums[mid] == nums[mid + 1], the single element lies on the right side • Else, it lies on the left side (including mid) By leveraging this pattern, we can find the answer in O(log n) time and O(1) space. Continuing to strengthen binary search intuition and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 31 Today’s focus: Binary Search for boundaries and square roots. Problems solved: • Sqrt(x) (LeetCode 69) • Search Insert Position (LeetCode 35) Concepts used: • Binary Search • Search space reduction • Boundary conditions Key takeaway: In Sqrt(x), the goal is to find the integer square root. Using binary search, we search in the range [1, x] and check mid * mid against x to narrow down the answer. This avoids linear iteration and achieves O(log n) time. In Search Insert Position, we use binary search to find either: • The exact position of the target, or • The correct index where it should be inserted The key idea is that when the target is not found, the final position of the left pointer gives the correct insertion index. These problems highlight how binary search is not just for finding elements, but also for determining positions and boundaries efficiently. Continuing to strengthen fundamentals and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

Classical Backtracking Problem with a Classical Approach Solved Word Search (LeetCode 79) using a clean and intuitive DFS + Backtracking strategy Approach (Simple & Clear): •Start from every cell that matches the first character of the word. •Use DFS (Depth-First Search) to explore all 4 directions (up, down, left, right). •Mark the current cell as visited (by replacing it temporarily) to avoid revisiting. •If the full word is matched → return true immediately. •Backtrack by restoring the cell when the path doesn’t work. Key Insight: We explore all possible paths, but prune early when characters don’t match — this keeps the solution efficient. ⏱️ Time Complexity: 👉 O(m × n × 4^L) •m × n → starting points •4^L → exploring 4 directions for each character of length L 📌 Space Complexity: 👉 O(L) (recursion stack) 🔥 Clean recursion + smart backtracking = problem cracked! #DSA #Backtracking #LeetCode #CodingInterview #Java #ProblemSolving

📘 DSA Journey — Day 27 Today’s focus: Binary Search on modified arrays. Problem solved: • Search in Rotated Sorted Array (LeetCode 33) Concepts used: • Binary Search • Identifying sorted halves • Conditional search space reduction Key takeaway: This problem extends binary search to a rotated sorted array, where the array is not fully sorted but divided into two sorted parts. At each step, we: • Find the mid element • Check which half (left or right) is sorted • Decide whether the target lies in the sorted half • Eliminate the other half This allows us to still achieve O(log n) time complexity. Continuing to strengthen fundamentals and problem-solving consistency. #DSA #Java #LeetCode #CodingJourney

Day 47 of Daily DSA 🚀 Solved LeetCode 74: Search a 2D Matrix ✅ Problem: Given a sorted 2D matrix where: • Each row is sorted • First element of each row > last element of previous row Find whether a target exists in the matrix. Approach: Used an optimized staircase search (top-right traversal). Steps: Start from top-right corner If element == target → return true If element > target → move left If element < target → move down Continue until found or out of bounds ⏱ Complexity: • Time: O(n + m) • Space: O(1) 📊 LeetCode Stats: • Runtime: 0 ms (Beats 100%) ⚡ • Memory: 43.84 MB Sometimes choosing the right starting point (top-right) makes the search super efficient 💡 #DSA #LeetCode #Java #Matrix #BinarySearch #CodingJourney #ProblemSolving

📘 DSA Journey — Day 24 Today’s focus: Prefix Sum for range queries. Problem solved: • Count Vowel Strings in Ranges (LeetCode 2559) Concepts used: • Prefix Sum • Efficient range query processing • String boundary checks Key takeaway: The goal is to count how many strings in a given range start and end with a vowel. A direct approach would check each query range individually, leading to higher time complexity. Instead, we preprocess using a prefix sum array: • Mark each word as 1 if it starts and ends with a vowel, else 0 • Build a prefix sum over this array For any query [l, r], the answer can be found in O(1) using: prefix[r] - prefix[l - 1] This reduces the overall complexity significantly when handling multiple queries. This problem highlights how prefix sum is extremely useful for repeated range-based queries. Continuing to strengthen fundamentals and consistency in DSA problem solving. #DSA #Java #LeetCode #CodingJourney