Day 16/150 | LeetCode 42 - Trapping Rain Water | Java | DSA Journey | Becoming Sudeep

🚀 Day 16 of My DSA Journey! I'm documenting my journey to become the best version of myself and prepare for Software Engineering roles at top product-based companies by solving the LeetCode Top Interview 150 questions—one problem at a time. 📌 Today's Problem ✅ LeetCode 42 – Trapping Rain Water 🎯 In this video, I cover: Understanding the Problem 🐢 Brute Force Approach ⚡ Two Pointer Approach (Optimal) Java Implementation Dry Run Time & Space Complexity Key Takeaways 📚 Approaches Covered 1️⃣ Brute Force For every building, calculate the tallest bar on its left and right. The amount of trapped water at that position is: min(leftMax, rightMax) − currentHeight Repeat this for every index and sum the trapped water. Although simple, this repeatedly scans the array to find the left and right maximum heights. ⏱ Time Complexity O(n²) 💾 Space Complexity O(1) 2️⃣ Optimal — Two Pointer Approach Maintain two pointers: Left pointer Right pointer Also maintain: leftMax rightMax At every step: If leftMax ≤ rightMax, process the left pointer. Otherwise, process the right pointer. The trapped water is calculated immediately without any extra arrays. This achieves the optimal solution using constant extra space. ⏱ Time Complexity O(n) 💾 Space Complexity O(1) 💡 Key Learning This problem teaches one of the most important Two Pointer techniques. The key ideas are: ✅ Water trapped at an index depends on the smaller of the tallest bars on both sides. ✅ Brute force repeatedly searches for the left and right maximum heights. ✅ The Two Pointer approach avoids repeated scans by maintaining leftMax and rightMax while traversing from both ends. ✅ Only the side with the smaller maximum height determines the trapped water at that step. ✅ The optimal solution solves the problem in O(n) time with O(1) extra space. This is one of the most frequently asked interview problems because it demonstrates how a clever Two Pointer strategy reduces the time complexity from O(n²) to O(n) while keeping the space complexity constant. 💬 Quote "I have never been confident about my career at any stage." — Amitabh Bachchan 🚀 My Goals ✔ Solve the LeetCode Top 150 Interview Questions ✔ Strengthen Problem-Solving Skills ✔ Master Data Structures & Algorithms ✔ Crack Software Engineering Interviews at Top Tech Companies ✔ Build in Public & Stay Consistent If you're preparing for coding interviews, improving your DSA skills, or simply love programming, let's learn and grow together. ✅ Day 16/150 — 134 problems to go. See you on Day 17! 💪 #leetcode #leetcode150 #dsa #java #twopointers #arrays #algorithms #datastructures #coding #programming #softwareengineer #interviewprep #buildinpublic #100DaysOfCode #problemsolving #trappingrainwater #leetcode42