Optimize O(n²) to O(n) with Simple Trick

📘 DSA Journey — Day 10 Today’s focus: Prefix Sum and Sliding Window techniques. Problems solved: • Binary Subarrays With Sum (LeetCode 930) • Maximum Sum of Distinct Subarrays With Length K (LeetCode 2461) Concepts used: • Prefix Sum with HashMap • Sliding Window technique • Frequency tracking for distinct elements Key takeaway: In Binary Subarrays With Sum, the goal is to count the number of subarrays whose sum equals a given target. This can be solved efficiently using the prefix sum technique combined with a HashMap. As we iterate through the array, we keep track of the running sum and check how many times (currentSum - goal) has appeared before. This allows us to count valid subarrays in O(n) time. In Maximum Sum of Distinct Subarrays With Length K, a fixed-size sliding window is used. While moving the window across the array, we maintain a frequency map to ensure all elements in the window are distinct. If the window contains exactly k unique elements, we update the maximum sum. These problems highlight how recognizing the right pattern—prefix sums for counting subarrays and sliding windows for fixed-length constraints—can significantly reduce brute-force complexity. Continuing to strengthen pattern recognition and consistency in solving DSA problems. #DSA #Java #LeetCode #CodingJourney

🚀 DSA Practice – Longest Subarray with Sum = K (Positive Numbers) Today I practiced a classic Sliding Window / Two Pointer problem. Problem: Find the longest subarray whose sum equals K, when the array contains only positive numbers. 💡 Key Idea: * Since all numbers are positive, we can use the sliding window technique: Expand the window by moving the right pointer. * If the sum becomes greater than k, shrink the window using the left pointer. Whenever sum == k, update the maximum length. ⚡ Time Complexity: O(n) ⚡ Space Complexity: O(1) Example: arr = [1, 2, 3, 1, 1, 1, 1, 4, 2, 3] k = 3 Longest subarray: [1, 1, 1] Length = 3 This problem is a great example of how understanding constraints (positive numbers) allows us to replace complex approaches like HashMap + Prefix Sum with a simpler and more efficient Sliding Window technique. #DSA #Algorithms #Java #SlidingWindow #LeetCode #SoftwareEngineering

Day 33 of Daily DSA 🚀 Solved LeetCode 58: Length of Last Word ✅ Problem: Given a string s, return the length of the last word (a sequence of non-space characters). Approach: First, trim() the string to remove trailing spaces Traverse the string from the end Count characters until a space is encountered 💡 Key Insight: Instead of splitting the string (which uses extra space), we can simply iterate backwards for an efficient solution. ⏱ Complexity: • Time: O(n) • Space: O(1) 📊 LeetCode Stats: • Runtime: 0 ms (Beats 100%) ⚡ • Memory: 43.17 MB A simple yet important problem to strengthen string traversal techniques. #DSA #LeetCode #Java #Strings #ProblemSolving #CodingJourney #Consistency

🚀 Day 62/365 — DSA Challenge Today's problem was simple in statement... but powerful in concept. Solved: 242. Valid Anagram The task: Given two strings s and t, return true if t is an anagram of s. An anagram means: Same characters. Same frequency. Different order allowed. 💡 My Approach Instead of sorting both strings, I used a frequency counter array of size 26. Steps: • If lengths differ -> return false • Increment count for each character in s • Decrement count for each character in t • If all values return to zero -> it's an anagram ⚡ Why this approach? Sorting -> O(n log n) Frequency count -> O(n) Time Complexity: O(n) Space Complexity: O(1) (fixed 26 letters) What I learned today Sometimes the optimal solution is just about counting correctly. Not every string problem needs sorting. Clean. Efficient. Intentional. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #LearningInPublic #Consistency #ProblemSolving

