public static int mystery(int a, int b) {
	if (b == 0) return 1;
	if (b % 2 == 0) return mystery(a + a, b / 2);
	return mystery(a + a, b / 2) + a;
}

public List<Integer> grayCode(int n) {
	List<Integer> result = new ArrayList<>();
	result.add(0);
	for (int i = 0; i < n; i++) {
		int size = result.size();
		for (int k = size - 1; k >= 0; k--) {
			result.add(result.get(k) | (1 << i));
		}
	}
	return result;
}

moveDisks(int n, Tower origin, Tower destination, Tower buffer) {
	// Base Case
	if (n <= 0)
		return;

	// Move top n - 1 disks from origin to buffer, using destination as a buffer.
		moveDisk(n - 1, origin, buffer, destination)

	// Move top (the last one) from origin to destination
		moveTop(origin, destination)

	// Move top n - 1 disks from buffer to destination, using origin as a buffer.
		moveDisks(n - 1, buffer, destination, origin)
}

public class HanoiTower {
	private static final int NUM_PEGS = 3;

	class Tower {
		private Stack<Integer> disks;
		private int index;

		public Tower(int i) {
			disks = new Stack<Integer>();
			index = i;
		}

		public int index() {
			return index;
		}

		public void add(int disk) {
			if (!disks.isEmpty() && disks.peek() <= disk)
				System.err.println("Error placing disk " + disk);
			else
				disks.push(disk);
		}

		public void moveTopTo(Tower tower) {
			int top = disks.pop();
			tower.add(top);
		}

		public void moveDisks(int n, Tower destination, Tower buffer) {
			if (n <= 0)
				return;
			moveDisks(n - 1, buffer, destination);
			moveTopTo(destination);
			System.out.println("Moved top from " + this.index + " to " + destination.index);
			buffer.moveDisks(n - 1, destination, this);
		}

		public String toString() {
			return disks.toString();
		}
	}

	public Tower printHanoiTower(int numRings) {
		Tower[] towers = new Tower[NUM_PEGS];
		for (int i = 0; i < towers.length; i++) {
			towers[i] = new Tower(i);
		}
		for (int i = numRings; i >= 1; i--) {
			towers[0].add(i);
		}
		towers[0].moveDisks(numRings, towers[2], towers[1]);
		return towers[2];
	}

	public static void main(String[] args) {
		HanoiTower solution = new HanoiTower();
		Tower tower = solution.printHanoiTower(5);
		System.out.println("Tower: " + tower.toString());
		assert tower.toString().equals("[5, 4, 3, 2, 1]");
	}
}

public class TreeDiameter {
	public static class TreeNode {
		List<Edge> edges = new ArrayList<>();
	}

	private static class Edge {
		public TreeNode node;
		public Double length;

		public Edge(TreeNode node, Double length) {
			this.node = node;
			this.length = length;
		}
	}

	private static class DistanceAndDiameter {
		public Double distance;
		public Double diameter;

		public DistanceAndDiameter(Double distance, Double diameter) {
			this.distance = distance;
			this.diameter = diameter;
		}
	}

	public static double computeDiameter(TreeNode T) {
		return T != null ? computeDistanceAndDiameter(T).diameter : 0.0;
	}

