Counting Subarrays with Sum K using Prefix Sum and Hashmap

Day 11 of being consistent with DSA Today’s problem: 𝗧𝗼𝗽 𝗞 𝗙𝗿𝗲𝗾𝘂𝗲𝗻𝘁 𝗘𝗹𝗲𝗺𝗲𝗻𝘁𝘀 The goal is to return the k most frequent elements from an array. I first solved it using a hashmap + heap, which works with 𝗢(𝗻 𝗹𝗼𝗴 𝗻) 𝘁𝗶𝗺𝗲 𝗰𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆. Then I explored the optimal approach using bucket sort, where elements are grouped by their frequency. 𝗛𝗲𝗮𝗽 -> 𝗢(𝗻 𝗹𝗼𝗴 𝗻) 𝘁𝗶𝗺𝗲, 𝗢(𝗻) 𝘀𝗽𝗮𝗰𝗲 𝗕𝘂𝗰𝗸𝗲𝘁 𝘀𝗼𝗿𝘁 -> 𝗢(𝗻) 𝘁𝗶𝗺𝗲, 𝗢(𝗻) 𝘀𝗽𝗮𝗰𝗲 One thing I learned:- Sometimes grouping data based on properties (like frequency) can be more efficient than traditional sorting. Link:-https://lnkd.in/edWTqBaa GitHub Link:- https://lnkd.in/eEGnvF3h #SoftwareEngineering #DSA #ProblemSolving #LearningInPublic #NeetCode250

🚀 Day 45 of My DSA Journey 🔍 LeetCode Problem #454 – 4Sum II Today’s problem was a great example of optimizing brute force using hashing. Instead of checking all possible quadruplets (which would be inefficient), the idea is to break the problem into two parts and store intermediate sums. 💡 Key Learning: By storing sums of two arrays in a hashmap, we can efficiently find complementary pairs from the other two arrays. ⚡ Insight: This reduces the time complexity significantly from O(n⁴) to O(n²), making the solution practical. 📌 Takeaway: Breaking complex problems into smaller subproblems and using hashing can lead to major performance improvements. Consistency continues — Day 45 💪 #Day45 #LeetCode #DSA #HashMap #ProblemSolving #CodingJourney #Consistency

Day 37 Today I solved: Subarray Sum Equals K (LeetCode 560) 💡 Problem: Given an array and an integer k, find the total number of subarrays whose sum equals k. 💡 My Approach: I used Prefix Sum + HashMap for an optimal solution: 1️⃣ Compute running prefix sum while traversing the array 2️⃣ Use a HashMap to store frequency of prefix sums 3️⃣ At each index, check: 👉 If (currentSum - k) exists in map → we found subarrays 4️⃣ Add its frequency to the count 5️⃣ Update the map with current prefix sum 💡 Key Insight: If prefixSum[j] - prefixSum[i] = k 👉 Then prefixSum[i] = prefixSum[j] - k So instead of checking all subarrays ❌ We use previously seen sums to get result in O(n) ✅ ⚡ Complexity: Time: O(n) Space: O(n) 🔥 Takeaway: Prefix Sum + HashMap is a powerful combo for subarray problems 🚀 #LeetCode #DSA #CodingJourney #LearnInPublic

🚀 Solved a challenging Binary Tree problem – FindElements (Recover Contaminated Tree) on LeetCode! Today I worked on an interesting problem where an entire binary tree was “contaminated” (all values set to -1), and the goal was to reconstruct the original tree structure using given rules and efficiently support search queries. 🔍 Key Learnings & Approach: Recovered the tree using DFS by applying: Left child → 2*x + 1 Right child → 2*x + 2 Designed a recursive solution to restore values starting from root = 0 Implemented a traversal-based search to verify whether a target exists in the tree ⚡ Performance: ✅ All test cases passed (34/34) ⏱ Runtime: 304 ms 💾 Memory Usage: Optimized (better than ~91% submissions) 💡 What made it interesting? This problem is a great example of: Tree reconstruction logic DFS traversal usage Understanding implicit tree properties 📌 Next Improvement Plan: Planning to optimize the find() operation from O(n) to O(1) using hashing (unordered_set) for faster lookups. Consistency in solving DSA problems is really paying off. On to the next challenge! 💪 #DataStructures #Algorithms #BinaryTree #LeetCode #CodingJourney #Cplusplus #DSA #ProblemSolving

Day 167/365 – DSA Challenge 🚀 Solved Construct Binary Tree from Preorder and Inorder Traversal on LeetCode today. 🔹 Problem: Given two arrays — preorder and inorder traversal of a binary tree — construct the original tree. 🔹 Approach Used: Recursion + HashMap Steps followed: 1️⃣ First element of preorder → root 2️⃣ Find root in inorder using a hashmap (for O(1) lookup) 3️⃣ Split inorder into: Left subtree Right subtree 4️⃣ Recursively build left and right subtrees 🔹 Key Idea: Preorder gives the root, inorder gives the structure 🔹 Time Complexity: O(n) 🔹 Space Complexity: O(n) 💻 Language: C++ This is a classic problem that tests your understanding of tree reconstruction + recursion depth control. #Day167 #365DaysOfCode #DSA #LeetCode #BinaryTree #Recursion #HashMap #CodingChallenge #Cpp

