Leet Code 450. Delete Node in a BST

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.

package pep.Day70;

public class LeetCode_450_Delete_Node_in_BST {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode() {

        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;

        if (root.val < key) {
            // right me jaenge hum
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            // left me jaenge hum
            root.left = deleteNode(root.left, key);
        } else {
            // agr leaf node ko delete krna hoga
            // jab root.left ne null return kiya to jha se yeh
            // call hua hoga ie. iska parent me null add ho jaega aur
            // yeh key wala node delete ho jaega
            if (root.left == null && root.right == null)
                return null;
                // agr woh node delete krni hai jiska sirf ek child hai
            else if (root.left == null || root.right == null)
                return root.left == null ? root.right : root.left;
            else {
                // right wala element uthaya
                TreeNode temp = root.right;
                // right wala element ke left most child pr jaenge
                while (temp.left != null)
                    temp = temp.left;

                // jis root node ko delete krna hai usme leftmost wale ki value daal de
                root.val = temp.val;

                // aab leftmost wale ko delete krne ke lea
                // root node ki right side pr deleteNode call kr denge
                root.right = deleteNode(root.right, root.val);
            }
        }

        return root;
    }
}

 

Leet Code 701. Insert into a Binary Search Tree

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]

package pep.Day70;

public class LeetCode_703_Insert_into_Binary_Search_Tree {

    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode() {

        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode insertIntoBST(TreeNode root, int val) {

        if (root == null)
            return new TreeNode(val);

        if (root.val < val)
            root.right = insertIntoBST(root.right, val);
        else
            root.left = insertIntoBST(root.left, val);

        return root;
    }

}

Leet Code 889. Construct Binary Tree from Preorder and Postorder Traversal

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

package pep.Day69;

public class Construction_BinaryTree_From_PostOrder_and_PreOrder {

    public static void main(String[] args) {

        int[] pre = {1, 2, 3, 4};
        int[] post = {3, 4, 2, 1};

        Construction_BinaryTree_From_PostOrder_and_PreOrder x = new Construction_BinaryTree_From_PostOrder_and_PreOrder();
        x.constructFromPrePost(pre, post);
    }

    class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode() {

        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode constructFromPrePost(int[] preOrder, int[] postOrder) {
        TreeNode x = constructFromPrePost1(preOrder, 0, preOrder.length - 1, postOrder, 0, postOrder.length - 1);
        return x;
    }

    public TreeNode constructFromPrePost1(int[] preOrder, int preStart, int preEnd, int[] postOrder, int postStart, int postEnd) {

        if (preStart > preEnd)
            return null;

        TreeNode root = new TreeNode(postOrder[postEnd]);
        // base case: jisme ek hi node hogi eg. pre=[1], post[1]
        if (preStart == preEnd) {
            return root;
        }

        // find root element in PostOrder from PreOrder
        int i = findRoot_In_PostOrder(postOrder, preOrder[preStart + 1]);

        int leftCount = i - postStart + 1;

        root.left = constructFromPrePost1(preOrder, preStart + 1, preStart + leftCount, postOrder, postStart, i);
        root.right = constructFromPrePost1(preOrder, preStart + leftCount + 1, preEnd, postOrder, i + 1, postEnd - 1);

        return root;
    }

    public int findRoot_In_PostOrder(int[] postOrder, int rootLeftData) {
        for (int i = 0; i < postOrder.length; i++) {
            if (postOrder[i] == rootLeftData)
                return i;
        }
        return -1;
    }
}

Leet Code 106. Construct Binary Tree from Inorder and Postorder Traversal

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

package pep.Day69;

public class Construction_BinaryTree_From_PostOrder_and_InOrder {

    public static void main(String[] args) {
        int[] in = {9, 3, 15, 20, 7};
        int[] post = {9, 15, 7, 20, 3};
        Construction_BinaryTree_From_PostOrder_and_InOrder x = new Construction_BinaryTree_From_PostOrder_and_InOrder();
        x.buildTree(post, in);
    }

    class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode() {

        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode buildTree(int[] inOrder, int[] postOrder) {
        TreeNode x = postIn(postOrder, 0, postOrder.length - 1, inOrder, 0, inOrder.length - 1);
        return x;
    }