🚀 Day 86 of My DSA Journey | Subsets – Recursion ➡️ Bit Manipulation 💡 Yesterday, I solved the Subsets problem (LeetCode 78) using recursion (backtracking). Today, I challenged myself to solve the same problem using a different approach — Bit Manipulation 🔥 🔹 What changed? Instead of recursion, I used bit masking to generate all subsets. Every number from 0 to 2^n - 1 represents a subset in binary form. 👉 Core idea: (i & (1 << j)) != 0 This checks whether the j-th element should be included in the subset. 📌 Example: nums = [1,2,3] i = 5 → binary (101) Subset → [1,3] ⚡ Key Learning: One problem can have multiple approaches Recursion = intuitive Bit manipulation = optimized & clever Strengthened my understanding of binary concepts ⏱️ Time Complexity: O(n * 2^n) 📦 Space Complexity: O(2^n) Consistency is the key — learning, applying, and improving every single day 💯 #Day87 #DSA #Java #BitManipulation #Recursion #LeetCode #CodingJourney #PlacementPreparation

Day 82/100 – LeetCode Challenge ✅ Problem: #43 Multiply Strings Difficulty: Medium Language: Java Approach: Manual Multiplication with Result Array Time Complexity: O(n × m) Space Complexity: O(n + m) Key Insight: Multiply digits from right to left (least significant first). Store intermediate results in array where index i + j + 1 holds current digit. Handle carry by adding to previous index. Solution Brief: Edge case: if either number is "0", return "0". Created result array of size n1 + n2 (max possible digits). Nested loops multiply each digit of num1 with each digit of num2. Accumulated results with proper carry handling. Built final string skipping leading zeros. #LeetCode #Day82 #100DaysOfCode #Math #String #Java #Algorithm #CodingChallenge #ProblemSolving #MultiplyStrings #MediumProblem #Multiplication #Array #DSA

🎯 Day 67 of #100DaysOfCode 📌 Problem: Combination Sum Today's challenge was all about finding all unique combinations of candidates where the chosen numbers sum to a given target. The same number can be used unlimited times, and combinations must be unique. 🧠 Approach: Used dynamic programming with a 3D list structure dp[t] stores all combinations that sum to target t Iterated through candidates and built combinations from smaller sums Extended each valid combination by adding current candidate 📊 Stats: ✅ 160/160 test cases passed ⚡ Runtime: 5 ms | Beats 10.10% 💾 Memory: 46.71 MB | Beats 5.88% 📝 Takeaway: This problem highlighted the trade-off between intuitive DP solutions and optimization. While the approach works, there's room for improvement in both runtime and memory efficiency. Backtracking might be a more elegant solution here! 🔗 Problem: Combination Sum 🏷️ #LeetCode #CodingChallenge #Java #DynamicProgramming #Backtracking #Algorithms #TechJourney #ProblemSolving

Day 22 of Daily DSA 🚀 Solved LeetCode 66: Plus One ✅ Approach: Treat the array as a number and simulate addition from the last digit: • If the last digit is not 9, increment and return • Handle carry by setting 9 → 0 and moving left • If all digits are 9, create a new array with leading 1 This avoids converting the array into an integer and handles large numbers safely. ⏱ Complexity: • Time: O(n) • Space: O(1) (extra array only when overflow happens) 📊 LeetCode Stats: • Runtime: 0 ms (Beats 100%) ⚡ • Memory: 43.58 MB (Beats 38.49%) A simple problem that tests edge-case thinking 💡 #DSA #LeetCode #Java #ProblemSolving #DailyCoding #Consistency

🚀 Day 121/500 – LeetCode DSA Challenge Today I solved three problems focused on strings and number manipulation. ✅ Reverse String II – Reversed every k characters using two pointers. TC: O(n) | SC: O(n) ✅ Reverse Only Letters – Applied two-pointer approach while skipping non-letter characters. TC: O(n) | SC: O(n) ✅ Digitorial Permutation – Calculated factorial sum of digits and checked digit frequency match. TC: O(d) | SC: O(1) 💡 Key Learning: Two-pointer techniques simplify many string problems, and digit-based problems often rely on frequency counting and math logic. 👉 Day 121/500 #DSA #Java #500DaysChallenge #ProblemSolving #CodingJourney