import java.util.*;
class permuteUnique {
    public static class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            while (true) {
                res.add(getList(nums));
                if (!nextPermutation(nums)) {
                    break;
                }
            }
            return res;
        }
        private List<Integer> getList(int[] nums) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            return list;
        }
        private boolean nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i < 0) {
                return false;
            }
            int j = nums.length - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
            reverse(nums, i + 1);
            return true;
        }
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        private void reverse(int[] nums, int start) {
            int i = start, j = nums.length - 1;
            while (i < j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {1,1,2};
        System.out.println(s.permuteUnique(nums));
        int[] nums2 = {1,2,3};
        System.out.println(s.permuteUnique(nums2));
   }
}

import java.util.*;
class numIslands {
    public static class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int islandNum = 0;
            int[] dx = {0, 0, -1, 1};
            int[] dy = {-1, 1, 0, 0};
            Queue<int[]> queue = new LinkedList<>();
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && !visited[i][j]) {
                        islandNum++;
                        visited[i][j] = true;
                        queue.offer(new int[]{i, j});
                        while (!queue.isEmpty()) {
                            int[] curr = queue.poll();
                            for (int k = 0; k < 4; k++) {
                                int x = curr[0] + dx[k];
                                int y = curr[1] + dy[k];
                                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !visited[x][y]) {
                                    visited[x][y] = true;
                                    queue.offer(new int[]{x, y});
                                }
                            }
                        }
                    }
                }
            }
            return islandNum;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] grid = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}};
        System.out.println(s.numIslands(grid));
        char[][] grid2 = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}};
        System.out.println(s.numIslands(grid2));
   }
}

import java.util.*;
class isValidSudoku {
    public static class Solution {
        public boolean isValidSudoku(char[][] board) {
            Map<Integer, Set<Character>> rows = new HashMap<>();
            Map<Integer, Set<Character>> cols = new HashMap<>();
            Map<Integer, Set<Character>> boxes = new HashMap<>();
            for (int i = 0; i < 9; i++) {
                rows.put(i, new HashSet<>());
                cols.put(i, new HashSet<>());
                boxes.put(i, new HashSet<>());
            }
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    char num = board[i][j];
                    if (num == '.') {
                        continue;
                    }
                    if (rows.get(i).contains(num) || cols.get(j).contains(num) || boxes.get((i / 3) * 3 + j / 3).contains(num)) {
                        return false;
                    }
                    rows.get(i).add(num);
                    cols.get(j).add(num);
                    boxes.get((i / 3) * 3 + j / 3).add(num);
                }
            }
            return true;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] board = {
            {'5','3','.','.','7','.','.','.','.'},
            {'6','.','.','1','9','5','.','.','.'},
            {'.','9','8','.','.','.','.','6','.'},
            {'8','.','.','.','6','.','.','.','3'},
            {'4','.','.','8','.','3','.','.','1'},
            {'7','.','.','.','2','.','.','.','6'},
            {'.','6','.','.','.','.','2','8','.'},
            {'.','.','.','4','1','9','.','.','5'},
            {'.','.','.','.','8','.','.','7','9'}};
        System.out.println(s.isValidSudoku(board));
        char[][] board2 = {
            {'8','3','.','.','7','.','.','.','.'},
            {'6','.','.','1','9','5','.','.','.'},
            {'.','9','8','.','.','.','.','6','.'},
            {'8','.','.','.','6','.','.','.','3'},
            {'4','.','.','8','.','3','.','.','1'},
            {'7','.','.','.','2','.','.','.','6'},
            {'.','6','.','.','.','.','2','8','.'},
            {'.','.','.','4','1','9','.','.','5'},
            {'.','.','.','.','8','.','.','7','9'}};
        System.out.println(s.isValidSudoku(board2));
   }
}