import java.util.Map;
import java.util.HashMap;

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length())
            return "";
        Map<Character, Integer> charCount = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            charCount.put(t.charAt(i), charCount.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0, count = 0, minLeft = 0, minRight = 0, min = Integer.MAX_VALUE;
        while (right < s.length()) {
            if (charCount.containsKey(s.charAt(right))) {
                charCount.put(s.charAt(right), charCount.get(s.charAt(right)) - 1);
                if (charCount.get(s.charAt(right)) >= 0) {
                    count += 1;
                }
            }

            while (count == t.length() && left <= right) {
                if (right - left + 1 < min) {
                    minLeft = left;
                    minRight = right + 1;
                    min = right - left + 1;
                }
                if (charCount.containsKey(s.charAt(left))) {
                    charCount.put(s.charAt(left), charCount.get(s.charAt(left)) + 1);
                    if (charCount.get(s.charAt(left)) > 0) {
                        count -= 1;
                    }
                }
                left += 1;
            }
            right += 1;
        }
        return min != Integer.MAX_VALUE ? s.substring(minLeft, minRight) : "";
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < dp[0].length; i++) {
            if (obstacleGrid[0][i] == 1)
                break;
            dp[0][i] = 1;
        }
        for (int i = 0; i < dp.length; i++) {
            if (obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length && i <= maxReach; i++) {
            maxReach = Math.max(i + nums[i], maxReach);
            if (maxReach >= nums.length - 1)
                return true;
        }
        return maxReach >= nums.length - 1;
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0)
            return new ArrayList<>();
        int left = 0, right = matrix[0].length - 1, up = 0, down = matrix.length - 1;
        List<Integer> result = new ArrayList<>();
        while (left <= right && up <= down) {
            for (int i = left; i <= right; i++) {
                result.add(matrix[up][i]);
            }
            for (int i = up + 1; i <= down; i++) {
                result.add(matrix[i][right]);
            }
            if (up != down) {
                for (int i = right - 1; i >= left; i--) {
                    result.add(matrix[down][i]);
                }
            }
            if (left != right) {
                for (int i = down - 1; i > up; i--) {
                    result.add(matrix[i][left]);
                }
            }
            left += 1;
            right -= 1;
            up += 1;
            down -= 1;
        }
        return result;
    }
}

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), nums, 0);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> curr, int[] nums, int pos) {
        if (pos == nums.length) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            if (i > pos && nums[i - 1] == nums[i]) {
                continue;
            }
            curr.add(nums[i]);
            helper(ans, curr, nums, i + 1);
            curr.remove(curr.size() - 1);
        }
        ans.add(new ArrayList<>(curr));
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedString = new String(charArray);
            map.putIfAbsent(sortedString, new ArrayList<>());
            map.get(sortedString).add(str);
        }
        return new ArrayList<>(map.values());

    }
}

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Map<Integer, Set<Character>> rowRecorder = new HashMap<>();
        Map<Integer, Set<Character>> colRecorder = new HashMap<>();
        Map<Integer, Set<Character>> boxRecorder = new HashMap<>();
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (board[row][col] != '.') {
                    rowRecorder.putIfAbsent(row, new HashSet<>());
                    colRecorder.putIfAbsent(col, new HashSet<>());
                    int boxIndex = (row / 3) * 3 + col / 3;
                    boxRecorder.putIfAbsent(boxIndex, new HashSet<>());
                    if (!rowRecorder.get(row).add(board[row][col]) || !colRecorder.get(col).add(board[row][col])
                            || !boxRecorder.get(boxIndex).add(board[row][col])) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

public class Solution {
    public int[] searchRange(int[] a, int target) {

        int[] result = { -1, -1 };

        if (a == null || a.length == 0)
            return result;

        result[0] = findStartPosition(a, target);
        result[1] = findEndPosition(a, target);

        return result;
    }

    public int findStartPosition(int[] a, int target) {

        int left = 0;
        int right = a.length - 1;
        int start = -1;

        while (left <= right) {

            int mid = left + (right - left) / 2;

            if (a[mid] == target) {
                start = mid; // this is start
                right = mid - 1; // lets see if there one more on the left
            } else if (target > a[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return start;
    }

    public int findEndPosition(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;
        int end = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (a[mid] == target) {
                end = mid; // this is the end
                left = mid + 1; // lets see if there is one more on the right
            } else if (target > a[mid])
                left = mid + 1;
            else
                right = mid - 1;

        }

        return end;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2)
            return;
        int pos = nums.length - 2;
        while (pos >= 0 && nums[pos] >= nums[pos + 1]) {
            pos -= 1;
        }
        if (pos != -1) {
            int ptr = nums.length - 1;
            while (nums[ptr] <= nums[pos]) {
                ptr -= 1;
            }
            swap(nums, pos, ptr);
        }
        int left = pos + 1;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left += 1;
            right -= 1;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}