O(n) solution in Java


  • 0
    I

    This solution will try to find the minimum of first and last height, and then computes the trapped water for all the lower heights. However, considering that first or last heights might not be the tallest in the entire array - I extend the same theory to break into multiple sub-arrays.

    For ex:
    [5,3,1,1,3] --> This is a simple case: 1st/last elements are the tallest. whatever can fill in between 5 and 3 would be the max trapped water.
    [3,2,4,1,6,3,5,1] --> We break the arrays to {{3,2,4}, {4,1,6}, {6,3,5,1}} so that the 1st/last elements are the tallest and trapped water is easy to compute.

    public int trap(int[] blocks) {
    		if (blocks == null || blocks.length <= 0) {
    			return 0;
    		}
    
    		int min = blocks[0];
    		int minIndex = 0;
    		Map<Integer, Integer> nextMaxMap = new TreeMap<>();
    		for (int i=1;i<blocks.length;i++) {
    			if (blocks[i] > min) {
    				nextMaxMap.put(minIndex, i);
    				minIndex = i;
    				min = blocks[minIndex];
    			}
    		}
    		nextMaxMap.put(minIndex, blocks.length-1);
    
    		int maxWater = 0;
    		for (Map.Entry<Integer, Integer> entry: nextMaxMap.entrySet()) {
    			maxWater +=trap(blocks, entry.getKey(), entry.getValue());
    		}
    		return maxWater;
    
    	}
    
    	public int trap(int[] A, int start, int end) {
    		int min = Math.min(A[start], A[end]);
    		int maxWater = 0;
    		while (start < end) {
    			if (Math.min(A[start], A[end]) > min) {
    				min = Math.min(A[start], A[end]);
    			}
    			if (A[start] < A[end]) {
    				maxWater += (min - A[start]);
    				start++;
    			} else {
    				maxWater += (min - A[end]);
    				end--;
    			}
    		}
    		return maxWater;
    	}
    

Log in to reply
 

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