42 posts tagged with "leetcode"

class KthLargest {

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    int k;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        for(int n : nums) pq.add(n);
        while(pq.size() > k) pq.poll();
    }
    
    public int add(int val) {
        pq.add(val);
        if(pq.size() > k){
            pq.poll();
        }
        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // don't think quicksort is acutally good here 
        int[] res = new int[k];
        HashMap<Integer,Integer> count = new HashMap<>();
        for(int n : nums){
            if(count.containsKey(n)){
                count.put(n,count.get(n) + 1);
            }else{
                count.put(n,1);
            }
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> {return b[1] - a[1];});
        for(int key : count.keySet()){
            pq.add(new int[]{key,count.get(key)});
        }
        for(int i = 0; i < k; i ++){
            res[i] = pq.poll()[0];
        }
        return res;
    }
}

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // to solve this question
        // we first wanna to think this as a graph and using dfs find the path from a to b
        // in order to do so ,
        // we must construct a weighted graph
        HashMap<String,HashMap<String,Double>> graph = new HashMap<>();
        
        // we need to get equations to gain our two string node
        // we also need to have a index to keep track 
        int index = 0;
        for(List<String> e : equations){
            String a = e.get(0);
            String b = e.get(1);
            
            graph.putIfAbsent(a,new HashMap<>());
            graph.putIfAbsent(b,new HashMap<>());
            
            
            graph.get(a).put(b,values[index]);
            graph.get(b).put(a,1 / values[index]);
            index ++;
            
            graph.get(a).put(a,1.0);
            graph.get(b).put(b,1.0);
            
        }
        // we have sucessfully build our graph
        // lets look at our queiries
        double [] ans = new double[queries.size()];
        Arrays.fill(ans,-1.0);
        for(int i = 0; i < queries.size(); i ++){
            List<String> q = queries.get(i);
            String start = q.get(0);
            String end = q.get(1);
            
            // check if start and end in the graph at all
            if(!graph.containsKey(start) || !graph.containsKey(end)){
                continue;
            }else {
                dfs(graph,start,end,new HashSet<String>(),1.0,ans,i);
            
                continue;
            }
        }
        return ans;
    }
    // let's make our dfs method
    private void dfs (HashMap<String,HashMap<String,Double>> graph, String start, String end, Set<String> visited, double pre, double[] ans, int index){
        visited.add(start);
        if(graph.get(start).containsKey(end)){
            ans[index] = graph.get(start).get(end) * pre;
        }
        
        for(String next : graph.get(start).keySet()){
            if (visited.contains(next)) continue;
            dfs(graph,next,end,visited,graph.get(start).get(next) * pre ,ans,index);
        }
    }
}

class Solution {
    public boolean isBipartite(int[][] graph) {
        // graph color
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for(int i = 0; i < n; i ++){
            if(color[i] == -1){
                if(!isBipartite(graph,i,color)){
                    return false;
                }
            }
        }
        return true;
    }
    private boolean isBipartite(int[][] graph, int curr, int[] color){
        Queue<Integer> q = new LinkedList<>();
        color[curr] = 1; // color curr node to 1 
        q.add(curr);
        while(!q.isEmpty()){
            int c = q.poll();
            for(int next : graph[c]){
                if(color[next] == color[c]) return false;
                if(color[next] == -1){
                    // this is not colored yet 
                    color[next] = 1 - color[c];
                    q.add(next);
                }
            }
        }
        return true;
    }
}

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        boolean[] pointed = new boolean[n];
        for(List<Integer> edge : edges){
            pointed[edge.get(1)] = true; // this node can be reached from other nodes
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < n; i ++){
            // any nodes cant be reached from other nodes we just add into res
            if(!pointed[i]) res.add(i);
        }
        return res;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // Get middle of the linked list.
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // Reverse second half of the linked list.
        ListNode nextNode, prev = null;
        while (slow != null) {
            nextNode = slow.next;
            slow.next = prev;
            prev = slow;
            slow = nextNode;
        }
        ListNode start = head;
        int maximumSum = 0;
        while (prev != null) {
            maximumSum = Math.max(maximumSum, start.val + prev.val);
            prev = prev.next;
            start = start.next;
        }

        return maximumSum;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 
        if(head == null || head.next == null) return head;
        ListNode last = head.next; // this would be the new head, because we have to reverse curr and next
        head.next = swapPairs(head.next.next); // the head is now the curr sections last node and it suppose to connect to the rest of the list
        last.next = head; // set the new head to connect to the curr head which is tail of the curr section
        return last;
    }
}

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        // locate the end node 
        ListNode slow = head;
        ListNode fast = head;
        int k1 = k;
        while(fast != null && k1 > 0){
            fast = fast.next;
            k1 --;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        ListNode p = head;
        while(p != null && k > 1){
            p = p.next;
            k --;
        }
        // make the swap 
        int temp = p.val;
        p.val = slow.val;
        slow.val = temp;
        return head;
    }
}