	private static DistanceAndDiameter computeDistanceAndDiameter(TreeNode r) {
		double diameter = Double.MIN_VALUE;
		// Stores the max two distances. distance[0] is the max distance
		double[] distances = { 0.0, 0.0 };
		for (Edge e : r.edges) {
			DistanceAndDiameter distanceDiameter = computeDistanceAndDiameter(e.node);
			if (distanceDiameter.distance + e.length > distances[0]) {
				// Shift and store the max two distances
				distances = new double[] { distanceDiameter.distance + e.length, distances[0] };
			} else if (distanceDiameter.distance + e.length > distances[1]) {
				// When only greater than the second distance
				distances[1] = distanceDiameter.distance + e.length;
			}
			diameter = Math.max(diameter, distanceDiameter.diameter);
		}
		return new DistanceAndDiameter(distances[0], Math.max(diameter, distances[0] + distances[1]));
	}
}

  public int networkDelayTime(int[][] times, int N, int K) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] edge : times) {
      if (!graph.containsKey(edge[0])) {
        graph.put(edge[0], new ArrayList<>());
      }
      graph.get(edge[0]).add(new int[] { edge[1], edge[2] });
    }

    Queue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    heap.offer(new int[] { K, 0 }); // [node, distance]

    // Cache distances of shortest path from A -> B
    Map<Integer, Integer> distances = new HashMap<>();
    while (!heap.isEmpty()) {
      int[] info = heap.poll();
      if (distances.containsKey(info[0])) {
        continue; // Alreay visited
      }
      distances.put(info[0], info[1]);
      if (graph.containsKey(info[0])) {
        for (int[] edge : graph.get(info[0])) {
          if (!distances.containsKey(edge[0]))
            heap.offer(new int[] { edge[0], info[1] + edge[1] });
        }
      }
    }

    if (distances.size() != N)
      return -1;
    int answer = 0;
    for (int delay : distances.values())
      answer = Math.max(answer, delay);
    return answer;
  }

  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[][] graph = new int[n][n];
    for (int[] flight : flights) {
      graph[flight[0]][flight[1]] = flight[2];
    }

    // minimum costs array
    int[] costs = new int[n];
    // shortest steps array
    int[] stops = new int[n];
    Arrays.fill(costs, Integer.MAX_VALUE);
    Arrays.fill(stops, Integer.MAX_VALUE);
    costs[src] = 0;
    stops[src] = 0;

    // priority queue would contain (node, cost, stop)
    Queue<int[]> minHeap = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
    minHeap.offer(new int[] { src, 0, 0 });

    while (!minHeap.isEmpty()) {
      int[] top = minHeap.poll();
      int city = top[0];
      int cost = top[1];
      int stop = top[2];

      if (city == dst) {
        return cost;
      }

      // if there are no more steps left, continue
      if (stop == k + 1) {
        continue;
      }

      // relax all neighboring edges if possible
      for (int neighbor = 0; neighbor < n; neighbor++) {
        if (graph[city][neighbor] > 0) {
          int nextCost = cost + graph[city][neighbor];
          if (nextCost < costs[neighbor]) { // better cost?
            costs[neighbor] = nextCost;
            minHeap.offer(new int[] { neighbor, nextCost, stop + 1 });
            stops[neighbor] = stop; // does not have to be the shortest path
          } else if (stop < stops[neighbor]) { // better steps?
            minHeap.offer(new int[] { neighbor, nextCost, stop + 1 });
            stops[neighbor] = stop;
          }
        }
      }
    }

    return costs[dst] == Integer.MAX_VALUE ? -1 : costs[dst];
  }

/**
 * Different Ways to Add Parentheses
 * 
 * Given a string expression of numbers and operators, return all possible results from computing
 * all the different possible ways to group numbers and operators. You may return the answer in any
 * order.
 * 
 * <pre>
 * Example 1:
 * 
 * Input: expression = "2-1-1"
 * Output: [0,2]
 * Explanation:
 * ((2-1)-1) = 0 
 * (2-(1-1)) = 2
 * 
 * Example 2:
 * 
 * Input: expression = "2*3-4*5"
 * Output: [-34,-14,-10,-10,10]
 * Explanation:
 * (2*(3-(4*5))) = -34 
 * ((2*3)-(4*5)) = -14 
 * ((2*(3-4))*5) = -10 
 * (2*((3-4)*5)) = -10 
 * (((2*3)-4)*5) = 10
 * </pre>
 *
 */
public class AddParentheses {
  // Standard divide and conquer
  public List<Integer> diffWaysToCompute(String input) {
    List<Integer> result = new LinkedList<Integer>();
    for (int i = 0; i < input.length(); i++) {
      char c = input.charAt(i);
      if (c == '-' || c == '*' || c == '+') {
        String left = input.substring(0, i);
        String right = input.substring(i + 1);
        List<Integer> leftResult = diffWaysToCompute(left);
        List<Integer> rightResult = diffWaysToCompute(right);
        for (Integer l : leftResult) {
          for (Integer r : rightResult) {
            int x = 0;
            switch (c) {
            case '+':
              x = l + r;
              break;
            case '-':
              x = l - r;
              break;
            case '*':
              x = l * r;
              break;
            }
            result.add(x);
          }
        }
      }
    }
    // no operator
    if (result.size() == 0) {
      result.add(Integer.valueOf(input));
    }
    return result;
  }
}

public static int minimumTotalWaitingTime(List<Integer> serviceTimes) {
	Collections.sort(serviceTimes);
	int totalWaitingTime = 0;
	for (int i = 0; i < serviceTimes.size(); i++) {
		// exclude the last one!
		int numRemainingQueries = serviceTimes.size() - (i + 1);
		totalWaitingTime += serviceTimes.get(i) * numRemainingQueries;
	}
	return totalWaitingTime;
}

public static Integer findMinimumVisits(List<Interval> intervals) {
	Collections.sort(intervals, (a, b) -> (a.right - b.right));
	int numVisits = 0;
	int lastVisitTime = 0;
	for (Interval interval : intervals) {
		if (interval.left > lastVisitTime) {
			lastVisitTime = interval.right;
			numVisits++;
		}
	}
	return numVisits;
}

