after watching 4 videos , finally I understood from this lecture .... thank you sir ❤🙏

very good explainetion

Nice Explanation

//Bruteforce Approach class Solution { public int trap(int[] arr) { /* * In a sorted array (ascending or descending), no water can be trapped because * there are no valleys where water can collect. Ascending arrays form an upward * slope, and descending arrays form a downward slope, causing water to flow * off. Valleys are essential for trapping water, which sorted arrays lack. */ if (arr.length < 3 || isMonotonicallySorted(arr)) { return 0; } int totalUnitOfWaterTrapped = 0; for (int i = 0; i < arr.length; i++) { // Find the maximum height to the left of the current index int leftMax = maxOnLeft(arr, i); // Find the maximum height to the right of the current index int rightMax = maxOnRight(arr, i); /* * If both the left and right maximum heights are greater than the current * height, calculate the trapped water at this index and add it to the total. */ if (leftMax > arr[i] && rightMax > arr[i]) { totalUnitOfWaterTrapped += (Math.min(leftMax, rightMax) - arr[i]); } } return totalUnitOfWaterTrapped; } private int maxOnLeft(int[] arr, int index) { int max = Integer.MIN_VALUE; for (int i = 0; i < index; i++) { max = Math.max(max, arr[i]); } return max; } private int maxOnRight(int[] arr, int index) { int max = Integer.MIN_VALUE; for (int i = index + 1; i < arr.length; i++) { max = Math.max(max, arr[i]); } return max; } private boolean isMonotonicallySorted(int[] arr) { boolean ascendingSorted = true; boolean descendingSorted = true; for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { ascendingSorted = false; } if (arr[i] < arr[i + 1]) { descendingSorted = false; } if (!ascendingSorted && !descendingSorted) { return false; } } return true; } } //Good Approach class Solution { public int trap(int[] arr) { if (arr.length < 3) { return 0; } int totalUnitOfWaterTrapped = 0; int[] maxOnLeft = computeMaxLeft(arr); int[] maxOnRight = computeMaxRight(arr); for (int i = 0; i < arr.length; i++) { int leftMax = maxOnLeft[i]; int rightMax = maxOnRight[i]; if (leftMax > arr[i] && rightMax > arr[i]) { totalUnitOfWaterTrapped += (Math.min(leftMax, rightMax) - arr[i]); } } return totalUnitOfWaterTrapped; } private int[] computeMaxLeft(int[] arr) { int[] maxOnLeft = new int[arr.length]; int maxSoFarOnLeft = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { maxOnLeft[i] = maxSoFarOnLeft; maxSoFarOnLeft = Math.max(maxSoFarOnLeft, arr[i]); } return maxOnLeft; } private int[] computeMaxRight(int[] arr) { int[] maxOnRight = new int[arr.length]; int maxSoFarOnRight = Integer.MIN_VALUE; for (int i = arr.length - 1; i >= 0; i--) { maxOnRight[i] = maxSoFarOnRight; maxSoFarOnRight = Math.max(maxSoFarOnRight, arr[i]); } return maxOnRight; } } //Better Approach class Solution { public int trap(int[] arr) { if (arr.length < 3) { return 0; } int totalUnitOfWaterTrapped = 0; int maxSoFarOnLeft = Integer.MIN_VALUE; int[] maxOnRight = computeMaxRight(arr); for (int i = 0; i < arr.length; i++) { int rightMax = maxOnRight[i]; if (maxSoFarOnLeft > arr[i] && rightMax > arr[i]) { totalUnitOfWaterTrapped += (Math.min(maxSoFarOnLeft, rightMax) - arr[i]); } maxSoFarOnLeft = Math.max(maxSoFarOnLeft, arr[i]); } return totalUnitOfWaterTrapped; } private int[] computeMaxRight(int[] arr) { int[] maxOnRight = new int[arr.length]; int maxSoFarOnRight = Integer.MIN_VALUE; for (int i = arr.length - 1; i >= 0; i--) { maxOnRight[i] = maxSoFarOnRight; maxSoFarOnRight = Math.max(maxSoFarOnRight, arr[i]); } return maxOnRight; } } //Optimal Approach (Space Optimised) /* * The building at `height[maxHeightIndex]` divides the array into two halves: left and right. * * For all buildings in the left half (before `maxHeightIndex`), the maximum height building * to their right will always be `height[maxHeightIndex]`. Thus, water can be trapped at each * position based on the difference between the current building height and `height[maxHeightIndex]`. * * Similarly, for all buildings in the right half (after `maxHeightIndex`), the maximum height * building to their left will always be `height[maxHeightIndex]`. Water is trapped based on the * difference between the current building height and `height[maxHeightIndex]`. * * By treating `height[maxHeightIndex]` as the boundary, we can independently calculate the trapped * water in the left and right halves. */ class Solution { public int trap(int[] arr) { if (arr.length < 3) { return 0; } int totalUnitOfWaterTrapped = 0; // Step 1: Find the maximum height building int i = 1, j = arr.length - 1; int maxHeightIndex = 0; // Index of the highest building. while (i <= j) { if (arr[i] > arr[maxHeightIndex]) { maxHeightIndex = i; } if (arr[j] > arr[maxHeightIndex]) { maxHeightIndex = j; } i++; j--; } // Step 2: Compute water trapped in the first half (left to maxHeightIndex) int maxSoFarOnLeft = Integer.MIN_VALUE; for (i = 0; i < maxHeightIndex; i++) { if (arr[i] < maxSoFarOnLeft) { totalUnitOfWaterTrapped += maxSoFarOnLeft - arr[i]; } maxSoFarOnLeft = Math.max(maxSoFarOnLeft, arr[i]); } // Step 3: Compute water trapped in the second half (right from maxHeightIndex) int maxSoFarOnRight = Integer.MIN_VALUE; for (i = arr.length - 1; i > maxHeightIndex; i--) { if (arr[i] < maxSoFarOnRight) { totalUnitOfWaterTrapped += maxSoFarOnRight - arr[i]; } maxSoFarOnRight = Math.max(maxSoFarOnRight, arr[i]); } return totalUnitOfWaterTrapped; } }