    public TreeNode postIn(int[] postOrder, int postStart, int postEnd, int[] inOrder, int inStart, int inEnd) {
        // base case
        if (inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postOrder[postEnd]);
        // find root element in InOrder from postOrder
        int i = findRoot_In_InOrder(inOrder, root.val);

        int lcount = i - inStart;

        root.left = postIn(postOrder, postStart, postStart + lcount - 1, inOrder, inStart, i - 1);
        root.right = postIn(postOrder, postStart + lcount, postEnd - 1, inOrder, i + 1, inEnd);

        return root;
    }

    public int findRoot_In_InOrder(int[] postOrder, int rootData) {
        for (int i = 0; i < postOrder.length; i++) {
            if (postOrder[i] == rootData)
                return i;
        }
        return -1;
    }
}

Leet Code 105. Construct Binary Tree from Preorder and Inorder Traversal

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

package pep.Day69;

public class Construction_BinaryTree_From_PreOrder_and_InOrder {

    class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode() {

        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return preIn(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode preIn(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {

        // base case
        if (preStart > preEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preOrder[preStart]);
        // find root element in InOrder from PreOrder
        int i = findRoot_In_InOrder(inOrder, root.val);

        int lcount = i - inStart;

        root.left = preIn(preOrder, preStart + 1, preStart + lcount, inOrder, inStart, i - 1);
        root.right = preIn(preOrder, preStart + lcount + 1, preEnd, inOrder, i + 1, inEnd);

        return root;
    }

    public int findRoot_In_InOrder(int[] inOrder, int rootData) {
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootData)
                return i;
        }
        return -1;
    }
}

HashMap Implementation

package pep.Day68;

import java.util.ArrayList;

public class HashMap_Implementation {
    private class Node {
        Integer key = 0;
        Integer value = 0;
        Node next = null;

        Node(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    private class MyLinkedList {
        public Node head = null, tail = null;
        public int numberOfElements = 0;

        public int size() {
            return numberOfElements;
        }

        public void addLast(Node node) {
            if (head == null) {
                head = tail = node;
            } else {
                tail.next = node;
                tail = tail.next;
            }
            numberOfElements++;
        }

        public Node getFirst() {
            return head;
        }

        public Node removeFirst() {
            Node temp = head;
            if (numberOfElements == 0)
                head = tail = null;

            if (head != null) {
                head = head.next;
                numberOfElements--;
            }

            return temp;
        }
    }

    private MyLinkedList[] containers;
    private int sizeOfHashMap = 0;

    public void assignValues(int size) {
        containers = new MyLinkedList[size];
        sizeOfHashMap = 0;
        for (int i = 0; i < size; i++) {
            containers[i] = new MyLinkedList();
        }
    }

    HashMap_Implementation() {
        assignValues(5);
    }

    // jo bhi yeh return krega woh container ki range me hogi,
    // hence, mujhe unique container mil jaega
    private int hashCode(Integer key) {
        int val = key.hashCode();
        return val % containers.length;
    }

    // aab hum container nikalenge,
    // hashCode() method se jo key mile hai, usse konsa group ya container allot krenge
    private MyLinkedList group(Integer key) {
        int code = hashCode(key);

        return containers[code];
    }

    public int getOrDefault(Integer key, Integer defaultVal) {
        return containsKey(key) ? get(key) : defaultVal;
    }

    // iss baat ki guarantee nhi hai, ki jo user ne key daale hai woh exist krege

    public int get(Integer key) {
        // yeh krne se agr mere key mil jaege to humne apni key ko head pr daal diya hoga
        boolean isKey = containsKey(key);

        // yha se mujhe mere container ki linked list mil jaege
        MyLinkedList group = group(key);
        return isKey ? group.head.value : null;
    }

    public boolean containsKey(Integer key) {
        MyLinkedList group = group(key);
        int size = group.size();

        while (size-- > 0) {
            if (group.getFirst().key == key)
                return true;

            // agr first element me key nhi hai
            // first element ko remove krenge aur last me add kr denge
            group.addLast(group.removeFirst());
        }
        return false;

    }

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

    public Integer remove(Integer key) {
        boolean isKey = containsKey(key);

        if (!isKey) {
            return null;
        }

        MyLinkedList group = group(key);
        Node returnValue = group.removeFirst();
        sizeOfHashMap--;
        return returnValue.value;
    }

    public ArrayList<Integer> keySet() {
        ArrayList<Integer> keys = new ArrayList<>();
        for (int i = 0; i < containers.length; i++) {
            MyLinkedList group = containers[i];
            int size = group.size();
            while (size-- > 0) {
                Node node = group.removeFirst();
                keys.add(node.key);
                group.addLast(node);
            }
        }
        return keys;
    }

    public void put(Integer key, Integer value) {
        // isme check krna hoga ki pehle se exist krte hain value ya nahi
        boolean isKey = containsKey(key);
        if (isKey) {
            MyLinkedList group = group(key);
            group.head.value = value;
        } else {
            MyLinkedList group = group(key);
            group.addLast(new Node(key, value));
            sizeOfHashMap++;

            // humne starting me hashmap ke 10 containers liye the
            // but jese hi mera lambda 0.6 se jyada hoga toh hum REHASH kr denge
            double lambda = group.size() / (containers.length * 0.1);
            if (lambda > 0.6)
                rehash();
            // rehash hum islea kar rhe hain, taki linked list me search time kaam ho sake
        }
    }

    private void rehash() {
        // shallow copy bnn gae
        MyLinkedList[] backup = containers;
        // agr lambda cross hota hai to, main double size ka hashmap bnaunga
        // also, yha pr humne nya hashmap bna liya
        assignValues(2 * backup.length);
        for (int i = 0; i < backup.length; i++) {
            MyLinkedList group = backup[i];
            int size = group.size();

            while (size-- > 0) {
                Node node = group.removeFirst();
                put(node.key, node.value);
            }
        }
    }

    public void putIfAbsent(Integer key, Integer value) {
        if (!containsKey(key))
            put(key, value);
    }

    public void display() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");

        for (int i = 0; i < containers.length; i++) {
            MyLinkedList group = containers[i];
            int size = group.size();

            while (size-- > 0) {
                Node node = group.removeFirst();
                sb.append("(" + node.key + "->" + node.value + ") ");
                group.addLast(node);
            }
        }
        sb.append("]");

        System.out.println(sb.toString());
    }


}

class Client {
    public static void main(String[] args) {
        HashMap_Implementation hm = new HashMap_Implementation();

        // rehashing hogi as mere Hashmap ka size pehle 5 tha aur hum 8 values add kr rhe hain
        for (int i = 0; i < 8; i++) {
            hm.put(i, i * 10);
        }
        System.out.println(hm.getOrDefault(4, 400));
        System.out.println(hm.getOrDefault(40, 400));
        hm.display();
    }
}

Leet Code 128. Longest Consecutive Sequence