/**
 * Given weights and values of n items, put these items in a knapsack of capacity W to get the
 * maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and
 * wt[0..n-1] which represent values and weights associated with n items respectively. Also given an
 * integer W which represents knapsack capacity, find out the maximum value subset of val[] such
 * that sum of the weights of this subset is smaller than or equal to W. You cannot break an item,
 * either pick the complete item or don’t pick it (0-1 property).
 * 
 * <pre>
 * Example:     
 * int[] values = { 60, 100, 120 };
 * int[] weights = { 10, 20, 30 };
 * int capacity = 50;
 * 
 * Answer: 220; Weight = (30 + 20); Value = (120 + 100)
 * </pre>
 */
public class Knapsack {

  /**
   * Let Weights = {1, 2, 3}, Values = {10, 15, 40}, Capacity=6
   * 
   * <pre>
  0   1   2   3   4   5   6
  
  0  0   0   0   0   0   0   0
  
  1  0  10  10  10  10  10  10
  
  2  0  10  15  25  25  25  25
  
  3  0  10  15  40  50  55  65
   * </pre>
   */
  // Bottom up DP: Time complexity (O(n*w)), Space (O(w))
  public static int knapSack(int capacity, int[] weights, int[] values) {
    // From 2D to 1D array
    int[] dp = new int[capacity + 1];
    dp[0] = 0;

    for (int i = 0; i < weights.length; i++) {
      // Bottom up to avoid duplicate
      for (int w = capacity; w >= weights[i]; w--) {
        dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
      }
    }

    return dp[capacity];
  }

  // Memorization Recursive
  public static int knapSack2(int capacity, int weights[], int[] values) {
    int[][] dp = new int[values.length][capacity + 1];
    for (int[] d : dp) {
      Arrays.fill(d, -1);
    }
    return knapSackRec(capacity, weights, values, values.length - 1, dp);
  }

  private static int knapSackRec(int capacity, int[] weights, int[] values, int n, int[][] memo) {
    if (n < 0 || capacity == 0) {
      return 0;
    }

    if (memo[n][capacity] != -1) {
      return memo[n][capacity];
    }

    if (weights[n] > capacity) {
      memo[n][capacity] = knapSackRec(capacity, weights, values, n - 1, memo);
    } else {
      memo[n][capacity] = Math.max(values[n] + knapSackRec(capacity - weights[n], weights, values, n - 1, memo),
          knapSackRec(capacity, weights, values, n - 1, memo));
    }

    return memo[n][capacity];
  }

  public static void main(String[] args) {
    int[] values = { 60, 100, 120 };
    int[] weights = { 10, 20, 30 };
    int capacity = 30;
    System.out.print(knapSack2(capacity, weights, values));
  }

}

public static String majoritySearch(Iterator<String> sequence) {
	String candidate = null;
	int candidateCount = 0;
	while (sequence.hasNext()) {
		String current = sequence.next();
		if (candidateCount == 0) {
			candidate = current;
			candidateCount = 1;
		} else {
			if (current.equals(candidate))
				candidateCount++;
			else
				candidateCount--;
		}
	}
	return candidate;
}

// Use double linked list
public class HitCounter {
  private int total;
  private int window;
  private Deque<int[]> hits;

  public HitCounter() {
    total = 0;
    window = 5 * 60; // 5 mins window
    hits = new LinkedList<int[]>();
  }

  public void hit(int timestamp) {
    if (hits.isEmpty() || hits.getLast()[0] != timestamp) {
      hits.add(new int[] { timestamp, 1 });
    } else {
      hits.getLast()[1]++;
      // hits.add(new int[] { timestamp, hits.removeLast()[1] + 1 });
    }
    // Prevent from growing too much
    if (hits.size() > window) {
      purge(timestamp);
    }
    total++;
  }

  public int getHits(int timestamp) {
    purge(timestamp);
    return total;
  }

  private void purge(int timestamp) {
    while (!hits.isEmpty() && timestamp - hits.getFirst()[0] >= window) {
      total -= hits.removeFirst()[1];
    }
  }
}

// Use array rotation
public class HitCounter {
  private int total;
  private int window;
  private int[][] hits;

   public HitCounter() {
    total = 0;
    window = 5 * 60; // 5 mins window
    hits = new int[window][2];
  }

  public void hit(int timestamp) {
    int i = timestamp % hits.length;
    if (hits[i][0] != timestamp) {
      purge(i, timestamp);
    }
    hits[i][1]++;
    total++;
  }

  public int getHits(int timestamp) {
    for (int i = 0; i < hits.length; i++) {
      if (hits[i][0] != 0 && timestamp - hits[i][0] >= window) {
        purge(i, timestamp);
      }
    }
    return total;
  }

  private void purge(int i, int timestamp) {
    total -= hits[i][1];
    hits[i][0] = timestamp;
    hits[i][1] = 0;
  }
}