Bsc in CS students are eligible For scaler ?

I'm btech ee I'm 27 can I join scaler

I'm betech passout can I join scaler and which course will be best in 27 right now.।।।।।

thanks to you sir , this algorithm best explained by you ,in youtube

good teaching skills

Sir can i give nset exam in mobile phn????

kya baat hai bhut saare video dekhne ke baad n=bhi nhi smjh aaya lekin kya clear code explain kiya maza aa gya....aur new subscriber bhi🤠

Thanks for great video

DATA STRUCTURE 5 MONTHS FEE ?

Sir mere bca complete hua lakin mujhe kuch nhi aata hai 😢 toh mai konsa course choose kru scaler ka jise mereko skillup krne or job milne mai help ho please answer sir ???

Waste of money , I had done my data science from here and my 2.5 lakh rupees got waste

Sir ji me Aapko wottsap pe messages kar raha hu

Maine koi bhi technical nahi kiya 😢 kya mai kuch kar paounga mai mere paas koi government & diploma degree nahi

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> m1=new HashMap<>(); for(int i=0;i<nums.length;i++) { int complement=target-nums[i]; if(m1.containsKey(complement)) { return new int[] {m1.get(complement),i}; } m1.put(nums[i], i); } return new int[0]; } }

Devops ki fees kya hai???

Good 👍

NST,SST,PW IOI >>>> PRIVATE ENGINEERING COLLEGE OR LOWER NIT IIT

Kyo chale aate ho padhane jab nahi aata hai padana time bhi waste karte ho aur concept bhi samajh nahi aata hai

Hi brother, I am one of your subscriber. I am preparing for Nset right now. Can I know which college you suggest among scaler,Newton,PW ioi, polaris and kalvium.I am so confused.As you are a software engineer you know more about this.Pick one please.

Bro what's your insta id

Sir agr koi baccha exam kr le lekin vo fees pay na kr skey to

😊

Thankyou brother very helpfull your video me

Data science wala 12th passed course nhi le sakta ??😢😢

Online kahi se bhi padh sakte hai n ya college jana padega ?

Bhai highest placement kitna gya hai plzz reply scaler se

Bro for international students?

Bhaiya i m 1st year student but i m studying in normal college form bihar pursuing BTech in CSE so i can join scaler course

After spending 4hours in depression for understanding this concept, finally landed here...crisp and clear!

Bhaiya kya mujhe class 12 maths me 80%+ lena padhrga?? Mera 77 aya he admission possible hai??

HEY BRO CAN YOU TELL ME SOMETHING ABOUT SCHOLARSHIPS??

Please firstly upload a video on how to solve problems on this leet code platform As it seems very different, like already given inputs, result and some prrle written part of codes, like overall interface is so weird, So please a separate video on that ❤

Work from home ka placement mil sakta ha kya

may I know sir I m working bpo sector and m graduated from arts stream and hv zero knowledge , looking for better opportunities and planning to change the field so may I know can I try fr course

After watching 2 , 3 videos from others , lastly i understand this topic from this channel . Thanks Daddaa.💌

Bcom graduated bhe join kr skte hei

Jisko koi bhi language nahi aata vo beginners le sakta hai kya???

Bhai kya financial assistance hai

I'm 2019 passout university medalist.।।। 1year apprenticeship.। I did।।।। 6 months chemical plant Ive joined and july 2024 I left that.।। I'm looking for a course

for me no one explained this question better than you!

Bahut accha batayaaapne 😊

Bhaiya regular videos upload karo leetocde solution kei🙏🏻🙏🏻. Kisse aue ka vdo dekh ke smjh nhi aata & java me bahot km mentor hai plz upload

Bhai apna leetcode ke problem ki iss series of 1000 tak le jao please aaap bahut accha padate ho.

Is scaler have branch in pune for physical class

Here is my solution without using 2nd while loop : class Solution { public int lengthOfLongestSubstring(String s) { int right=0,left=0; Set<Character>st = new HashSet(); int max=0; while(right<s.length()) { if(st.add(s.charAt(right))) { max=Math.max(max,right-left+1); right++; } else { st.remove(s.charAt(left)); left++; } } return max; } }

Nice explanation 👍👍