@franz.sarmiento I understand the problem's description and solution, but it looks really really unreasonable(fair) to me!
airwindow
@airwindow
Posts made by airwindow

RE: Why two adjacent children with equal rating don't get equal candies?

Test case 61  Help!
For the test case 61,
[[0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1]]
[29,18]
[14,22]The expected output is,
"ururulululululurul"while my solution outputs,
"urululurdrulululul"They both takes 43 steps to reach the hole. It looks to me the expected output is not the lowest (in alphabet order) movement string.
public String findShortestWay(int[][] maze, int[] ball, int[] hole) { int m = maze.length, n = maze[0].length; int[][] min_dist = new int[m][n]; String[][] min_path = new String[m][n]; min_path[hole[0]][hole[1]] = ""; boolean[][] visited = new boolean[m][n]; char[] dirs = {'d', 'l', 'r', 'u'}; HashMap<Character, int[]> dir_map = new HashMap<Character, int[]> (); dir_map.put('d', new int[] {1, 0}); dir_map.put('l', new int[] {0, 1}); dir_map.put('r', new int[] {0, 1}); dir_map.put('u', new int[] {1, 0}); visited[ball[0]][ball[1]] = true; dfs(maze, ball, hole, min_dist, min_path, visited, dirs, dir_map); return min_dist[ball[0]][ball[1]] == Integer.MAX_VALUE ? "impossible" : min_path[ball[0]][ball[1]]; } private int dfs(int[][] maze, int[] ball, int[] hole, int[][] min_dist, String[][] min_path, boolean[][] visited, char[] dirs, HashMap<Character, int[]> dir_map) { int i = ball[0], j = ball[1]; if (min_dist[i][j] != 0) { return min_dist[i][j]; } min_dist[i][j] = Integer.MAX_VALUE; for (char dir_c : dirs) { int[] dir = dir_map.get(dir_c); int cur_to_next_dist = 0; int x = ball[0] + dir[0], y = ball[1] + dir[1]; while (x !=  1 && x != maze.length && y != 1 && y != maze[0].length && maze[x][y] == 0) { cur_to_next_dist++; if (x == hole[0] && y == hole[1]) { min_dist[i][j] = cur_to_next_dist; min_path[i][j] = String.valueOf(dir_c); return cur_to_next_dist; } x += dir[0]; y += dir[1]; } x = dir[0]; y = dir[1]; if (!visited[x][y]) { visited[x][y] = true; int next_to_hole_dist = dfs(maze, new int[]{x, y}, hole, min_dist, min_path, visited, dirs, dir_map); if (next_to_hole_dist != Integer.MAX_VALUE && cur_to_next_dist + next_to_hole_dist < min_dist[i][j]) { min_dist[i][j] = cur_to_next_dist + next_to_hole_dist; min_path[i][j] = String.valueOf(dir_c) + min_path[x][y]; } visited[x][y] = false; } } return min_dist[i][j]; }

RE: Java Easy to understand O(n logn), beats 90%
I think the time complexity of your solution is actually O(n).
The most time consuming part:
for(int i=0; i<s.length(); i++){
...
}
Since the Entry[] contains fixed 256 element, you can treat the sorting cost over it as constant, which is O(1). 
DP solution with O(n) space complexity
public int uniquePaths(int m, int n) { if (m <= 0  n <= 0) { return 0; } int[] counts = new int[n]; counts[0] = 1; /*transitional function: counts(i, j) = counts(i, j1) + counts(i1, j)*/ for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { counts[j] = counts[j  1] + counts[j]; } } return counts[n  1]; }

Java dp solution with constant space
public class Solution {public int numDecodings(String s) { if (s == null  s.length() == 0  s.startsWith("0")) { return 0; } int pre_1_cnt = 1; int pre_2_cnt = 1; int num1 = 0, num2 = 0, cur_cnt = 1; /* transitional function: cnt(i) = cnt(i1) + cnt(i2) note: to account for cnt(i1), num[i] must be in the valid range [1, 9] to account for cnt(i2), num[i1, i] must be in the valid range[10, 26] */ for (int i = 1; i < s.length(); i++) { cur_cnt = 0; num1 = Integer.valueOf(s.substring(i, i+1)); num2 = Integer.valueOf(s.substring(i1, i+1)); if (num1 > 0) { cur_cnt += pre_1_cnt; } if (num2 >= 10 && num2 <= 26) { cur_cnt += pre_2_cnt; } pre_2_cnt = pre_1_cnt; pre_1_cnt = cur_cnt; } return cur_cnt; }

A clear recursive and DP method in Java
public int coinChange(int[] coins, int amount) { if (coins == null  coins.length == 0  amount <= 0) { return 0; } int[] min = new int[amount + 1]; Arrays.fill(min, Integer.MAX_VALUE); min[0] = 0; helper(amount, coins, min); return min[amount]; } public void helper(int amount, int[] coins, int[] min) { if (amount == 0) { return; } /* test if min[amount] has alreay been explored min[i] = 1: explored, but no combination for it. min[i] = Integer.MAX_VALUE: not explored. */ if (min[amount] != Integer.MAX_VALUE) { return; } int min_count = Integer.MAX_VALUE; for (int coin : coins) { if (amount  coin >= 0) { helper(amount  coin, coins, min); if (min[amount  coin] != 1 && min[amount  coin] + 1 < min_count) { min_count = min[amount  coin] + 1; } } } min[amount] = (min_count == Integer.MAX_VALUE ? 1 : min_count); }

Java concise solution with O(n) complexity
public int minSubArrayLen(int s, int[] nums) { if (nums == null  nums.length == 0) { return 0; } int minLen = Integer.MAX_VALUE; int start = 0; int localSum = 0; for (int end = 0; end < nums.length; end++) { localSum += nums[end]; while (localSum >= s) { minLen = Math.min(minLen, end  start + 1); localSum = nums[start++]; } } return minLen == Integer.MAX_VALUE ? 0 : minLen; }