JAVA 10 lines accepted code, O(n) time, O(1) space. Is there a better solution?


  • 36
    R

    Basically this solution runs two pointers from two sides to the middle, and the plank is used to record the height of the elevation within a certain range, plank height can only increase (or remain the same) from two sides to the middle. If the current pointer is pointing at a number that is less than the current plank height, the difference between plank height and the number would be the amount of water trapped. Otherwise, A[i] == plank, no water is trapped.

    public class Solution {
        public int trap(int[] A) {
            int i = 0, j = A.length - 1, result = 0, plank = 0;
            while(i <= j){
                plank = plank < Math.min(A[i], A[j]) ? Math.min(A[i], A[j]) : plank;
                result = A[i] >= A[j] ? result + (plank - A[j--]) : result + (plank - A[i++]);
            }
            return result;
        }
    }

  • 0
    I

    sweet! good job ;)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.