class Solution {
    public int minCostII(int[][] costs) {
        if(costs.length == 0) return 0; // nothing to paint
        int k = costs[0].length; // the k color we are looking for
        int n = costs.length;
        int[] previousRow = costs[0];

        for(int house = 1; house < n; house++){
            // we going to look at curr costs
            int[] currRow = new int[k];
            for(int color = 0; color < k; color ++){
                int min = Integer.MAX_VALUE;
                // locate the cheapest solution from last row, we want the cheapest cost so far
                for(int previousColor = 0; previousColor < k; previousColor ++){
                    if(color == previousColor){
                        // we can't print two adjusent color same
                        continue;
                    }
                    min = Math.min(min, previousRow[previousColor]);
                }
                // if we would paint curr house curr color, then we add cost from min previous house and cost of curr house 
                currRow[color] += costs[house][color] += min;
            }
            // now we want to change previousRow = curr
            previousRow = currRow;
        }
        // now we have the final row, find return the res
        int res = Integer.MAX_VALUE;
        for(int cost : previousRow){
            res = Math.min(res,cost);
        }
        return res;
    }
}

class Solution {
    int[] memo;
    public int maxScore(int[] nums) {
        memo = new int[ 1 << nums.length];
        Arrays.fill(memo,-1);
        return dp(nums, 0, 0);
    }
    private int dp(int[] nums, int mask, int pairsPicked){
        // base case 
        if(2 * pairsPicked == nums.length) return 0; // we picked all number
        // solved case
        if(memo[mask] != -1) return memo[mask];

        int max = 0;
        for(int i = 0; i < nums.length; i ++){
            for(int j = i + 1; j < nums.length; j ++){
                // If the numbers are same, or already picked, then we move to next number.
                if (((mask >> i) & 1) == 1 || ((mask >> j) & 1) == 1) {
                    continue;
                }

                // Both numbers are marked as picked in this new mask.
                int newMask = mask | (1 << i) | (1 << j);
                 // Calculate score of current pair of numbers, and the remaining array.
                int currScore = (pairsPicked + 1) * gcd(nums[i], nums[j]);
                int remainingScore = dp(nums, newMask, pairsPicked + 1);

                // Store the maximum score.
                max = Math.max(max, currScore + remainingScore);
                // We will use old mask in loop's next interation, 
                // means we discarded the picked number and backtracked.
            }
        }
        return memo[mask] = max;
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

class Solution {
    Integer[] memo;
    int MOD = 1_000_000_007;
    public int countGoodStrings(int low, int high, int zero, int one) {
        memo = new Integer[high + 1];
        int res = 0;
        for(int i = low; i <= high; i ++){
            res += dp(i,zero,one);
            res %= MOD;
        }
        return res;
    }
    private int dp(int l, int zero, int one){
        // base case 
        if(l == 0) return 1; // we made to zero then we have 1 good string
        if(l < zero && l < one) return 0; //this case we are not allowed to append 
        // solved case 
        if(memo[l] != null) return memo[l]; // we have done this before 
        // solving the problem 
        int appendZeros = dp(l - zero,zero,one);
        int appendOnes = dp(l - one, zero, one);
        return memo[l] = (appendOnes + appendZeros) % MOD;
    }
}