public static List<String> searchFrequentItems(Iterable<String> stream, int k) {
	// Finds the candidates which may occur > n / k times
	Map<String, Integer> table = new HashMap<>();
	int count = 0; // Counts the number of items

	Iterator<String> sequence = stream.iterator();
	while (sequence.hasNext()) {
		String item = sequence.next();
		table.put(item, table.getOrDefault(item, 0) + 1);
		count++;
		// Detecting k items in table, at least one of them must have exactly one in it, We will
		// discard those k items by one for each
		if (table.size() == k) {
			List<String> delKeys = new ArrayList<>();
			for (Map.Entry<String, Integer> entry : table.entrySet()) {
				if (entry.getValue() - 1 == 0)
					delKeys.add(entry.getKey());
				else
					table.put(entry.getKey(), entry.getValue() - 1);
			}
			for (String delKey : delKeys) {
				table.remove(delKey);
			}
		}
	}

	// Reset table for the following counting.
	for (String key : table.keySet()) {
		table.put(key, 0);
	}

	// Counts the occurence of each candidate word.
	sequence = stream.iterator();
	while (sequence.hasNext()) {
		String item = sequence.next();
		if (table.containsKey(item)) {
			table.put(item, table.get(item) + 1);
		}
	}

	// Selects the word which occurs > n/k times
	List<String> result = new ArrayList<>();
	for (Map.Entry<String, Integer> it : table.entrySet()) {
		if (count * 1.0 / k < (double) it.getValue()) {
			result.add(it.getKey());
		}
	}

	return result;
}

public static int canCompleteCircuit(int[] gas, int[] cost) {
	int sumGas = 0, sumCost = 0;
	int start = 0, tank = 0;
	for (int i = 0; i < gas.length; i++) {
		sumGas += gas[i];
		sumCost += cost[i];
		tank += gas[i] - cost[i]; // track tank's gas left!
		if (tank < 0) {
			start = i + 1;
			tank = 0;
		}
	}
	return sumGas < sumCost ? -1 : start;
}

public class ThreeFourSumProblems {
	/**
	 * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find
	 * all unique triplets in the array which gives the sum of zero.
	 *
	 * Note: The solution set must not contain duplicate triplets.
	 *
	 * <pre>
	For example, given array S = [-1, 0, 1, 2, -1, -4],

	A solution set is:
	[
	  [-1, 0, 1],
	  [-1, -1, 2]
	]
	 * </pre>
	 *
	 */
	public static List<List<Integer>> threeSumEquals(int[] nums, int target) {
		List<List<Integer>> result = new ArrayList<>();
		if (nums == null || nums.length < 3)
			return result;
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 2; i++) {
			// skip duplicates
			if (i > 0 && nums[i] == nums[i - 1])
				continue;
			int lo = i + 1, hi = nums.length - 1;
			while (lo < hi) {
				int sum = nums[i] + nums[lo] + nums[hi];
				if (sum == target) {
					result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
					// skip duplicates
					while (lo < hi && nums[lo] == nums[lo + 1])
						lo++;
					// skip duplicates
					while (lo < hi && nums[hi] == nums[hi - 1])
						hi--;
					lo++;
					hi--;
				} else if (sum > target) {
					hi--;
				} else {
					lo++;
				}
			}
		}

