Mastering Prefix Sum for Efficient Range Sum Queries

Day - 63 Combination Sum III The problem - Find all combinations of k numbers that sum to n, using only numbers 1-9, each number used at most once. Example : k = 3, n = 7 → [[1,2,4]] Brute Force - Generate all C(9, k) combinations, check each sum, still needs to enumerate all combinations. Approach Used - •) Initialize: Call findCombination(k, 1, n, new ArrayList<>(), ans) (start with number 1). •) findCombination(k, num, target, lst, ans), •) If (target == 0 && k == 0), found valid combination, add new ArrayList(lst) to ans and return. •) Recursive case, for num to 9, 1 - If i > target || k <= 0, break. 2 - Add i to lst. 3 - Recurse with k - 1 (need one less number), i + 1 (next number to try), target - i (remaining sum). 4 - Backtrack: remove i from lst. Complexity - Time - O(C(9, k) × k), C(9,k) combinations, k time to copy each. Space - O(k), recursion depth. Note - Loop from 1-9, add number, recurse with k-1 and target-num. Backtrack when target == 0 && k == 0! #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🔥 Day 304 – Daily DSA Challenge! 🔥 Problem: 🎯 Combination Sum II Given an array of candidate numbers (with possible duplicates) and a target value, return all unique combinations where the chosen numbers sum to the target. 👉 Each number can be used at most once in a combination. 💡 Key Insights: 🔹 This is a classic backtracking + pruning problem. 🔹 Sorting the array is crucial to handle duplicates efficiently. 🔹 Skip repeated elements at the same recursion level to avoid duplicate combinations. 🔹 Once a number exceeds the remaining target, we can stop early (thanks to sorting). 🔹 Always move to i + 1 since each element can be used only once. ⚡ Optimized Plan: ✅ Sort the candidates array ✅ Use backtracking to explore all valid combinations ✅ Maintain a temporary list (cur) for the current path ✅ Add the path to result when target == 0 ✅ Skip duplicates using if (i > idx && a[i] == a[i - 1]) ✅ Backtrack after each recursive call ✅ Time Complexity: O(2ⁿ) in the worst case ✅ Space Complexity: O(n) (recursion stack + current combination) 💬 Challenge for you: 1️⃣ What happens if we remove sorting — how do duplicates affect the output? 2️⃣ How is this problem different from Combination Sum I? 3️⃣ Can you convert this recursive solution into an iterative one? #DSA #LeetCode #Backtracking #Recursion #ProblemSolving #Java #KeepCoding

𝗠𝗼𝘀𝘁 𝗗𝗦𝗔 𝗽𝗿𝗼𝗯𝗹𝗲𝗺𝘀 𝗮𝗿𝗲 𝘀𝗹𝗼𝘄 𝗯𝗲𝗰𝗮𝘂𝘀𝗲 𝘄𝗲 𝗸𝗲𝗲𝗽 𝘀𝗲𝗮𝗿𝗰𝗵𝗶𝗻𝗴 𝘁𝗵𝗲 𝗽𝗮𝘀𝘁 𝗮𝗴𝗮𝗶𝗻 𝗮𝗻𝗱 𝗮𝗴𝗮𝗶𝗻. There is a faster way. Day 4/30 – DSA Pattern: Hashing (Frequency Map) 🧠 How to spot this pattern If the problem asks: • Frequency or count • Seen before? • Duplicates • Fast lookup • Subarray counts (with Prefix Sum) 👉 Think HashMap 💡 Simple idea Instead of scanning the array again and again:  • Store what you have already seen  • Store how many times you saw it  • Reuse that information instantly 𝗦𝗲𝗮𝗿𝗰𝗵𝗶𝗻𝗴 𝗯𝗲𝗰𝗼𝗺𝗲𝘀 𝗢(𝟭) 𝗶𝗻𝘀𝘁𝗲𝗮𝗱 𝗼𝗳 𝗢(𝗻). ✏️ Pseudocode 𝙢𝙖𝙥 = 𝙚𝙢𝙥𝙩𝙮 𝙢𝙖𝙥 𝙛𝙤𝙧 𝙚𝙡𝙚𝙢𝙚𝙣𝙩 𝙞𝙣 𝙖𝙧𝙧𝙖𝙮:   𝙞𝙛 𝙚𝙡𝙚𝙢𝙚𝙣𝙩 𝙚𝙭𝙞𝙨𝙩𝙨 𝙞𝙣 𝙢𝙖𝙥:     𝙞𝙣𝙘𝙧𝙚𝙖𝙨𝙚 𝙞𝙩𝙨 𝙘𝙤𝙪𝙣𝙩   𝙚𝙡𝙨𝙚:     𝙨𝙩𝙤𝙧𝙚 𝙞𝙩 𝙬𝙞𝙩𝙝 𝙘𝙤𝙪𝙣𝙩 1 🧩 Problems that use this • Two Sum • Frequency of elements • First non-repeating element • Subarray sum equals K • Nice subarrays (Prefix Sum + HashMap) 🔥 One rule to remember If you keep checking the past again and again, store it in a HashMap. Hashing turns: ❌ repeated searching into ✅ instant lookup Tomorrow: Binary Search 👍 if this helped Comment “DSA” to follow the 30-day pattern series. #DSA #ProblemSolving #Java #CodingInterviews #LearningInPublic #30DaysOfDSA

