class Solution {
    public List<String> commonChars(String[] words) {
        int[][] arr = new int[words.length][26];
        int n=0;
        
        for(String word:words){
            for(char ch:word.toCharArray()){
                arr[n][ch-'a']++;
            }
            n++;
        }
        
        List<String> list = new ArrayList<>();
        
        for(int i=0; i<26; i++){
            int k=100;
            for(int j=0; j<arr.length; j++){
                k=Math.min(k, arr[j][i]);
            }
            
            while(k-- >0){
                list.add(Character.toString(i+'a'));
            }
        }
        
        return list;
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[][] arr = new int[2][1001];
        List<Integer> list = new ArrayList<>();
        
        for(int i:nums1)
            arr[0][i]++;
        
        for(int i:nums2)
            arr[1][i]++;
        
        for(int i=0; i<1001; i++){
            if(arr[0][i]*arr[1][i]>0) list.add(i);
        }
        
        int[] res = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int diff = Integer.MAX_VALUE;
        
        for(int i=0; i<arr.length-1; i++)
            diff = Math.min(diff, arr[i+1] - arr[i]);
        
        List<List<Integer>> list = new ArrayList<>();
        
        for(int i=0; i<arr.length-1; i++){
            if(diff == arr[i+1] - arr[i]){
                List<Integer> sublist = new ArrayList<>();
                sublist.add(arr[i]);
                sublist.add(arr[i+1]);
                list.add(sublist);
            }
        }
        
        return list;
    }
}

class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        int min=Integer.MAX_VALUE, index=-1;;
        for(int i=points.length-1; i>=0; i--){
            if(points[i][0]==x||points[i][1]==y){
                if(min>=Math.abs(points[i][0]-x)+Math.abs(points[i][1]-y)){
                    min=Math.abs(points[i][0]-x)+Math.abs(points[i][1]-y);
                    index=i;
                }
            }
        }
        
        return index;
    }
}

class Solution {
    public int numRookCaptures(char[][] board) {
        int Rx=0, Ry=0, count=0;;
        for(int i=0; i<8; i++){
            for(int j=0; j<8; j++){
                if(board[i][j]=='R'){
                    Rx=i;
                    Ry=j;
                }
            }
        }
        
        int[][] helper = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
        for(int[] h:helper){
            for(int i=Rx+h[0], j=Ry+h[1]; i>=0 && i<8 && j>=0 && j<8; i+=h[0], j+=h[1]){
                if(board[i][j]=='p') count++;
                if(board[i][j]!='.') break;
            }
        }
        
        return count;
    }
}

class Solution {
    public double average(int[] salary) {
        Arrays.sort(salary);
        
        int sum=0;
        for(int i=1; i<salary.length-1; i++)
            sum+=salary[i];
        
        return (double)sum/(salary.length-2);
    }
}

class Solution {
    public int numUniqueEmails(String[] emails) {
        String lname, dname;
        
        Map<String, Integer> map = new HashMap<>();
        for(String email:emails){
            StringBuilder s = new StringBuilder();
            lname=email.split("@")[0];
            dname=email.split("@")[1];
            
            lname=lname.replace(".", "");
            if(lname.contains("+")) lname=lname.substring(0, lname.indexOf("+"));
            
            s.append(lname).append('@').append(dname);
            map.put(s.toString(), map.getOrDefault(s.toString(), 0) +1);
        }
        return map.size();
    }
}

class Solution {
    public String[] findWords(String[] words) {
        String row1="QWERTYUIOPqwertyuiop";
        String row2="ASDFGHJKLasdfghjkl";
        String row3="ZXCVBNMzxcvbnm";
        List<String> list = new ArrayList<>();
        for(String word:words){
            int[][] counter = new int[1][3];
            for(int i=0; i<word.length(); i++){
                if(row1.contains(word.valueOf(word.charAt(i))))
                    counter[0][0]++;
                if(row2.contains(word.valueOf(word.charAt(i))))
                    counter[0][1]++;
                if(row3.contains(word.valueOf(word.charAt(i))))
                    counter[0][2]++;
            }
            if(counter[0][0]==word.length()||counter[0][1]==word.length()||counter[0][2]==word.length()) list.add(word);
        }
        return list.toArray(new String[0]);
    }
}

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        for(int i=0; i<matrix.length-1; i++){
            for(int j=0; j<matrix[i].length-1; j++){
                if(matrix[i][j]!=matrix[i+1][j+1]) return false;
            }
        }
        
        return true;
    }
}

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int max=nums[0], min=nums[0];
        for(int n:nums){
            max = Math.max(max, n);
            min = Math.min(min, n);
        }
        return Math.max(max-min-2*k, 0); 
    }
}

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int res=0, l=arr2.length;
        
        Arrays.sort(arr1); Arrays.sort(arr2);
        for(int n:arr1){
            int count=0, start=0, end=l-1;
            while(start<=end){
                int mid=(start+end)/2;
                if(Math.abs(arr2[mid]-n)<=d) {
                    count++;
                    break;
                }
                if(arr2[mid]>n+d) end=mid-1;
                if(arr2[mid]<n-d) start=mid+1;
                
            }
            if(count==0) res++;
        }
        
        return res;
    }
}

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        
        for(int candy:candyType)
            set.add(candy);
        
        return Math.min(set.size(), candyType.length/2);
    }
}

class Solution {
    public int maxAscendingSum(int[] nums) {
        List<Integer> sumlist = new ArrayList<>();
        int sum=0, i=0;
        
        for(; i<nums.length-1; i++){
            if(nums[i]<nums[i+1]){
                sum+=nums[i];
            }else{
                sum+=nums[i];
                sumlist.add(sum);
                sum=0;
            }
        }
        sum+=nums[i];
        sumlist.add(sum);
        
        int max=sumlist.get(0);
        for(int n:sumlist)
            max=Math.max(max, n);
        
        return max;
    }
}

class Solution {
    public int numSpecial(int[][] mat) {
        int count=0, row[]=new int[mat.length], col[]=new int[mat[0].length];
        
        for(int i=0; i<mat.length; i++)
            for(int j=0; j<mat[i].length; j++)
                if(mat[i][j]==1){
                    row[i]++;
                    col[j]++;
                }
        
        for(int i=0; i<mat.length; i++)
            for(int j=0; j<mat[i].length; j++)
                if(mat[i][j]==1 && row[i] == 1 && col [j] == 1)
                    count++;
        
        return count;
    }
}

class Solution {
    public double trimMean(int[] arr) {
        Arrays.sort(arr);
        
        for(int i=0; i<arr.length/20; i++)
            arr[i]=arr[arr.length-i-1]=0;
        
        int sum=0;
        for(int n:arr)
            sum+=n;
        
        return (double)sum/(arr.length*9/10);
    }
}

class Solution {
    public boolean threeConsecutiveOdds(int[] arr) {
        for(int i=0; i<arr.length-2; i++)
            if(arr[i]*arr[i+1]*arr[i+2] % 2 == 1) return true;
        
        return false;
    }
}

class Solution {
    public int minOperations(String[] logs) {
        int res = 0;
        for (String s : logs) {
            if (s.equals("../")) res = Math.max(0, --res);
            else if (s.equals("./")) continue;
            else res++;
        }
        return res;
    }
}

class Solution {
    public int findLucky(int[] arr) {
        int[] count = new int[501];
        
        for(int i: arr)
            count[i]++;
        
        for(int i=count.length-1; i>=0; i--){
            if(i==0) return -1;
            if(count[i]==i) return i;
        }
        
        return -1;
    }
}