Prefix Sum + HashMap for Subarray Sum Equals K Problem

Day 9/30 — DSA Challenge 🚀 Problem: Construct Binary Tree from Preorder and Inorder Traversal Topic: Tree + Recursion + Hashing Difficulty: Medium Approach: Used preorder to identify root node Used inorder to divide left and right subtrees Stored inorder indices in a HashMap for O(1) lookup Recursively built left and right subtrees Mistake / Challenge: Initially struggled to understand how preorder and inorder work together Got confused in managing indices for subtree boundaries Fix: Used a pointer for preorder traversal Used HashMap to quickly find root index in inorder Carefully handled left and right subtree ranges Key Learning: Preorder → gives root Inorder → gives structure (left/right split) Combining both helps reconstruct the tree Time Taken: 1 hour Consistency check ✅ See you on Day 10. GitHub Repo: https://lnkd.in/gHW9vKUf #DSA #LeetCode #Java #Trees #Recursion #LearningInPublic

Day 95 of #365DaysOfLeetCode Challenge Today’s problem: **Path Sum III (LeetCode 437)** This one looks like a typical tree problem… but the optimal solution introduces a powerful concept: **Prefix Sum + HashMap in Trees** 💡 **Core Idea:** Instead of checking every possible path (which would be slow), we track **running sums** as we traverse the tree. 👉 If at any point: `currentSum - targetSum` exists in our map → we’ve found a valid path! 📌 **Approach:** * Use DFS to traverse the tree * Maintain a running `currSum` * Store prefix sums in a HashMap * Check how many times `(currSum - targetSum)` has appeared * Backtrack to maintain correct state ⚡ **Time Complexity:** O(n) ⚡ **Space Complexity:** O(n) **What I learned today:** Prefix Sum isn’t just for arrays — it can be **beautifully extended to trees**. This problem completely changed how I look at tree path problems: 👉 From brute-force traversal → to optimized prefix tracking 💭 **Key takeaway:** When a problem involves “subarray/paths with a given sum,” think: ➡️ Prefix Sum + HashMap #LeetCode #DSA #BinaryTree #PrefixSum #CodingChallenge #ProblemSolving #Java #TechJourney #Consistency

Day 58/100 | #100DaysOfDSA 🔄🔍 Today’s problem: Search in Rotated Sorted Array A twist on Binary Search with a rotated array. Key idea: Even though the array is rotated, one half is always sorted. Approach: • Use binary search • Find mid element • Check which half is sorted (left or right) • Decide if target lies in the sorted half • Narrow the search accordingly Why it works: At every step, we eliminate half of the search space just like standard binary search. Time Complexity: O(log n) Space Complexity: O(1) Big takeaway: Understanding the structure of the problem helps adapt classic algorithms like binary search. Rotation doesn’t break order — it just shifts it. 🔥 Day 58 done. #100DaysOfCode #LeetCode #DSA #Algorithms #BinarySearch #Arrays #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity

𝐃𝐚𝐲 𝟕𝟑 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on detecting duplicates within a given index range. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Contains Duplicate II --- 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 – 𝐇𝐚𝐬𝐡𝐌𝐚𝐩 • Stored each number with its latest index • For every element: • Checked if it already exists in the map • If yes → verified index difference ≤ k • Updated index to keep the most recent occurrence --- 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • Storing indices helps solve range-based problems • HashMap enables O(1) lookup • Updating latest index ensures correctness • Small constraints can change the approach --- 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Time: O(n) • Space: O(n) --- 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Adding constraints doesn’t always make problems harder — it often makes them more interesting to solve. --- 73 days consistent 🚀 On to Day 74. #DSA #Arrays #HashMap #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

Day 10/30 — DSA Challenge 🚀 Problem: Construct Binary Tree from Inorder and Postorder Traversal Topic: Tree + Recursion + Hashing Difficulty: Medium Approach: Used postorder to identify root node (last element) Used inorder to split tree into left and right subtrees Stored inorder indices in a HashMap for fast lookup Built tree recursively (right subtree first, then left) Mistake / Challenge: Initially confused about traversal order Made mistake by building left subtree first instead of right Fix: Understood that postorder processes (Left → Right → Root) So while constructing → build Right first, then Left Key Learning: Preorder → Root first Postorder → Root last Always align recursion order with traversal type Time Taken: 50 minutes Consistency check ✅ See you on Day 11. GitHub Repo: https://lnkd.in/gHW9vKUf #DSA #LeetCode #Java #Trees #Recursion #LearningInPublic