		return result;
	}

	/**
	 * Given an array S of n integers, find three integers in S such that the sum is closest to a
	 * given number, target. Return the sum of the three integers. You may assume that each input
	 * would have exactly one solution.
	 *
	 * For example, given array S = {-1 2 1 -4}, and target = 1.
	 *
	 * The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
	 *
	 */
	public static int threeSumClosest(int[] nums, int target) {
		if (nums == null || nums.length < 3)
			return 0;
		Arrays.sort(nums);
		int result = nums[0] + nums[1] + nums[2];
		for (int i = 0; i < nums.length - 2; i++) {
			int lo = i + 1, hi = nums.length - 1;
			while (lo < hi) {
				int sum = nums[i] + nums[lo] + nums[hi];
				if (sum > target)
					hi--;
				else
					lo++;
				if (Math.abs(sum - target) < Math.abs(result - target))
					result = sum;
			}
		}
		return result;
	}

	/**
	 * Given an array of n integers nums and a target, find the number of index triplets i, j, k
	 * with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
	 *
	 * <pre>
	For example, given nums = [-2, 0, 1, 3], and target = 2.

	Return 2. Because there are two triplets which sums are less than 2:

	[-2, 0, 1]
	[-2, 0, 3]
	 * </pre>
	 */
	public static int threeSumSmaller(int[] nums, int target) {
		if (nums == null || nums.length < 3)
			return 0;

		Arrays.sort(nums);

		int result = 0;
		for (int i = 0; i < nums.length - 2; i++) {
			int lo = i + 1, hi = nums.length - 1;
			while (lo < hi) {
				int sum = nums[i] + nums[lo] + nums[hi];
				if (sum < target) {
					result += hi - lo;
					lo++;
				} else {
					hi--;
				}
			}
		}

		return result;
	}

	/**
	 * <pre>
	Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

	Note: The solution set must not contain duplicate quadruplets.

	For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

	A solution set is:
	[
	[-1,  0, 0, 1],
	[-2, -1, 1, 2],
	[-2,  0, 0, 2]
	]
	 * </pre>
	 *
	 */
	public List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> result = new ArrayList<>();
		if (nums == null || nums.length < 4)
			return result;
		Arrays.sort(nums);
		int len = nums.length;

		for (int i = 0; i < nums.length - 3; i++) {
			if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
				break;
			if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)
				continue;
			if (i > 0 && nums[i] == nums[i - 1])
				continue;
			for (int j = i + 1; j < nums.length - 2; j++) {
				if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
					break;
				if (nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target)
					continue;
				if (j > i + 1 && nums[j] == nums[j - 1])
					continue;
				int lo = j + 1, hi = nums.length - 1;
				while (lo < hi) {
					int sum = nums[i] + nums[j] + nums[lo] + nums[hi];
					if (sum == target) {
						result.add(Arrays.asList(nums[i], nums[j], nums[lo], nums[hi]));
						while (lo < hi && nums[lo] == nums[lo + 1])
							lo++;
						while (lo < hi && nums[hi] == nums[hi - 1])
							hi--;
						lo++;
						hi--;
					} else if (sum > target)
						hi--;
					else
						lo++;
				}
			}
		}

		return result;
	}

	/**
	 * Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are
	 * such that A[i] + B[j] + C[k] + D[l] is zero.
	 *
	 * To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All
	 * integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 -
	 * 1.
	 *
	 */
	public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
		Map<Integer, Integer> map = new HashMap<>();

		for (int i = 0; i < C.length; i++) {
			for (int j = 0; j < D.length; j++) {
				int sum = C[i] + D[j];
				map.put(sum, map.getOrDefault(sum, 0) + 1);
			}
		}

		int result = 0;
		for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < B.length; j++) {
				int sum = A[i] + B[j];
				result += map.getOrDefault(-1 * sum, 0);
			}
		}

		return result;
	}

	public static void main(String[] args) {
		int[] nums = { -1, 0, 1, 2, -1, -4 };
		List<List<Integer>> result = threeSumEquals(nums, 0);
		assert result.toString().equals("[[-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]");
		nums = new int[] { -1, 2, 1, -4 };
		assert threeSumClosest(nums, 1) == 2;
		nums = new int[] { -2, 0, 1, 3 };
		assert threeSumSmaller(nums, 2) == 2;
	}
}

public int maxTrappedWaterInLines(List<Integer> heights) {
	int i = 0, j = heights.size() - 1, maxWater = 0;
	while (i < j) {
		int width = j - i;
		maxWater = Math.max(maxWater, width * Math.min(heights.get(i), heights.get(j)));
		if (heights.get(i) > heights.get(j))
			j--;
		else
			i++;
	}
	return maxWater;
}

public static int computeHistogramVolume(int[] heights) {
	int a = 0;
	int b = heights.length - 1;
	int max = 0;
	int leftMax = 0;
	int rightMax = 0;
	while (a <= b) {
		leftMax = Math.max(leftMax, heights[a]);
		rightMax = Math.max(rightMax, heights[b]);
		if (leftMax < rightMax) {
			max += (leftMax - heights[a]);
			a++;
		} else {
			max += (rightMax - heights[b]);
			b--;
		}
	}
	return max;
}

public static int computeHistogramVolume2(int[] heights) {
	Deque<Integer> stack = new ArrayDeque<>();
	int max = 0;
	int current = 0;
	while (current < heights.length) {
		while (!stack.isEmpty() && heights[current] > heights[stack.peek()]) {
			int top = stack.pop();
			if (stack.isEmpty())
				break;
			int distance = current - stack.peek() - 1;
			int height = Math.min(heights[current], heights[stack.peek()]) - heights[top];
			max += height * distance;
		}
		stack.push(current++);
	}
	return max;
}

public class TrappingRainWaterII {
    public class Cell {
        int row;
        int col;
        int height;

        public Cell(int row, int col, int height) {
            this.row = row;
            this.col = col;
            this.height = height;
        }
    }