Day 88 / 100 – 100 Days of LeetCode Challenge 🚀 Problem: Strictly Palindromic Number (LeetCode #2396) Today I solved the Strictly Palindromic Number problem. The task is to determine whether a given integer n is strictly palindromic in all bases from 2 to n−2. Approach Instead of converting the number into every base and checking manually, I analyzed the mathematical property of the problem. It turns out that for any integer n ≥ 4, the number cannot be strictly palindromic in all required bases. Therefore, the result will always be false. Steps followed: • Understand the definition of strictly palindromic numbers • Analyze the mathematical behavior of numbers in different bases • Apply the observation that such numbers do not exist for n ≥ 4 • Directly return false This approach avoids unnecessary computation and relies on mathematical reasoning. Complexity Time Complexity: O(1) Space Complexity: O(1) Result ✔ Accepted ⚡ Constant time solution 🧠 Mathematical insight-based optimization A good problem to strengthen understanding of mathematical reasoning and problem analysis. #100DaysOfCode #100DaysLeetCodeChallenge #LeetCode #DSA #CPlusPlus #ProblemSolving #Math #Logic

Day 28 of being consistent with DSA Today's problem: 𝗦𝗲𝗮𝗿𝗰𝗵 𝗜𝗻𝘀𝗲𝗿𝘁 𝗣𝗼𝘀𝗶𝘁𝗶𝗼𝗻 The goal is to find the index of a target in a sorted array, or the position where it should be inserted if not found. I solved it using binary search, narrowing down the search space by comparing the target with the middle element. One interesting part:- Even when the target is not present, the final value of the left pointer gives the correct insertion position. One thing I learned:- Binary search is not just for finding elements, it can also be used to determine positions efficiently. 𝗧𝗶𝗺𝗲 𝗰𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 -> 𝗢(𝗹𝗼𝗴 𝗻) 𝗦𝗽𝗮𝗰𝗲 𝗰𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 -> 𝗢(𝟭) NeetCode Link:- https://lnkd.in/eHAz6q5Y GitHub:- https://lnkd.in/eUm9nw5i #SoftwareEngineering #DSA #ProblemSolving #LearningInPublic #NeetCode250

🚀 Day 54 of My DSA Journey Solved LeetCode Problem #275 – H-Index II Today’s problem focused on Binary Search and understanding how sorted data can help optimize solutions from linear time to logarithmic time. 🔍 Problem Insight: Given a sorted citations array, the goal was to find the maximum h such that at least h papers have h or more citations. 💡 Key Learning: Instead of checking every possible value, Binary Search helps efficiently identify the correct h-index in O(log n) time. ⚡ Main Observation: At any index i, the number of papers with at least citations[i] citations is n - i. This relationship makes Binary Search possible. 📌 Takeaway: Whenever the input is sorted, always think about Binary Search before using brute force. It can drastically improve performance. Consistency continues 💪 #Day54 #LeetCode #DSA #BinarySearch #ProblemSolving #CodingJourney #Cpp

From solving DSA problems → to building real systems ⚡ Made a CLI-based Cache Simulator that brings LRU & LFU algorithms to life — not just theory, but actual execution. 🔧 What’s under the hood: • Algorithms implemented from scratch. • Java-powered backend with clean operations using HashMap + Doubly Linked List • Modular design → easy to plug in new cache strategies 💡 Why this matters: • Understand how real-world systems optimize memory • Simulate cache behavior for systems design & interviews • Bridge the gap between DSA concepts and practical engineering Learning isn’t just solving problems… it’s engineering them. #DataStructures #Java #SystemDesign #Caching #LRU #LFU #BackendDevelopment #DSA #Projects #SoftwareEngineering

Day 3: LeetCode – 74. Search a 2D Matrix Today I solved a problem that looks like a 2D matrix question but is actually a binary search problem in disguise. Key Insight: Although the input is a matrix, the constraints ensure it behaves like a single sorted array. That allows us to apply binary search across the entire matrix in O(log(m × n)) time. My Approach: • Treated the matrix as a single sorted list • Applied binary search on the range [0 … m×n − 1] • Converted the mid index back to matrix coordinates using: – row = mid / n – col = mid % n • Compared the value at that position with the target and adjusted the search range Takeaway: A shift in perspective can simplify seemingly complex problems. Recognizing hidden patterns is as important as knowing algorithms. Day 3 completed. #DSA #LeetCode #BinarySearch #ProblemSolving