Improvements for Trapping Rain water Problem.
iHackSubhodip opened this issue · 0 comments
iHackSubhodip commented
Here I just tried to improve the space complexity.
your Solution ->
https://github.com/soapyigu/LeetCode-Swift/blob/master/Math/TrappingRainWater.swift
Mine with -> O(n) TC and O(1) SC
`
class Solution {
func trap(_ height: [Int]) -> Int {
var waterContainerResult = 0
var left = 0, right = height.count - 1, leftMax = 0, rightMax = 0
while left < right{
if height[left] < height[right]{
if height[left] >= leftMax{
leftMax = height[left]
}else{
waterContainerResult = waterContainerResult + leftMax - height[left]
}
left += 1
}else{
if height[right] >= rightMax{
rightMax = height[right]
}else{
waterContainerResult = waterContainerResult + rightMax - height[right]
}
right -= 1
}
}
return waterContainerResult
}
}
`
Runtime: 28 ms, faster than 93.62% of Swift online submissions for Trapping Rain Water.
Memory Usage: 20.9 MB, less than 5.01% of Swift online submissions for Trapping Rain Water.
If it looks fine, I will raise a PR for this.