    public int trapRainWater(int[][] heights) {
        if (heights == null || heights.length == 0 || heights[0].length == 0)
            return 0;

        Queue<Cell> queue = new PriorityQueue<>(1, new Comparator<Cell>() {
            public int compare(Cell a, Cell b) {
                return a.height - b.height;
            }
        });

        int m = heights.length;
        int n = heights[0].length;
        boolean[][] visited = new boolean[m][n];

        // Initially, add all the Cells which are on borders to the queue.
        for (int i = 0; i < m; i++) {
            visited[i][0] = true;
            visited[i][n - 1] = true;
            queue.offer(new Cell(i, 0, heights[i][0]));
            queue.offer(new Cell(i, n - 1, heights[i][n - 1]));
        }

        for (int i = 0; i < n; i++) {
            visited[0][i] = true;
            visited[m - 1][i] = true;
            queue.offer(new Cell(0, i, heights[0][i]));
            queue.offer(new Cell(m - 1, i, heights[m - 1][i]));
        }

        // from the borders, pick the shortest cell visited and check its neighbors:
        // if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped
        // add all its neighbors to the queue.
        int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        int result = 0;
        while (!queue.isEmpty()) {
            Cell cell = queue.poll();
            for (int[] dir : dirs) {
                int row = cell.row + dir[0];
                int col = cell.col + dir[1];
                if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col]) {
                    visited[row][col] = true;
                    result += Math.max(0, cell.height - heights[row][col]);
                    queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height)));
                }
            }
        }

        return result;
    }
}

  public static int[] pourWaterInHistogram(int[] heights, int units, int index) {
    while (units-- > 0) {
      boolean foundBest = false;
      for (int dir : new int[] { -1, 1 }) {
        // two pointers shit together
        int i = index, j = index + dir, best = index;
        while (0 <= j && j < heights.length && heights[j] <= heights[i]) {
          if (heights[j] < heights[i])
            best = j;
          i = j;
          j += dir;
        }
        // break if found the best
        if (best != index) {
          heights[best]++;
          foundBest = true;
          break;
        }
      }
      // Otherwise pour straight down
      if (!foundBest) {
        heights[index]++;
      }
    }
    return heights;
  }


public static void printTerrian() {
		int[] terrain = { 5, 4, 2, 1, 2, 3, 2, 1, 0, 1, 2, 4 };
		int m = Arrays.stream(terrain).max().getAsInt() + 1;
		int n = terrain.length;
		char[][] grid = new char[m][n];
		for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
						if (i >= m - terrain[j] - 1)
								grid[i][j] = '+';
						else
								grid[i][j] = ' ';
				}
		}
		for (char[] row : grid) {
				System.out.println(Arrays.toString(row));
		}
}

public int candy(int[] ratings) {
	int[] candies = new int[ratings.length];
	Arrays.fill(candies, 1);
	for (int i = 1; i < ratings.length; i++) {
		if (ratings[i] > ratings[i - 1]) {
			candies[i] = candies[i - 1] + 1;
		}
	}
	int sum = candies[ratings.length - 1];
	for (int i = ratings.length - 2; i >= 0; i--) {
		if (ratings[i] > ratings[i + 1]) {
			// makes it satisfy both left and right neighbor criteria
			candies[i] = Math.max(candies[i], candies[i + 1] + 1);
		}
		sum += candies[i];
	}
	return sum;
}