 https://leetcode.com/problems/longest-consecutive-sequence/description/

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

• sab number ko HashSet me add kr denge, fir har number ki min aur max range nikalenge.

package pep.Day68;

import java.util.HashSet;

public class LeetCode_128_Longest_Consecutive_Sequence {
    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{100, 4, 3, 200, 2, 1, 0}));
    }

    public static int longestConsecutive(int[] nums) {
        HashSet<Integer> hs = new HashSet<>();
        for (int i : nums)
            hs.add(i);

        int range = 0;
        for (int i : nums) {
            int min = i, max = i;

            if (hs.contains(i)) {
                while (hs.contains(min - 1)) {
                    min = min - 1;
                    hs.remove(min);
                }

                while (hs.contains(max + 1)) {
                    max = max + 1;
                    hs.remove(max);
                }

                range = Math.max(range, max - min + 1);
            }
        }

        return range;
    }
}

Leet Code 781. Rabbits in Forest

Example 1:

Input: answers = [1,1,2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit that answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

package pep.Day67;

import java.util.HashMap;

public class LeetCode_781_Rabbits_in_Forest {
 
    public static int numRabbits(int[] answers) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i : answers) {
            hm.put(i, hm.getOrDefault(i, 0) + 1);
        }
        int ans = 0;
        for (int i : hm.keySet()) {
            ans += (Math.ceil(hm.get(i) / (i + 1.0))) * (i + 1);
        }


        return ans;
    }
}

Leet Code 632. Smallest Range Covering Elements from K Lists

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

package pep.Day67;

import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class LeetCode_632_Smallest_Range_Covering_Elements_from_K_Lists {

    public static class Pair implements Comparable<Pair> {
        int r, c, val;

        Pair(int r, int c, int val) {
            this.r = r;
            this.c = c;
            this.val = val;
        }

        public int compareTo(Pair other) {
            return this.val - other.val;
        }


    }

    public static int[] smallestRange(List<List<Integer>> nums) {

        Queue<Pair> pq = new PriorityQueue<>();
        int n = nums.size(), max = Integer.MIN_VALUE, range = Integer.MAX_VALUE, firstNumber = -1, secondNumber = -1;

        // sab list mese ek ek element queue me daal diya, also, max nikal liya
        for (int i = 0; i < n; i++) {
            pq.add(new Pair(i, 0, nums.get(i).get(0)));
            max = Math.max(max, nums.get(i).get(0));
        }

        while (pq.size() == n) {
            Pair rem = pq.remove();

            // update range agr choti mile to
            if (max - rem.val < range) {
                range = max - rem.val;
                firstNumber = rem.val;
                secondNumber = max;
            }

            if (rem.c + 1 < nums.get(rem.r).size()) {
                pq.add(new Pair(rem.r, rem.c + 1, nums.get(rem.r).get(rem.c + 1)));
                max = Math.max(max, nums.get(rem.r).get(rem.c + 1));
            }

        }

        return new int[]{firstNumber, secondNumber};

    }
}

Leet Code 778. Swim in Rising Water

Example 1:

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

package pep.Day67;

import java.util.PriorityQueue;
import java.util.Queue;

public class LeetCode_778_Swim_in_Rising_Water {