Today’s focus was on solving a real logical problem using strings — checking whether multiple words are anagrams. This felt different from earlier steps because it required combining string handling, sorting, and comparison logic instead of only modifying characters. What became clearer during this problem: - Two strings are anagrams when their sorted character sequences become identical - Converting a string to a character array and sorting it makes comparison straightforward - Logical validation across multiple strings builds real problem-solving confidence, not just syntax familiarity A small example used for practice: String[] arr = { "listen", "silent", "enlist" }; String base = sort(arr[0]); boolean ok = true; for (String s : arr) { if (!sort(s).equals(base)) { ok = false; break; } } System.out.println("All anagrams: " + ok); public static String sort(String s) { char[] a = s.toCharArray(); Arrays.sort(a); return new String(a); } Output : All anagrams: true Why this step matters: - It connects string concepts with DSA-style thinking - Shows movement from basic manipulation → logical validation problems - Feels like the point where strings start behaving like a real problem-solving topic, not just syntax #java #strings #anagram #problemSolving #codingjourney #learninginpublic

🚀 Daily DSA Practice – Day 37 | Tree Depth, Height & Diameter (Java) As part of my ongoing Data Structures & Algorithms preparation, today I focused on tree depth and height–based problems, which rely heavily on DFS recursion and postorder traversal to compute values from bottom to top. 📌 Problems Solved (LeetCode): • 104. Maximum Depth of Binary Tree – Calculated tree height using recursive DFS • 111. Minimum Depth of Binary Tree – Handled edge cases where one child is null • 543. Diameter of Binary Tree – Used postorder traversal to compute the longest path between any two nodes 🎯 Key Learnings: ✔ Difference between depth and height in binary trees ✔ Why postorder traversal is ideal for bottom-up calculations ✔ Managing global/state variables in recursive solutions ✔ Writing clean and efficient DFS-based tree algorithms These problems are frequently asked in coding interviews because they test recursion mastery, edge-case handling, and tree traversal intuition, which are essential for backend and system-level problem solving. #DSA #LeetCode #Java #BinaryTree #DFS #Recursion #TreeHeight #ProblemSolving #InterviewPreparation #BackendDeveloper #SoftwareEngineer

🔥 Day 309 – Daily DSA Challenge! 🔥 Problem: 🔁 Permutations II Given an array nums that may contain duplicate numbers, return all unique permutations in any order. 💡 Key Insights: 🔹 This is a backtracking problem with an extra twist — duplicates. 🔹 Sorting the array upfront is the key to handling duplicates cleanly. 🔹 Use a used[] boolean array to track which elements are already in the current permutation. 🔹 The golden rule to skip duplicates 👇     👉 If the current number is the same as the previous one and the previous one is not used, skip it. 🔹 This ensures we only generate unique permutations. ⚡ Optimized Plan: ✅ Sort the input array ✅ Use backtracking to build permutations ✅ Track used elements with a boolean array ✅ Add permutation to result when its size equals nums.length ✅ Skip duplicates using:     if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; ✅ Backtrack after each recursive call ✅ Time Complexity: O(n! × n) (due to copying permutations) ✅ Space Complexity: O(n) (recursion stack + used array) 💬 Challenge for you: 1️⃣ Why does the condition !used[i - 1] matter for avoiding duplicates? 2️⃣ How would this solution change if all numbers were unique? 3️⃣ Can you generate permutations iteratively instead of using recursion? #DSA #Day309 #LeetCode #Permutations #Backtracking #Recursion #Java #ProblemSolving #KeepCoding #100DaysOfCode