public int candy2(int[] ratings) {
	if (ratings == null || ratings.length == 0)
		return 0;
	int start = 0, sum = 0, len = ratings.length;
	while (start < len) {
		if (start + 1 < len && ratings[start] == ratings[start + 1]) {
			sum += 1;
			start++;
			continue;
		}
		// left means the left part of the mountain,right means the right part of the mountain
		int left = 0, right = 0;
		// climbing up
		while (start + 1 < len && ratings[start] < ratings[start + 1]) {
			start++;
			left++;
		}
		// falling down
		while (start + 1 < len && ratings[start] > ratings[start + 1]) {
			start++;
			right++;
		}
		// break for flat point
		if (left == 0 && right == 0) {
			sum += 1;
			break;
		}
		// calculate for mountain
		int max = Math.max(left, right) + 1;
		int leftSum = (1 + left) * left / 2;
		int rightSum = (1 + right) * right / 2 - 1;
		sum += max + leftSum + rightSum;
	}
	return sum;
}

  /**
   * You are given an integer array nums. You are initially positioned at the array's first index, and
   * each element in the array represents your maximum jump length at that position.
   * 
   * Return true if you can reach the last index, or false otherwise.
   * 
   * Solution: could use recursive backtracking + memoization array; top-down or bottom-up dynamic
   * programming; track the furthest position
   */
  // Top-down dynamic programming (Greedy)
  public boolean canJump(int[] nums) {
    int pos = 0;
    for (int i = 0; i < nums.length; i++) {
      if (pos >= nums.length - 1) {
        return true;
      } else if (i > pos) {
        return false;
      } else {
        pos = Math.max(pos, i + nums[i]);
      }
    }
    return false;
  }

  // Bottom-up dynamic programming
  public boolean canJump2(int[] nums) {
    int lastPos = nums.length - 1;
    for (int i = nums.length - 1; i >= 0; i--) {
      if (i + nums[i] >= lastPos) {
        lastPos = i;
      }
    }
    return lastPos == 0;
  }

  /**
   * Given an array of non-negative integers nums, you are initially positioned at the first index of
   * the array.
   * 
   * Each element in the array represents your maximum jump length at that position.
   * 
   * Your goal is to reach the last index in the minimum number of jumps.
   * 
   * You can assume that you can always reach the last index.
   * 
   * Solution: Greedy dynamic programming, please note that we exclude the last element from our
   * iteration because as soon as we reach the last element, we do not need to jump anymore.
   */
  public int jump(int[] nums) {
    int jumps = 0, currentJumpEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
      // we continuously find the how far we can reach in the current jump
      farthest = Math.max(farthest, i + nums[i]);
      // if we have come to the end of the current jump,
      // we need to make another jump
      if (i == currentJumpEnd) {
        jumps++;
        currentJumpEnd = farthest;
      }
    }
    return jumps;
  }

  /**
   * Given an array of non-negative integers arr, you are initially positioned at start index of the
   * array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach
   * to any index with value 0.
   * 
   * Notice that you can not jump outside of the array at any time.
   * 
   * Solution: Use either BFS or DFS
   */
  public boolean canReach(int[] arr, int start) {
    if (start >= 0 && start < arr.length) {
      if (arr[start] < 0) {
        return false; // visited
      }
      if (arr[start] == 0) {
        return true; // reached
      }
      arr[start] *= -1; // mark as visited
      return canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]);
    }
    return false;
  }

  /**
   * Given an array of integers arr, you are initially positioned at the first index of the array.
   * 
   * In one step you can jump from index i to index: Notice that you can not jump outside of the array
   * at any time.
   * 
   * In one step you can jump from index i to index: <br>
   * 
   * i + 1 where: i + 1 < arr.length. <br>
   * i - 1 where: i - 1 >= 0. <br>
   * j where: arr[i] == arr[j] and i != j. <br>
   * Return the minimum number of steps to reach the last index of the array.
   * 
   * 
   * Solution: Breadth-First Search or Bidirectional BFS
   */
  public int minJumps(int[] arr) {
    if (arr == null || arr.length < 2) {
      return 0;
    }

    Map<Integer, List<Integer>> graph = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
      graph.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
    }

    // int[] {jumpIndex, jumpTimes}
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[] { 0, 0 });
    boolean[] visited = new boolean[arr.length];
    visited[0] = true;

    while (!queue.isEmpty()) {
      for (int i = 0; i < queue.size(); i++) {
        int[] pair = queue.poll();
        if (pair[0] == arr.length - 1) {
          return pair[1];
        }
        int value = arr[pair[0]];
        List<Integer> neighbors = graph.get(value);
        neighbors.add(pair[0] - 1);
        neighbors.add(pair[0] + 1);
        neighbors.forEach(pos ->
          {
            if (pos >= 0 && pos < arr.length && !visited[pos]) {
              queue.offer(new int[] { pos, pair[1] + 1 });
              visited[pos] = true;
            }
          });
        // Clear to prevent stepping back
        neighbors.clear();
      }
    }

    return 0;
  }

  /**
   * Given an array of integers arr and an integer d. In one step you can jump from index i to index:
   * 
   * i + x where: i + x < arr.length and 0 < x <= d. <br>
   * i - x where: i - x >= 0 and 0 < x <= d. <br>
   * In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for
   * all indices k between i and j (More formally min(i, j) < k < max(i, j)).
   * 
   * You can choose any index of the array and start jumping. Return the maximum number of indices you
   * can visit.
   * 
   * Notice that you can not jump outside of the array at any time.
   * 
   * Solution: Longest path in a DAG(Directed Acyclic Graph) O(n*d)
   * 
   * https://leetcode.com/problems/jump-game-v/
   */
  public int maxJumps(int[] arr, int d) {
    int dp[] = new int[arr.length];

    int maxJump = 0;
    for (int i = 0; i < arr.length; i++) {
      maxJump = Math.max(maxJump, longestJump(i, arr, dp, d));
    }
    return maxJump;

  }

  private int longestJump(int start, int[] arr, int[] dp, int d) {
    if (dp[start] != 0)
      return dp[start];
    dp[start] = 1;

    int leftBound = Math.max(start - d, 0);
    int rightBound = Math.min(start + d, arr.length - 1);

    // scan left
    for (int i = start - 1; i >= leftBound; i--) {
      if (arr[i] >= arr[start])
        break;
      dp[start] = Math.max(dp[start], longestJump(i, arr, dp, d) + 1);
    }

    // scan right
    for (int i = start + 1; i <= rightBound; i++) {
      if (arr[i] >= arr[start])
        break;
      dp[start] = Math.max(dp[start], longestJump(i, arr, dp, d) + 1);
    }

    return dp[start];
  }

  /**
   * You are given a 0-indexed integer array nums and an integer k.
   * 
   * You are initially standing at index 0. In one move, you can jump at most k steps forward without
   * going outside the boundaries of the array. That is, you can jump from index i to any index in the
   * range [i + 1, min(n - 1, i + k)] inclusive.
   * 
   * You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j]
   * for each index j you visited in the array.
   * 
   * Return the maximum score you can get.
   * 
   * Solution: Dynamic Programming + Deque (Compressed) + Sliding Window Maximum; <br>
   * Time/Space Complexity: O(N)/O(k)
   * 
   * https://leetcode.com/problems/jump-game-vi/ <br>
   * https://codebycase.github.io/algorithm/a15-the-honors-question.html#sliding-window-maximum
   * 
   */
  public int maxResult(int[] nums, int k) {
    // score represents the max score we can get starting at index i
    // score[i] = max(score[i-k], ..., score[i-1]) + nums[i]
    int score = nums[0];
    Deque<int[]> deque = new LinkedList<>();
    deque.offerLast(new int[] { 0, score });
    for (int i = 1; i < nums.length; i++) {
      // Pop all the indexes smaller than i-k out of deque from top
      while (deque.peekFirst() != null && deque.peekFirst()[0] < i - k) {
        deque.pollFirst();
      }
      score = deque.peekFirst()[1] + nums[i];
      // Keep the maximum value always at the top of the queue.
      while (deque.peekLast() != null && score >= deque.peekLast()[1]) {
        deque.pollLast();
      }
      deque.offerLast(new int[] { i, score });
    }
    return score;
  }

  /**
   * You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning,
   * you are standing at index 0, which is equal to '0'. You can move from index i to index j if the
   * following conditions are fulfilled:
   * 
   * i + minJump <= j <= min(i + maxJump, s.length - 1), <br>
   * and s[j] == '0'.
   * 
   * Return true if you can reach index s.length - 1 in s, or false otherwise.
   * 
   * https://leetcode.com/problems/jump-game-vii/
   */
  public boolean canReach(String s, int minJump, int maxJump) {
    int farthest = 0;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(0);

    while (!queue.isEmpty()) {
      int curr = queue.poll();
      int start = Math.max(curr + minJump, farthest + 1);
      int end = Math.min(s.length(), curr + maxJump + 1);
      for (int j = start; j < end; j++) {
        if (s.charAt(j) == '0') {
          if (j == s.length() - 1) {
            return true;
          }
          queue.offer(j);
        }
      }
      farthest = Math.max(farthest, curr + maxJump);
    }

    return false;
  }

