class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int first = binarySearchFloor(nums, target);
        if (first == -1)
            return false;
        int second = first + nums.length / 2;
        if (second >= nums.length || nums[second] != target)
            return false;
        return true;
    }

    private int binarySearchFloor(int[] nums, int target) {
        int left = 0, right = nums.length - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution {
    public String reorganizeString(String s) {
        int[] charCount = new int[26];
        char[] sArray = s.toCharArray();
        int max = 0;
        char maxChar = '*';
        for (int i = 0; i < sArray.length; i++) {
            char currChar = sArray[i];
            charCount[currChar - 'a'] += 1;
            if (charCount[currChar - 'a'] > max) {
                max = charCount[currChar - 'a'];
                maxChar = currChar;
            }
        }
        if (max > (s.length() + 1) / 2)
            return "";
        char[] ans = new char[s.length()];
        int index = 0;
        while (charCount[maxChar - 'a'] > 0) {
            ans[index] = maxChar;
            charCount[maxChar - 'a'] -= 1;
            index += 2;
        }
        int ptr = 0;
        while (ptr < charCount.length) {
            while (charCount[ptr] > 0) {
                if (index >= s.length()) {
                    index = 1;
                }
                ans[index] = (char) ('a' + ptr);
                charCount[ptr] -= 1;
                index += 2;
            }
            ptr += 1;
        }
        return String.valueOf(ans);
    }
}

class Solution {
    public int numOfWays(int n) {
        long allDiff = 6, alternate = 6, modulo = (long) 1e9 + 7;
        for (int i = 1; i < n; i++) {
            long nextAllDiff = allDiff * 3 + alternate * 2;
            long nextAlternate = allDiff * 2 + alternate * 2;
            allDiff = nextAllDiff % modulo;
            alternate = nextAlternate % modulo;
        }
        return (int) ((allDiff + alternate) % modulo);
    }
}

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        TreeMap<Integer, Integer> cardFreq = new TreeMap<>();
        for (int card : hand) {
            cardFreq.put(card, cardFreq.getOrDefault(card, 0) + 1);
        }
        while (!cardFreq.isEmpty()) {
            int lowest = cardFreq.firstKey();
            for (int i = 0, currNum = lowest; i < groupSize; i++) {
                if (!cardFreq.containsKey(currNum) || cardFreq.get(currNum) <= 0) {
                    return false;
                }
                cardFreq.put(currNum, cardFreq.get(currNum) - 1);
                if (cardFreq.get(currNum) <= 0) {
                    cardFreq.remove(currNum);
                }
                currNum += 1;
            }
        }
        return true;
    }
}

class Solution {
    private static class Cell {
        int row;
        int col;
        int height;

        Cell(int _row, int _col, int _height) {
            row = _row;
            col = _col;
            height = _height;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        PriorityQueue<Cell> pq = new PriorityQueue<>((a, b) -> a.height - b.height);
        boolean[][] visited = new boolean[heightMap.length][heightMap[0].length];
        for (int i = 0; i < heightMap[0].length; i++) {
            pq.offer(new Cell(0, i, heightMap[0][i]));
            visited[0][i] = true;
            pq.offer(new Cell(heightMap.length - 1, i, heightMap[heightMap.length - 1][i]));
            visited[heightMap.length - 1][i] = true;
        }
        for (int i = 1; i < heightMap.length - 1; i++) {
            pq.offer(new Cell(i, 0, heightMap[i][0]));
            visited[i][0] = true;
            pq.offer(new Cell(i, heightMap[0].length - 1, heightMap[i][heightMap[0].length - 1]));
            visited[i][heightMap[0].length - 1] = true;
        }
        int ans = 0;
        int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
        while (!pq.isEmpty()) {
            Cell currCell = pq.poll();
            for (int[] direction : directions) {
                int newRow = currCell.row + direction[0];
                int newCol = currCell.col + direction[1];
                if (!isOutOfBound(heightMap, newRow, newCol) && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    ans += Math.max(0, currCell.height - heightMap[newRow][newCol]);
                    pq.offer(new Cell(newRow, newCol, Math.max(currCell.height, heightMap[newRow][newCol])));
                }
            }
        }
        return ans;
    }

