trappingRainWater.java

    public int trap(int[] h) {
        int n = h.length;
        //edge cases--TODO
        if(n == 0 || n == 1) return 0;
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();//heights to Indices
        boolean leftZeroes = true;
        for(int i = 0; i < n; i++){
            //ignore left zeroes
            if(h[i] == 0) continue;
            //Fill map height --> [idx1, idx2, ...]
            int height = h[i];
            for(int heightCandidata = 1; heightCandidata <= height; heightCandidata++){
                if(!map.containsKey(heightCandidata)){
                    ArrayList<Integer> indices = new ArrayList<>();
                    indices.add(i);
                    map.put(heightCandidata, indices);
                }else{
                    ArrayList<Integer> indices = map.get(heightCandidata);
                    indices.add(i);
                    map.put(heightCandidata, indices);
                }
            }

        }
        //System.out.println(map.toString());
        int water = 0;
        for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
            Integer height = entry.getKey();
            ArrayList<Integer> list = entry.getValue();
            if(list.size() == 1) continue;
            for(int ilist = 0; ilist < list.size()-1; ilist++){
                int startIdx = list.get(ilist);
                for(int i = startIdx+1; i < n; i++){
                    if(h[i] >= height) break;
                    water++;
                }
            }
        }
        return water;
    }