8000 Update README for Trapping Rain Water problem. · mmuchin/javascript-algorithms@f1152bf · GitHub
[go: up one dir, main page]
Skip to content

Commit f1152bf

Browse files
trekhlebtrekhleb
committed
Update README for Trapping Rain Water problem.
1 parent 26239f9 commit f1152bf

File tree

1 file changed

+5
-2
lines changed
  • src/algorithms/uncategorized/rain-terraces

1 file changed

+5
-2
lines changed

‎src/algorithms/uncategorized/rain-terraces/README.md

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -109,9 +109,12 @@ The concept is illustrated as shown:
109109

110110
**Complexity Analysis**
111111

112-
Time complexity: `O(n)`.
112+
Time complexity: `O(n)`. We store the maximum heights upto a point using 2
113+
iterations of `O(n)` each. We finally update `answer` using the stored
114+
values in `O(n)`.
113115

114-
Auxiliary space complexity: `O(n)` extra space.
116+
Auxiliary space complexity: `O(n)` extra space. Additional space
117+
for `left_max` and `right_max` arrays than in Approach 1.
115118

116119
## References
117120

0 commit comments

Comments
 (0)
0