    private boolean isOutOfBound(int[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}

class Solution {
    public boolean isNumber(String s) {
        boolean seenDigit = false;
        boolean seenDot = false;
        boolean seenExp = false;
        char[] sArray = s.toCharArray();
        for (int i = 0; i < sArray.length; i++) {
            if (Character.isDigit(sArray[i])) {
                seenDigit = true;
            } else if (sArray[i] == '+' || sArray[i] == '-') {
                if (i > 0 && sArray[i - 1] != 'e' && sArray[i - 1] != 'E') {
                    return false;
                }
            } else if (sArray[i] == '.') {
                if (seenDot || seenExp) {
                    return false;
                }
                seenDot = true;
            } else if (sArray[i] == 'e' || sArray[i] == 'E') {
                if (seenExp || !seenDigit) {
                    return false;
                }
                seenExp = true;
                seenDigit = false;
            } else {
                return false;
            }
        }
        return seenDigit;
    }
}

class MyCircularQueue {
    private int[] circularQueue;
    private int count;
    private int start;
    private int end;

    public MyCircularQueue(int k) {
        circularQueue = new int[k];
        start = 0;
        end = 0;
        count = 0;
    }

    public boolean enQueue(int value) {
        if (count == circularQueue.length) {
            return false;
        }
        circularQueue[end] = value;
        end = end == circularQueue.length - 1 ? 0 : end + 1;
        count += 1;
        return true;
    }

    public boolean deQueue() {
        if (count == 0) {
            return false;
        }
        start = start == circularQueue.length - 1 ? 0 : start + 1;
        count -= 1;
        return true;
    }

    public int Front() {
        if (count == 0) {
            return -1;
        }
        return circularQueue[start];
    }

    public int Rear() {
        if (count == 0) {
            return -1;
        }
        int lastIdx = end == 0 ? circularQueue.length - 1 : end - 1;
        return circularQueue[lastIdx];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == circularQueue.length;
    }
}

class Solution {
    private Integer[][][] memo;

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] charCount = new int[strs.length][2];
        for (int i = 0; i < charCount.length; i++) {
            String currString = strs[i];
            int ones = countOne(currString);
            int zeroes = currString.length() - ones;
            charCount[i][0] = zeroes;
            charCount[i][1] = ones;
        }
        memo = new Integer[strs.length][m + 1][n + 1];
        return dfs(charCount, 0, m, n);
    }

    private int dfs(int[][] charCount, int pos, int remainM, int remainN) {
        if (pos == charCount.length) {
            return 0;
        }
        if (memo[pos][remainM][remainN] != null) {
            return memo[pos][remainM][remainN];
        }
        int taken = 0;
        if (remainM - charCount[pos][0] >= 0 && remainN - charCount[pos][1] >= 0) {
            taken = dfs(charCount, pos + 1, remainM - charCount[pos][0], remainN - charCount[pos][1]) + 1;
        }
        int notTaken = dfs(charCount, pos + 1, remainM, remainN);
        return memo[pos][remainM][remainN] = Math.max(taken, notTaken);

    }

    private int countOne(String s) {
        char[] sArray = s.toCharArray();
        int ans = 0;
        for (char c : sArray) {
            if (c == '1') {
                ans += 1;
            }
        }
        return ans;
    }
}

class Solution {
    private int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X' && !visited[i][j]) {
                    dfs(board, visited, i, j);
                    ans += 1;
                }
            }
        }
        return ans;
    }

    private void dfs(char[][] board, boolean[][] visited, int row, int col) {
        visited[row][col] = true;
        for (int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutOfBound(board, newRow, newCol) && board[newRow][newCol] == 'X' && !visited[newRow][newCol]) {
                dfs(board, visited, newRow, newCol);
            }
        }
    }

    private boolean isOutOfBound(char[][] board, int row, int col) {
        return row < 0 || row >= board.length || col < 0 || col >= board[0].length;
    }
}

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new LinkedList<>();
        backtrack(s, list, new StringBuilder(), 0, 0);
        return list;
    }

    private void backtrack(String s, List<String> list, StringBuilder sb, int index, int level) {
        if (level > 4)
            return;
        if (index == s.length() && level == 4) {
            list.add(sb.toString());
            return;
        }
        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length())
                break;
            int num = Integer.valueOf(s.substring(index, index + i));
            // Checking if num is 0~9 or 10~99 or 100 ~ 255 because leading 0s is invalid.
            if (i == 1 || i == 2 && num >= 10 && num <= 99 || i == 3 && num >= 100 && num <= 255) {
                sb.append(num);
                if (level < 3)
                    sb.append(".");
                backtrack(s, list, sb, index + i, level + 1);
                if (level < 3)
                    sb.deleteCharAt(sb.length() - 1);
                sb.delete(sb.length() - i, sb.length());
            }
        }
    }
}