Solved LeetCode 198 House Robber with DP and Space Optimization

✅ Day 54 of LeetCode Medium/Hard Edition Today’s challenge was “Maximum Sum of 3 Non-Overlapping Subarrays” — a brilliant mix of prefix sums, dynamic programming, and optimization logic 🎯 📦 Problem: You’re given an integer array nums and a fixed length k. You must select three non-overlapping subarrays of length k such that their total sum is maximized, and return the starting indices of these subarrays. 🔗 Problem Link: https://lnkd.in/g76A35cZ ✅ My Submission: https://lnkd.in/gB-nDGqu 💡 Thought Process: First, precompute the sum of every k-length window using prefix sums. Then, maintain two helper arrays: left[i] → index of best (maximum sum) window from the left up to i right[i] → index of best window from the right starting at i For each possible middle window, combine it with the best left and right windows to form the maximum total sum. Track and update the maximum configuration across all possible middle positions. ⏱ Complexity: Time: O(n) Space: O(n) 🔥 Key Takeaway: This problem highlights the power of prefix sums and precomputation — turning what could be a brute-force O(n³) nightmare into a sleek, linear-time solution. Sometimes, the smartest code isn’t recursive… it’s prepared! 💪 #LeetCodeMediumHardEdition #100DaysChallenge #DynamicProgramming #PrefixSum #ProblemSolving #Java #CodingJourney

✅ Day 63 of LeetCode Medium/Hard Edition Today’s challenge was “Count Vowel Permutation” — a fascinating Dynamic Programming problem that explores state transitions across vowels 🔤✨ 📦 Problem: Given an integer n, we need to count how many strings of length n can be formed using only vowels (a, e, i, o, u), following these adjacency rules: 'a' → may only be followed by 'e' 'e' → may only be followed by 'a' or 'i' 'i' → may not be followed by another 'i' 'o' → may only be followed by 'i' or 'u' 'u' → may only be followed by 'a' Since the result can be very large, return it modulo 10⁹ + 7. 🔗 Problem Link: https://lnkd.in/gW7GMVUh ✅ My Submission: https://lnkd.in/g8t7mddT 💡 Thought Process: The problem models a finite-state machine, where each vowel transitions only to specific next vowels. We can use Dynamic Programming with memoization to count all possible sequences of length n, given a last-used vowel. Steps: 1️⃣ Define a recursive DP: dp[n][vowel] = number of valid strings of length n ending with that vowel. 2️⃣ Use transition rules to decide valid next vowels for each step. 3️⃣ Memoize results to avoid recomputation and take modulo 10⁹ + 7. 4️⃣ The total number of strings = sum of all dp[n][vowel] values. ⚙️ Complexity: ⏱ Time: O(n × 5) — one state per vowel per length 💾 Space: O(n × 5) — or O(1) if optimized iteratively #LeetCodeMediumHardEdition #100DaysChallenge #DynamicProgramming #ProblemSolving #Java #CodingChallenge #LeetCodeDay63

✅ Day 74 of LeetCode Medium/Hard Edition Today’s challenge was “Minimum Falling Path Sum II” — a dynamic programming problem that blends recursion, memoization, and row-wise optimization ⚡💡 📦 Problem: You're given an n × n integer matrix. A falling path selects exactly one element from each row, and the restriction is: No two consecutive elements may be chosen from the same column. Return the minimum possible sum of such a falling path. 🔗 Problem Link: https://lnkd.in/gbKyfbqs ✅ My Submission: https://lnkd.in/gtg_qzW8 💡 Thought Process: This problem extends the classic minimum falling path by enforcing a non-zero shift, meaning the chosen column must change at every row. To solve this efficiently, we can use Dynamic Programming with memoization, where: dp[r][c] represents the minimum falling path sum starting from grid[r][c]. From each cell, we explore all columns in the next row except the same one. Memoization prevents recomputing overlapping subproblems. A further optimization uses the idea of tracking: the minimum and second minimum values from the previous row So when transitioning: If the current column ≠ min-index → pick the global minimum Else → pick the second minimum This eliminates the O(n³) brute force and reduces complexity to O(n²). 🎯 Base Cases: The last row directly contributes its cell value: dp[n-1][c] = grid[n-1][c] Transition occurs upward row by row. Memoized states avoid repeated work. ⚙️ Complexity: ⏱ Time: O(n²) with optimized DP 💾 Space: O(n²) with memo / O(n) with rolling array 🧩 Key Learnings: Strengthened understanding of state transitions with constraints. Practiced converting a brute DFS idea into an efficient DP + memo solution. Learned how tracking min & second-min values avoids nested loops. Solidified recursion-to-DP thinking for grid-based problems. #LeetCodeMediumHardEdition #100DaysChallenge #DynamicProgramming #Java #DSA #ProblemSolving #LearnEveryday

