Leetcode Medium: Container with most water

Problem Name: Container with most water

Problem Description: https://leetcode.com/problems/container-with-most-water

Problem Approach used: This problem can be solved with multiple approaches. The naive solution calculates the water content in all possible containers, compares and returns the maximum water that can be contained. It is O(n^2) time solution with O(1) auxiliary space.

Other "smarter" solution takes O(n) time with O(1) space. It makes use of the 2-pointer technique. 

Time Complexity:  O(n) worst-case time complexity and O(1) auxiliary space complexity.

Solution 1:

class Solution { public int maxArea(int[] height) { int maxArea = Integer.MIN_VALUE; for (int i=0; i<height.length; i++) { for (int j=i+1; j<height.length; j++) { int lesserHeight = Math.min(height[i], height[j]); maxArea = Math.max (maxArea, lesserHeight*(j-i)); } } return maxArea; } }

Solution 2:

class Solution { public int maxArea(int[] height) { // 2 pointer technique int smallerIndex=0, greaterIndex=height.length-1; int maxAreaSoFar = 0; while (smallerIndex < greaterIndex) { if (height[smallerIndex] >= height[greaterIndex]) { maxAreaSoFar = Math.max(maxAreaSoFar, height[greaterIndex] * (greaterIndex - smallerIndex)); greaterIndex-- ; } else if (height[smallerIndex] < height[greaterIndex]) { maxAreaSoFar = Math.max(maxAreaSoFar, height[smallerIndex] * (greaterIndex - smallerIndex)); smallerIndex++; } else { ; } } return maxAreaSoFar; } }

Until Next time, Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder

Leetcode Hard: Trapping Rain Water

 

Problem Name: Trapping Rain Water

Problem Description: https://leetcode.com/problems/trapping-rain-water/

Problem Approach used: Calculate the amount of water this index would store with the knowledge of highest left and highest right tower. Then subtract the hight of the current tower as that's just conctrete, water can't seep into.

Time Complexity:  O(n) worst-case time and space complexity.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public int trap(int[] height) { int n = height.length; int[] leftMax = new int[n]; int[] rightMax = new int[n]; int maxHt = 0; for (int i=0; i<n; i++) { maxHt = Math.max (maxHt, height[i]); leftMax[i] = maxHt; } maxHt = 0; for (int i=n-1; i>=0; i--) { maxHt = Math.max (maxHt, height[i]); rightMax[i] = maxHt; } int totalWater = 0; int water = 0; for (int i=0; i<n; i++) { water = Math.min(leftMax[i], rightMax[i]) - height[i]; totalWater += water; } return totalWater; } }

Keep coding and have fun!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder