22 posts tagged with "dailychallenge"

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> seen1 = new HashSet<>();
        Set<Integer> seen2 = new HashSet<>();
        for(int num : nums1){
            seen1.add(num);
        }
        Set<Integer> distinct2 = new HashSet<>();
        for(int num : nums2){
            seen2.add(num);
            if(!seen1.contains(num)){
                distinct2.add(num);
            }
        }
        Set<Integer> distinct1 = new HashSet<>();
        for(int num : nums1){
            if(!seen2.contains(num)){
                distinct1.add(num);
            }
        }
        return List.of(new ArrayList<>(distinct1),new ArrayList<>(distinct2));
    }
}

class Solution {
    public int arraySign(int[] nums) {
        int count = 0;
        for(int i = 0; i < nums.length; i ++){
            if(nums[i] == 0) return 0;
            if(nums[i] < 0){
                count ++;
            }
        }
        return count % 2 == 0 ? 1 : -1;
    }
}

class Solution {
    public double average(int[] salary) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int total = 0;
        for(int n : salary){
            min = Math.min(min,n);
            max = Math.max(max,n);
            total += n;
        }
        return (total - min - max) / (double)(salary.length - 2);
    }
}

// the native apporach
class Solution {
    public int[][] indexPairs(String text, String[] words) {
        ArrayList<int[]> res = new ArrayList<>();
        Arrays.sort(words,(a,b) ->{return a.length() - b.length();}); // insure the order.
        for(int i = 0; i < text.length(); i ++){
            for(String word : words){
                if(text.substring(i).startsWith(word)){
                    res.add(new int[]{i,i + word.length() - 1});
                }
            }
        }
        int[][] ans = new int[res.size()][2];
        for(int i = 0; i < res.size(); i ++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}

class Solution {
    public class TrieNode{
        boolean word;
        TrieNode[] children;
        public TrieNode(){
            word = false;
            children = new TrieNode[26]; //26 character
        }
    }
    public class MyTrie{
        TrieNode root;
        public MyTrie(){
            root = new TrieNode();
        }
        public void add(String word){
            TrieNode curr = root;
            for(char c : word.toCharArray()){
                if(curr.children[c - 'a'] == null){
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.word = true;
        }
        public boolean serach(String word){
            TrieNode curr = root;
            for(char c : word.toCharArray()){
                if(curr.children[c - 'a'] == null) return false;
                curr = curr.children[c - 'a'];
            }
            return curr.word;
        }
        
    }
    public int[][] indexPairs(String text, String[] words) {
        MyTrie trie = new MyTrie();
        for(String word : words){
            trie.add(word);
        }
        List<int[]> res = new ArrayList<>();
        for(int i = 0; i < text.length(); i ++){
            TrieNode p = trie.root;
            for (int j = i; j < text.length(); j++) {
                if (p.children[text.charAt(j) - 'a'] == null) {
                    break;
                }
                p = p.children[text.charAt(j) - 'a'];
                if (p.word) {
                    res.add(new int[] { i, j });
                }
            }
        }
        int[][] ans = new int[res.size()][];
        ans = res.toArray(ans);
        return ans;
    }
}

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        // still union find
        // we can remove edge if when we trying to connect the nodes are already connected
        UnionFind alice = new UnionFind(n);
        UnionFind bob = new UnionFind(n);
        int res = 0;
        // do union for type 3 first
        for(int[] edge : edges){
            if(edge[0] == 3){
                int a = edge[1];
                int b = edge[2];
                res += (alice.union(a,b) | bob.union(a,b));
            }
        }

        for(int[] edge : edges){
            int type = edge[0];
            int a = edge[1];
            int b = edge[2];
            if(type == 1){
                res += alice.union(a,b);
            }else if(type == 2){
                res += bob.union(a,b);
            }
        }

        if(alice.isValid() && bob.isValid()){
            return edges.length - res;
        }else{
            return -1;
        }
    }
    public class UnionFind {
        int[] parent;
        int[] size;
        int n;
        public UnionFind(int n){
            parent = new int[n + 1];
            size = new int[n + 1];
            for(int i = 0; i <= n; i ++){
                parent[i] = i;
                size[i] = 1;
            }
            this.n = n;
        }
        public int find(int a){
            if(parent[a] == a) return a;
            return parent[a] = find(parent[a]);
        }
        public int union(int a, int b){
            int pa = find(a);
            int pb = find(b);
            if(pa == pb) return 0;
            if(size[pa] > size[pb]){
                // join b into a 
                parent[pb] = a;
                size[pa] += size[pb];
            }else{
                parent[pa] = b;
                size[pb] += size[pa];
            }
            n --;
            return 1;
        }
        public boolean isValid(){
            return n == 1;
        }
    }
}

class Solution {
    int[] parent;
    int[] size;
    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        int queriesCount = queries.length;
        boolean[] res = new boolean[queriesCount];
        // init 
        parent = new int[n];
        size = new int[n];
        for(int i = 0; i < n; i ++){
            parent[i] = i;
            size[i] = 1;
        }
        // Store original indices with all queries.
        int[][] queriesWithIndex = new int[queriesCount][4];
        for (int i = 0; i < queriesCount; ++i) {
            queriesWithIndex[i][0] = queries[i][0];
            queriesWithIndex[i][1] = queries[i][1];
            queriesWithIndex[i][2] = queries[i][2];
            queriesWithIndex[i][3] = i;
        }
        Arrays.sort(edgeList,(a,b) ->{return a[2] - b[2];});
        Arrays.sort(queriesWithIndex,(a,b) ->{return a[2] - b[2];});
        int edgesIndex = 0;
        for(int i = 0; i < queriesCount; i ++){
            int p = queriesWithIndex[i][0];
            int q = queriesWithIndex[i][1];
            int limit = queriesWithIndex[i][2];
            int originalIndex = queriesWithIndex[i][3];
            // because we have the edges sorted
            // while our paths are smaller than limit, we want to attache all the edges thta is less than limit
            // if this made p q in a same union aka connected, we return true
            while(edgesIndex < edgeList.length && edgeList[edgesIndex][2] < limit){
                int node1 = edgeList[edgesIndex][0];
                int node2 = edgeList[edgesIndex][1];
                union(node1,node2);
                edgesIndex += 1;
            }
            res[originalIndex] = find(p) == find(q);
        }
        return res;
        
    }
    private int find(int a){
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    private int union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb) return 0;
        if(size[pa] > pb){
            parent[pb] = a;
            size[pa] += size[pb];
        }else{
            parent[pa] = b;
            size[pb] += size[pa];
        }
        return 1;
    }
}

class Solution {
    // union find 
    int[] parent;
    int[] size;
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        parent = new int[n];
        size = new int[n];
        for(int i = 0; i < n; i ++){
            parent[i] = i;
            size[i] = 1;
        }
        int count = n;
        for(int i = 0; i < n; i ++){
            for(int j = i + 1; j < n; j ++){
                String a = strs[i];
                String b = strs[j];
                if(similar(a,b)){
                    count -= union(i,j);
                }
            }
        }
        return count;
    }
    private int find(int a){
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    private int union(int a, int b){
        int pa = find(a);
        int pb = find(b);
        if(pa == pb) return 0;
        if(size[pa] > size[pb]){
            // join b to a 
            parent[pb] = a;
            size[pa] += size[pb];
        }else{
            parent[pa] = b;
            size[pb] += size[pa];
        }
        return 1;
    }
    private boolean similar(String a, String b){
        int diff = 0;
        for(int i = 0; i < a.length(); i ++){
            if(a.charAt(i) != b.charAt(i)){
                diff ++;
            }
        }
        return diff == 2 || diff == 0;
    }
}

class Solution {
    public int bulbSwitch(int n) {
        // n == 0 all bulbs are off
        // n == 1 all bulbs with factor of 1 
        // n == 2 all bulbs with factor 2 (2,4,6,8,10)...
        // n == 3 all bulbs with factor 3 (3,6,9).....
        // ......
        // so we are finding number from 1 to n are perfect square
        // essencially we are trying to find the sqrt of the n 
        return (int) Math.sqrt(n);
    }
}

class Solution {
    public int addDigits(int num) {
        // base case
        if(num < 10) return num;
        int res = 0;
        while(num != 0){
            res += num % 10;
            num /= 10;
        }
        return addDigits(res);
    }
}

class SmallestInfiniteSet {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    int curr;
    public SmallestInfiniteSet() {
        // set curr smallest to 1
        curr = 1;
    }
    
    public int popSmallest() {
        if(!pq.isEmpty())return pq.poll();
        // if we have nothing in pq, curr smallest is what we poll out, and sus next number would be curr + 1
        curr ++;
        return curr - 1;
    }
    
    public void addBack(int num) {
        if(num < curr & !pq.contains(num)){
            // number is small and we dont have it in our pq 
            // add back
            pq.add(num);
        }
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */

class Solution {
    public int lastStoneWeight(int[] stones) {
        // very straight forward, we use priority queue to ensure we polling the largest 2 stones
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->{return b - a;});
        for(int stone : stones){
            pq.add(stone);
        }
        // while we have 2 or more stones
        while(pq.size() > 1){
            int a = pq.poll();
            int b = pq.poll();
            if(a != b){
                int remain = Math.abs(a - b);
                pq.add(remain);
            }
        }
        // return nothing if we got no stone or last stone standing.
        return pq.isEmpty() ? 0 : pq.poll();
    }
}