House Robber Problem Solved with Dynamic Programming in Java

🚀 Daily DSA Practice – Day 57 | Dynamic Programming – Best Time to Buy and Sell Stock (Java) Continuing my DSA journey, today I worked on a classic problem that focuses on maximizing profit from stock prices using a single transaction. 📌 Problem Solved (LeetCode): 121. Best Time to Buy and Sell Stock (Easy) 🎯 Concept: Dynamic Programming / Greedy Optimization 🧠 Problem Idea: Given an array where each element represents the stock price on a given day, determine the maximum profit that can be achieved by buying once and selling once. The key idea is to keep track of: Minimum price seen so far Maximum profit achievable Logic minPrice = min(minPrice, price) profit = max(profit, price - minPrice) 🔍 What I Practiced: ✔ Tracking minimum value while traversing array ✔ Calculating maximum profit efficiently in O(n) ✔ Strengthening greedy + DP optimization thinking ✔ Understanding the foundation of stock trading DP problems This problem is the starting point for more complex stock DP problems like multiple transactions, cooldown periods, and transaction fees. #DSA #LeetCode #DynamicProgramming #Java #ProblemSolving #InterviewPreparation #Consistency #StockProblems

🚀 Daily DSA Practice – Day 58 | Dynamic Programming – Best Time to Buy and Sell Stock II (Java) Continuing my DSA journey, today I solved an extension of the stock trading problem where multiple transactions are allowed. 📌 Problem Solved (LeetCode): 122. Best Time to Buy and Sell Stock II (Medium) 🎯 Concept: Greedy + Dynamic Programming 🧠 Problem Idea: Unlike the previous stock problem where only one transaction was allowed, here we can perform multiple buy-sell transactions. The key idea is to capture every profitable price difference between consecutive days. Logic if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]; This means we buy at the previous day and sell today whenever there is profit. 🔍 What I Practiced: ✔ Understanding multiple transaction stock problems ✔ Applying greedy optimization techniques ✔ Improving array traversal efficiency ✔ Strengthening the foundation for advanced stock DP problems This problem is an important step toward more complex stock trading problems such as: • Stock with Cooldown • Stock with Transaction Fee • Stock with Limited Transactions #DSA #LeetCode #DynamicProgramming #Java #ProblemSolving #InterviewPreparation #Consistency #StockProblems

🚀 Daily DSA Practice – Day 59 | Dynamic Programming – Best Time to Buy and Sell Stock with Cooldown (Java) Continuing my DSA journey, today I solved a more advanced variation of the stock trading problem where an additional constraint is introduced. 📌 Problem Solved (LeetCode): 309. Best Time to Buy and Sell Stock with Cooldown (Medium) 🎯 Concept: Dynamic Programming with State Transitions 🧠 Problem Idea: You can buy and sell stocks multiple times, but after selling a stock, you must wait one day (cooldown) before buying again. To solve this, we track three possible states: • Buy State → Maximum profit when holding a stock • Sell State → Profit after selling the stock • Cooldown State → Rest period after selling DP State Idea buy[i] = max(buy[i-1], cooldown[i-1] - price[i]) sell[i] = buy[i-1] + price[i] cooldown[i] = max(cooldown[i-1], sell[i-1]) 🔍 What I Practiced: ✔ Understanding state-based dynamic programming ✔ Managing multiple DP states simultaneously ✔ Handling cooldown constraints in trading problems ✔ Strengthening logic for complex transition problems This problem helped me understand how DP can model real-world scenarios with multiple decision states. #DSA #LeetCode #DynamicProgramming #Java #ProblemSolving #InterviewPreparation #Consistency #StockProblems

🚀 Daily DSA Practice – Day 53 | Dynamic Programming – Circular Houses (Java) Continuing my Dynamic Programming practice, today I solved an extension of the House Robber problem where houses are arranged in a circular street. This adds an extra constraint because the first and last houses are adjacent, meaning they cannot be robbed together. 📌 Problem Solved (LeetCode): 213. House Robber II (Medium) 🎯 Concept: Dynamic Programming with Circular Constraint 🧠 Key Learning: Since the first and last houses cannot both be robbed, the problem is divided into two linear House Robber problems: 1️⃣ Rob houses from index 0 → n-2 2️⃣ Rob houses from index 1 → n-1 Then take the maximum result from the two cases. DP Idea: result = max(rob(0...n-2), rob(1...n-1)) 🔍 What I Practiced: ✔ Handling circular array constraints ✔ Breaking a complex problem into two simpler DP subproblems ✔ Reusing House Robber DP logic ✔ Improving understanding of problem transformation techniques This problem reinforced how many advanced problems can be solved by transforming them into simpler known patterns. #DSA #LeetCode #DynamicProgramming #Java #ProblemSolving #InterviewPreparation #Consistency #SoftwareEngineer #HouseRobber

