<commit_before>package advanced.scan.twopointers.lc042_trappingrainwater;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * Given n non-negative integers representing an elevation map where the width of each bar is 1,
 * compute how much water it is able to trap after raining.
 * For example, given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
 */
public class Solution {

    // first search the maximal bar in the heights and then do two traverse -
    // one from the leftmost bar to the highest bar and another one from the rightmost to the highest bar.
    // This solution combine these three steps in a very clever way.
    public int trap(int[] height) {
        int ltall = 0, rtall = 0, water = 0;
        for (int l = 0, r = height.length - 1; l < r; ) {
            if (height[l] < height[r]) {
                if (ltall < height[l]) ltall = height[l];
                else water += ltall - height[l++];
            } else {
                if (rtall < height[r]) rtall = height[r];
                else water += rtall - height[r--];
            }
        }
        return water;
    }
<commit_msg>leetcode-42: trapping rain water<commit_after>package advanced.scan.twopointers.lc042_trappingrainwater;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * Given n non-negative integers representing an elevation map where the width of each bar is 1,
 * compute how much water it is able to trap after raining.
 * For example, given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
 */
public class Solution {

    public int trap(int[] height) {
        int total = 0, high1 = 0, high2 = 0;
        for (int l = 0, r = height.length - 1; l < r;) {
            if (height[l] < height[r]) {
                high1 = Math.max(high1, height[l]);
                total += high1 - height[l++];
            } else {
                high2 = Math.max(high2, height[r]);
                total += high2 - height[r--];
            }
        }
        return total;
    }

    // first search the maximal bar in the heights and then do two traverse -
    // one from the leftmost bar to the highest bar and another one from the rightmost to the highest bar.
    // This solution combine these three steps in a very clever way.
    public int trap4(int[] height) {
        int ltall = 0, rtall = 0, water = 0;
        for (int l = 0, r = height.length - 1; l < r; ) {
            if (height[l] < height[r]) {
                if (ltall < height[l]) ltall = height[l];
                else water += ltall - height[l++];
            } else {
                if (rtall < height[r]) rtall = height[r];
                else water += rtall - height[r--];
            }
        }
        return water;
    }

{'fraction_non_alphanumeric': 0.11537083482622716, 'fraction_numerical': 0.02149767108563239, 'mean_word_length': 2.0021505376344084, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6725558', 'n_tokens_mistral': 894, 'n_tokens_neox': 835, 'n_words': 307}