Group Anagrams — 49 🎯 Goal Group strings that are anagrams and return them as a list of groups. Anagram: Strings having the same characters with the same frequency (order does not matter). Core Intuition We need to group items based on a common property. Property here = same character composition Best data structure for grouping by a property → HashMap Approach 1 — Sorting (Brute / Standard) If we sort a string, all anagrams become identical. Example: eat → aet tea → aet ate → aet So we can: - Sort each string - Use the sorted string as the key - Store original strings as values in a HashMap Complexity Let: - N = number of strings - K = average string length Time Complexity: O(N × K log K) (because sorting each string takes K log K) Space Complexity: O(N × K) Worst case: if all strings are different, each gets stored separately in the HashMap. Trade-off Sorting is simple and clean, but: If strings are very large, sorting becomes expensive. Optimized Approach — Frequency Count To avoid sorting cost, we can use character frequency. This works when: - All characters are lowercase (or uppercase) - Fixed alphabet size (26) Idea - Create an array of size 26. - Traverse each string and count character frequency. - Convert this frequency array into a string. - Use that string as the HashMap key. Now: - Building key = O(K) - No sorting needed. Complexity Time Complexity: O(N × K) Space Complexity: O(N × K) Extra space used is constant (26-size array), but we gain better time performance. 🕸Trap Trying to use an array/list directly as a HashMap key. In Java: - Arrays do not implement "equals()" properly for value comparison. ✔ Always convert frequency array to a String before using it as a key. Trigger Whenever you see: Group items based on a property Think: HashMap + Generated Key If I missed anything or if you have a better approach, please feel free to add it in the comments 🙌 #DSA #LeetCode #Java #Algorithms #ProblemSolving #CodingJourney #InterviewPreparation #SoftwareEngineer

Day - 61 Subsets II The problem - Given array that may contain duplicates, return all possible unique subsets. Example : candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6],[1,2,5],[1,7],[2,6]] Brute Force - Generate all combinations iteratively, still exponential, but less elegant than recursion. Approach Used - •) Sort the nums array.nums.lengthcktrack(0, nums, subset, res). •) Base case, if i == nums.length, reached end, add new ArrayList(subset) to res and return. •) Recursive First case, include nums[i], add to subset, recurse with i+1, backtrack (remove). •) Recursive Second case, exclude nums[i], recurse with i+1 (don't add). Complexity - Time - O(2^n), each element include/exclude. Space - O(n), recursion depth. Note - Sort array. After excluding an element, skip all duplicates before next recursion to avoid duplicate subsets. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🚀 DSA Practice – find the first non -repeating character. While solving a string problem related to character frequency, I first thought of using a HashMap. But then I optimized it further by using an array based on ASCII values — which is faster and more memory-efficient. 💡 Optimized Approach (Using ASCII Array) 🔹 Step 1: Use an integer array of size 256 Since characters are stored internally using ASCII values, we can directly use an array where the index represents the character. ```java int[] freq = new int[256]; ``` 🔹 Step 2: Store frequency using ASCII index Traverse the string once and increment the count using the character’s ASCII value. ```java for (char ch : str.toCharArray()) { freq[ch]++; } ``` Here, `ch` automatically converts to its ASCII integer value, making access O(1) without hashing overhead. 🔹 Step 3: Find the required character while preserving order Traverse the string again and check which character has frequency = 1. ```java for (char ch : str.toCharArray()) { if (freq[ch] == 1) { System.out.println("Answer: " + ch); break; } } `` 🧠 Why This is More Optimized Than HashMap ✅ No hashing overhead ✅ Faster lookups (direct index access) ✅ Lower memory usage compared to HashMap objects ✅ Time Complexity: O(n) ✅ Space Complexity: O(1) (fixed array size – 256) This approach shows how understanding how characters are stored internally (ASCII/Unicode) can help write even more efficient code. Small optimizations like this can make a big difference in performance-critical applications. 💯 #DSA #Java #OptimizedCode #ProblemSolving #CodingPractice

Day 20 of DSA Consistency – LeetCode 15 (3Sum) Today I solved the classic 3Sum problem. Problem: Find all unique triplets in an array such that a + b + c = 0. At first glance, brute force looks easy (O(n³)), but that’s useless for interviews. It will timeout. The correct approach is: • Sort the array • Fix one number • Use Two Pointers (2Sum technique) • Skip duplicates carefully This reduces the complexity to O(n²). Key learning: Most “hard” problems are just combinations of simpler patterns. 3Sum = Sorting + Two Pointers + Duplicate handling. Patterns > memorizing solutions. Code (Java): class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < 0) left++; else right--; } } return res; } } Time Complexity: O(n²) Space Complexity: O(1) Consistency matters more than speed. 20 days done. No breaks. #DSA #LeetCode #Java #ProblemSolving #CodingInterview #SoftwareEngineering #100DaysOfCode