    public int swimInWater(int[][] grid) {
        int n = grid.length, m = grid[0].length;

        Queue<Integer> pq = new PriorityQueue<>((a, b) -> {
            int r1 = a / m;
            int c1 = a % m;
            int r2 = b / m;
            int c2 = b % m;

            return grid[r1][c1] - grid[r2][c2]; // min heap
        });

        boolean[][] visited = new boolean[n][m];
        pq.add(0);
        visited[0][0] = true;

        int previousPosition = 0, time = 0, dirns[][] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        while (!pq.isEmpty()) {
            int rem = pq.remove();

            // jisko remove kiya uske index nikalenge
            int x = rem / m;
            int y = rem % m;

            int currentPosition = grid[x][y];
            // time unit, currentPosition - previousPosition se jo niklega
            time += currentPosition - previousPosition < 0 ? 0 : currentPosition - previousPosition;

            // agr hum pehle hi apni destination node pr aa gae, time calculate krne ke baad
            if (x == n - 1 && y == m - 1)
                return time;

            //isme agr max time wala cell visit kr liya hai toh, usse chota wala visit nhi krenge
            previousPosition = Math.max(currentPosition, previousPosition);

            for (int[] dir : dirns) {
                int row = x + dir[0];
                int col = y + dir[1];

                if (row >= 0 && col >= 0 && row < n && col < m && !visited[row][col]) {
                    visited[row][col] = true;
                    pq.add(row * m + col);
                }
            }

        }

        return time;
    }

    class Pair implements Comparable<Pair> {

        int x, y, val;

        Pair(int i, int j, int value) {
            x = i;
            y = j;
            val = value;
        }

        @Override
        public int compareTo(Pair other) {
            return this.val - other.val;
        }
    }

    public int swimInWater1(int[][] grid) {
        int row = grid.length, col = grid[0].length;

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.add(new Pair(0, 0, grid[0][0]));

        grid[0][0] = -1;// visited
        int ans = 0;
        int[][] dirns = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        while (!pq.isEmpty()) {
            Pair top = pq.remove();
            int x = top.x;
            int y = top.y;
            int val = top.val;

            if (x == row - 1 && y == col - 1)
                return val;

            for (int[] dir : dirns) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx < 0 || ny < 0 || nx == row || ny == col || grid[nx][ny] == -1)
                    continue;

                pq.add(new Pair(nx, ny, Math.max(val, grid[nx][ny])));
                grid[nx][ny] = -1;// visited

            }

        }

        return -1;
    }

}

Leet Code 692. Top K Frequent Words

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

package pep.Day66;

import java.util.*;

public class LeetCode_692_Top_k_Frequent_Words {
    public static void main(String[] args) {
        int k = 2;
        System.out.println(topKFrequent(new String[]{"i", "love", "leetcode", "i", 

        "love", "coding"}, k));
    }

    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        for (String word : words) {
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String child, String parent) {
                int frequency1 = hashMap.get(child);
                int frequency2 = hashMap.get(parent);

                // when count will be same then, use alphabetical order descending
                if (frequency1 == frequency2)
                    return parent.compareTo(child);
                    //return newVal - oldVal;
                return frequency1 - frequency2;
            }
        });

        for (String s : hashMap.keySet()) {
            pq.add(s);
            if (pq.size() > k)
                pq.remove();
        }

        List<String> ans = new LinkedList<>();

        while (!pq.isEmpty())
            // this will add the value to 0th index and
            // then shift previous and add next on 0th index only
            ans.add(0, pq.remove());

        return ans;
    }

}