💡 LeetCode 3467 – Transform Array 💡 Today, I solved LeetCode Problem #3467: Transform Array, which focuses on array manipulation and the use of conditional logic in Java — a neat problem that strengthens core programming fundamentals. ⚙️ 🧩 Problem Overview: You’re given an integer array nums. Your task is to: Replace even numbers with 0 Replace odd numbers with 1 Then, sort the transformed array in ascending order. 👉 Example: Input → nums = [4, 7, 2, 9] Output → [0, 0, 1, 1] 💡 Approach: 1️⃣ Iterate through the array. 2️⃣ Use a ternary operator to transform each element (even → 0, odd → 1). 3️⃣ Sort the array to arrange all zeros before ones. ⚙️ Complexity Analysis: ✅ Time Complexity: O(n log n) — due to sorting. ✅ Space Complexity: O(1) — in-place transformation. ✨ Key Takeaways: Practiced logical thinking and ternary operations in Java. Strengthened understanding of array transformations and sorting. Reinforced the value of writing clean, concise, and efficient code. 🌱 Reflection: Even simple transformation problems like this one sharpen the habit of thinking algorithmically. Consistency in small challenges leads to big growth in problem-solving skills. 🚀 #LeetCode #3467 #Java #ArrayManipulation #LogicBuilding #ProblemSolving #CodingJourney #DSA #CleanCode #ConsistencyIsKey

✨ Just Implemented LeetCode challenges — “Minimum Window Substring” using Java! This problem truly sharpened my understanding of the Sliding Window technique and taught me how efficient algorithms depend on balancing two moving pointers 🧠💻   Key Steps: Initialization: Create a frequency map (need) for characters in T. Initialize a counter (required) with T's length.      2.  Expansion (Right Pointer): The right pointer expands the window one character at a time.    3.Contraction (Left Pointer): Once required is 0 (a valid window is found), the inner while loop starts contracting the window from the left.    4. Result: After the entire string $S$ is traversed, return the minimum window substring found  ⚙️ Time Complexity: O(n) — Each character is processed at most twice (once by right and once by left). 🧠 Space Complexity: O(1) — Constant space, since the frequency array size is fixed (128 ASCII characters).   🔑 Takeaway: Efficient coding isn’t just about writing code that works — it’s about writing code that adapts smartly to changing conditions. 🖼️ Caption for Code Image “Sliding windows, shifting focus — finding clarity through logic 🪟💡” #LeetCode #Java #CodingChallenge #ProblemSolving #DataStructures #Algorithms #LearningJourney #SoftwareEngineering #WomenInTech

💻 Day 69 of #LeetCode100DaysChallenge Solved LeetCode 264: Ugly Number II a dynamic programming problem that improves sequence generation and pointer-based optimization skills. 🧩 Problem: An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the n-th ugly number. 💡 Approach — Dynamic Programming with Three Pointers: 1️⃣ Maintain an array dp where dp[i] stores the i-th ugly number. 2️⃣ Use three pointers p2, p3, and p5 to track multiples of 2, 3, and 5 respectively. 3️⃣ At each step, choose the smallest of dp[p2]*2, dp[p3]*3, and dp[p5]*5 as the next ugly number. 4️⃣ Increment the corresponding pointer(s) to avoid duplicates. 5️⃣ Continue until the nth ugly number is found. ⚙️ Complexity: Time: O(N) — one pass to generate all ugly numbers Space: O(N) — for storing the sequence ✨ Key Takeaways: ✅ Strengthened understanding of pointer-based DP techniques. ✅ Learned how to efficiently generate sorted multiplicative sequences. ✅ Practiced optimization over brute-force factor checking. #LeetCode #100DaysOfCode #Java #DynamicProgramming #TwoPointers #Math #DSA #ProblemSolving #CodingJourney #WomenInTech

