MinDepth.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class MinDepth {

        private static void mindepth(int[] array, int index, int depth, HashMap<Integer, int[]> maps) {
                List<Integer> added = new ArrayList<Integer>();
                for (int i = 0; i < index; ++i) {
                        if (array[i] + i >= index) {
                                int olddepth;
                                if (maps.containsKey(i)) {
                                        olddepth = maps.get(i)[0];
                                } else {
                                        olddepth = Integer.MAX_VALUE;
                                }
                                if (depth < olddepth) {
                                        if (!maps.containsKey(i)) {
                                                added.add(i);
                                        }
                                        maps.put(i, new int[] { depth, index });
                                }
                        }
                }
                for (int key : added) {
                        mindepth(array, key, maps.get(key)[0] + 1, maps);
                }
        }

        public static void mindepth(int[] array) {
                int length = array.length;
                HashMap<Integer, int[]> maps = new HashMap<Integer, int[]>();
                maps.put(length - 1, new int[] { 0, length });
                mindepth(array, length - 1, 1, maps);
                System.out.println("input: " + Arrays.toString(array));
                if (maps.containsKey(0)) {
                        System.out.println("count: " + maps.get(0)[0]);
                        int i = 0;
                        while (maps.containsKey(i) && i < length) {
                                System.out.println("steps: " + array[i] + ", index: " + i);
                                i = maps.get(i)[1];
                        }
                } else {
                        System.out.println("count: -1");
                }
        }

        public static void main(String... args) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                for (String arg : args) {
                        for (String i : arg.split(",")) {
                                try {
                                        list.add(Integer.parseInt(i.trim()));
                                } catch (NumberFormatException e) {
                                        // do nothing
                                }
                        }
                }
                int[] array = new int[list.size()];
                for (int i = 0; i < list.size(); ++i) {
                        array[i] = list.get(i);
                }
                mindepth(array);
        }

}