public boolean canCross(int[] stones) {
	int[][] memo = new int[stones.length][stones.length];
	for (int[] row : memo) {
		Arrays.fill(row, -1);
	}
	return canCross(stones, 0, 0, memo) == 1;
}

public int canCross(int[] stones, int index, int jumpsize, int[][] memo) {
	if (memo[index][jumpsize] >= 0) {
		return memo[index][jumpsize];
	}
	int ind1 = Arrays.binarySearch(stones, index + 1, stones.length, stones[index] + jumpsize);
	if (ind1 >= 0 && canCross(stones, ind1, jumpsize, memo) == 1) {
		memo[index][jumpsize] = 1;
		return 1;
	}
	int ind2 = Arrays.binarySearch(stones, index + 1, stones.length, stones[index] + jumpsize - 1);
	if (ind2 >= 0 && canCross(stones, ind2, jumpsize - 1, memo) == 1) {
		memo[index][jumpsize - 1] = 1;
		return 1;
	}
	int ind3 = Arrays.binarySearch(stones, index + 1, stones.length, stones[index] + jumpsize + 1);
	if (ind3 >= 0 && canCross(stones, ind3, jumpsize + 1, memo) == 1) {
		memo[index][jumpsize + 1] = 1;
		return 1;
	}
	memo[index][jumpsize] = ((index == stones.length - 1) ? 1 : 0);
	return memo[index][jumpsize];
}

public boolean canCross2(int[] stones) {
	Map<Integer, Set<Integer>> map = new HashMap<>();
	for (int i = 0; i < stones.length; i++) {
		map.put(stones[i], new HashSet<Integer>());
	}
	map.get(0).add(0);
	for (int i = 0; i < stones.length; i++) {
		// for each stone, calculate next stones it can reach
		for (int k : map.get(stones[i])) {
			for (int step = k - 1; step <= k + 1; step++) {
				if (step > 0 && map.containsKey(stones[i] + step)) {
					map.get(stones[i] + step).add(step);
				}
			}
		}
	}
	return map.get(stones[stones.length - 1]).size() > 0;
}