🚀 Day 7: Cracking the "Two Pointer" Pattern 🚀 Today, I dived into LeetCode 167 (Two Sum II) to master the Two Pointer technique! While the standard Two Sum problem is often solved with a Hash Map, a Sorted Array gives us a secret advantage. By using two pointers—one at the start and one at the end—we can find the target sum in $O(n)$ time and $O(1)$ space. No extra memory needed! 🧠 💡 Key Takeaway: The magic happens in the movement: Sum < Target? Move the left pointer to grab a larger value. Sum > Target? Move the right pointer to grab a smaller value. Pro Tip: Always watch out for 1-indexed requirements! Adding that +1 to your return indices is the difference between a "Wrong Answer" and "Accepted." ✅ 🛠️ The Logic (Java): Java while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) return new int[]{left + 1, right + 1}; else if (sum < target) left++; else right--; } One week down, more patterns to go! Following the roadmap from the "25 DSA Patterns" series. 📈 #DSA #LeetCode #CodingChallenge #Java #TwoPointers #SoftwareEngineering #Consistency

Day 58/75 — Contiguous Array Today’s problem was about finding the maximum length of a subarray with equal number of 0s and 1s. Approach: • Convert 0 → -1 to transform the problem into finding subarray with sum = 0 • Use HashMap to store first occurrence of prefix sum • If same sum appears again → subarray between them has equal 0s and 1s Key logic: if (nums[i] == 0) sum -= 1; else sum += 1; if (map.containsKey(sum)) { maxLen = Math.max(maxLen, i - map.get(sum)); } else { map.put(sum, i); } Time Complexity: O(n) Space Complexity: O(n) A clever problem that builds strong intuition for prefix sum + hashing. 58/75 🚀 #Day58 #DSA #PrefixSum #HashMap #Java #Algorithms #LeetCode

----Continuing my DSA journey---- * Problem: Parse Lisp Expression (736) * Approach: I solved this using recursion + hashmap (scope handling). I parsed the expression and evaluated it based on three cases: • add → evaluate both expressions and sum • mult → evaluate both expressions and multiply • let → assign variables and evaluate in scoped context I used a HashMap to maintain variable values and passed copies to handle nested scopes correctly. * Key Insight: The tricky part was managing variable scope in nested expressions. Each "let" creates a new scope, and variables must be resolved from inner to outer scope. * What I Learned: This problem improved my understanding of parsing complex expressions and scope management. #LeetCode #DSA #Java #Recursion #HashMap #ProblemSolving

🚀 DSA Preparation 💪 Solved an interesting Array + HashMap problem involving number reversal. Focused on identifying mirror pairs efficiently , minimizing index distance🔥 Great practice for combining hashing with logic building 🚀 🧠 Problem 🔎 Minimum Distance Between Mirror Pairs Given an array nums, a mirror pair is defined as indices (i, j) such that: 👉 i < j 👉 reverse(nums[i]) == nums[j] Return the minimum absolute distance |i - j| among all mirror pairs. 👉 If no such pair exists, return -1. Example Input: nums = [12,21,45,33,54] Output: 1 Input: nums = [120,21] Output: 1 Input: nums = [21,120] Output: -1 ⚡ Key Learning 📌 Use HashMap to store reversed values and their indices 📌 Check for matches while traversing the array 📌 Efficiently minimize distance during traversal 📌 Time Complexity: O(n * d) → n elements, d digits for reversal 📌 Space Complexity: O(n) → storing elements in map Improving DSA with smart hashing techniques 🚀 #DSA #LeetCode #HashMap #Arrays #Java #ProblemSolving #Consistency

**Day 113 of #365DaysOfLeetCode Challenge** Today’s problem: **Contiguous Array (LeetCode 525)** We need to find the **longest contiguous subarray** with an equal number of `0`s and `1`s. At first glance, it feels like a sliding window problem… but the real solution is: 👉 **Prefix Sum + HashMap** 💡 **Core Idea:** Convert: * `0 → -1` * `1 → +1` Now the problem becomes: 👉 Find the longest subarray whose sum = `0` Because equal number of `0`s and `1`s cancel each other out. 📌 **Approach:** 1️⃣ Maintain running sum 2️⃣ Store first occurrence of each sum in HashMap 3️⃣ If same sum appears again: * Subarray between those indices has sum `0` 4️⃣ Maximize length 💡 Why store first occurrence only? Because earliest index gives the **longest possible subarray** ⚡ **Time Complexity:** O(n) ⚡ **Space Complexity:** O(n) **What I learned today:** Many binary array problems can be transformed into prefix sum problems by clever value mapping. 💭 **Key Takeaway:** When asked: * Equal 0s and 1s * Balanced values * Longest valid subarray Think: 👉 Prefix Sum 👉 HashMap 👉 First occurrence trick #LeetCode #DSA #PrefixSum #HashMap #Arrays #CodingChallenge #ProblemSolving #Java #TechJourney #Consistency