🚀 Day 412 of #500DaysOfCode 🔹 LeetCode 474: Ones and Zeroes Difficulty: Medium | Topic: Dynamic Programming Today’s problem was all about balancing limits and maximizing choices — a classic 0/1 Knapsack twist! 🎒 🧩 Problem Summary: Given a list of binary strings and two integers m and n, find the largest subset of strings such that the total number of 0s ≤ m and the total number of 1s ≤ n. Example: Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 Output: 4 Explanation: Subset = {"10","0001","1","0"} ⚙️ Key Idea: Think of it like a two-dimensional knapsack problem: Each string "costs" a certain number of 0s and 1s. You have two limits — m zeros and n ones. Goal → pick the maximum number of strings without exceeding limits. We use a 2D DP table where: dp[i][j] = max number of strings we can form with i zeros and j ones. Update rule: 💡 Learning: This problem beautifully shows how Dynamic Programming can handle problems with multiple constraints. Just like in life — when you have limited time and energy, plan your choices smartly to maximize growth 🔥 💻 #DynamicProgramming #LeetCode #CodingChallenge #Java #ProblemSolving #CodeNewbie #100DaysOfCode #500DaysOfCode #LearningEveryday

🌟 Day 81 of #100DaysOfCoding 🌟 🔹 Problem: 1186. Maximum Subarray Sum with One Deletion 🔹 Platform: LeetCode 🔹 Language: Java 💡 Concept: This problem is an advanced variation of Kadane’s Algorithm. The goal is to find the maximum subarray sum where we are allowed to delete at most one element. To solve this, I used Dynamic Programming with two arrays: noDelete[i] → max subarray sum ending at index i without deleting any element. oneDelete[i] → max subarray sum ending at index i with one deletion allowed. The key idea is to track both possibilities at each step to ensure we consider both — keeping or deleting an element — while maximizing the result. 🧠 Fixed Error: Initially, I faced an ArrayIndexOutOfBoundsException because I started the loop from i = 0. After adjusting the loop to start from i = 1, the issue was resolved successfully. ✨ Learning: Always check loop boundaries carefully in DP problems. Maintaining two states helps handle “delete one element” type conditions efficiently. Small indexing mistakes can lead to runtime errors — debugging them strengthens logical precision. #Day81 #LeetCode #DynamicProgramming #KadaneAlgorithm #100DaysOfCode #CodingChallenge #Java #ProblemSolving

💡 LeetCode 1897 – Redistribute Characters to Make All Strings Equal 💡 Today, I solved LeetCode Problem #1897, a neat string frequency problem that tests your understanding of counting characters and modular arithmetic — a perfect exercise for logical reasoning and precision in coding. ⚙️📊 🧩 Problem Overview: You’re given an array of strings words. You can rearrange the characters of the strings however you like. Your task is to check if it’s possible to make all strings equal after redistributing the characters. 👉 Example: Input → ["abc","aabc","bc"] Output → true 💡 Approach: 1️⃣ Create a frequency array of size 26 (for each lowercase English letter). 2️⃣ Count how many times each character appears across all strings. 3️⃣ For all characters, check if their frequency is divisible by the number of words — ensuring equal distribution. 4️⃣ If all checks pass, return true; otherwise, return false. ⚙️ Complexity Analysis: ✅ Time Complexity: O(n * m) — where n is the number of words and m is the average length of each word. ✅ Space Complexity: O(1) — Only a fixed 26-element array is used. ✨ Key Takeaways: Strengthened understanding of frequency counting and modular logic. Reinforced clean looping structures and optimized space usage. Showed how simple math concepts like divisibility can simplify logic. 🌱 Reflection: This problem is a reminder that clean, logical solutions often come from understanding patterns rather than brute-forcing. Paying attention to problem constraints leads to more elegant, scalable code. 🚀 #LeetCode #1897 #Java #StringManipulation #FrequencyCounting #ProblemSolving #AlgorithmicThinking #CleanCode #DSA #CodingJourney #ConsistencyIsKey

🚀 Day 47 of My LeetCode Journey 🚀 Problem: Sum of Square Numbers Topic: Math / Two Pointers 🧠 Approach: To check if a number c can be expressed as the sum of squares of two integers (a² + b² = c), we use the two-pointer technique: Start a = 0 and b = √c Calculate sum = a² + b² If sum == c → ✅ return true If sum < c → increase a If sum > c → decrease b Repeat until a <= b. ⏱️ Complexity: Time: O(√c) Space: O(1) This problem beautifully combines mathematical logic with an efficient two-pointer approach — clean and elegant! 💡 #100DaysOfCode #LeetCode #Java #CodingChallenge #ProblemSolving #DSA