Day 8 — Array problems Searching & basic operations Method practice (modular coding) Big shift: Stopped writing everything in one block. Started breaking problems into functions. Less chaos. More structure. Day 9 tomorrow. #LearnInPublic #Java #BuildInPublic

Day 94/100 – LeetCode Challenge ✅ Problem: #139 Word Break Difficulty: Medium Language: Java Approach: Dynamic Programming with Max Length Optimization Time Complexity: O(n × m × k) where n = string length, m = max word length, k = avg word length comparison Space Complexity: O(n) Key Insight: dp[i] = true if substring s[0:i) can be segmented into dictionary words. Check all possible word endings ending at position i. Optimize by limiting check to maximum word length in dictionary. Solution Brief: Initialized dp[0] = true (empty string can be segmented). Found maximum word length in dictionary for pruning. For each position i, checked substrings ending at i with length ≤ max_len. If dp[j] is true and substring s[j:i) is in dictionary, set dp[i] = true. Return dp[n]. #LeetCode #Day94 #100DaysOfCode #DynamicProgramming #Java #Algorithm #CodingChallenge #ProblemSolving #WordBreak #MediumProblem #String #DP #Optimization #DSA

Day 4 of my DSA journey Today’s focus was on Dynamic Programming and Linked Lists. Key learnings: • Longest Common Subsequence (LCS), Longest Palindromic Subsequence (LPS), and Longest Repeating Subsequence (LRS) • Understood how breaking problems into smaller subproblems and storing results reduces time complexity significantly. • Learned the transition from recursion to dynamic programming for optimal solutions. • Explored Linked Lists and practiced problems involving traversal and pointer manipulation. • Understood the slow and fast pointer technique to detect cycles efficiently. Big takeaway: The real improvement is not just solving problems, but understanding patterns and optimizing solutions. #DSA #100DaysOfCode #Java #ProblemSolving #LearningJourney

🚀 Daily DSA Practice – Day 55 | Dynamic Programming – Maximum Product Subarray (Java) Continuing my Dynamic Programming practice, today I solved a problem that involves handling positive and negative numbers while maintaining optimal subarray products. 📌 Problem Solved (LeetCode): 152. Maximum Product Subarray (Medium) 🎯 Concept: Dynamic Programming with Tracking Min & Max 🧠 Problem Idea: Unlike the maximum sum subarray problem, this problem requires tracking both: Maximum product so far Minimum product so far because a negative number can flip the minimum into a maximum. DP Idea maxProd = max(nums[i], nums[i] * prevMax, nums[i] * prevMin) minProd = min(nums[i], nums[i] * prevMax, nums[i] * prevMin) 🔍 What I Practiced: ✔ Handling negative numbers in DP problems ✔ Tracking both minimum and maximum states ✔ Understanding subarray optimization techniques ✔ Improving array traversal with constant space This problem helped me understand how Dynamic Programming sometimes requires maintaining multiple states instead of a single DP array. #DSA #LeetCode #DynamicProgramming #Java #ProblemSolving #InterviewPreparation #Consistency #SoftwareEngineer

📘 DSA Journey — Day 11 Today’s focus: Sliding Window with distinct element constraints. Problem solved: • Subarrays with K Different Integers (LeetCode 992) Concepts used: • Sliding Window / Two-pointer technique • Frequency tracking using HashMap • Counting subarrays using window expansion Key takeaway: The goal of this problem is to count the number of subarrays that contain exactly K distinct integers. A useful trick here is to break the problem into two parts: Subarrays with exactly K distinct = Subarrays with at most K distinct − Subarrays with at most (K−1) distinct Using a sliding window, we maintain a window that contains at most K distinct elements. A frequency map keeps track of how many times each element appears in the current window. As the window expands, if the number of distinct elements exceeds K, we shrink the window from the left until the condition is satisfied again. At each step, the number of valid subarrays ending at the current index can be counted efficiently, allowing the entire problem to be solved in O(n) time. Continuing to strengthen pattern recognition and consistency in solving DSA problems. #DSA #Java #LeetCode #CodingJourney

🚀 Day 16/100 Days of Code Challenge Solved the classic “Sort Colors” problem (LeetCode 75) today! 🎯 🔹 Problem Summary: Given an array containing 0s, 1s, and 2s (representing colors), sort them in-place without using built-in sort. 🔹 Approach Used: Maintained three pointers: low, mid, high Efficiently partitioned the array in a single pass 🔹 Key Learning: ✔️ In-place sorting can be done in O(n) time ✔️ Using pointers smartly avoids extra space 💡 Time Complexity: O(n) 💡 Space Complexity: O(1) 🔹 Code Highlight : Used swapping and pointer movement to organize elements in one traversal. Consistency is the key 🔑 — one step closer to mastering DSA! #Day16 #100DaysOfCode #DSA #Java #CodingChallenge #LeetCode #ProblemSolving #TechJourney