soapyigu/LeetCode-Swift

Improvements for Trapping Rain water Problem.

iHackSubhodip opened this issue · 0 comments

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.