Leet Code 977. Squares of a Sorted Array

https://leetcode.com/problems/squares-of-a-sorted-array/

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

package pep.Day52;

public class LeetCode_977_Squares_of_sorted_array {
    public static void main(String[] args) {
        int[] x = sortedSquares(new int[]{-4, -1, 0, 3, 10});

        for (int xx : x)
            System.out.print(xx + " ");
    }

    public static int[] sortedSquares(int[] nums) {
        int start = 0, end = nums.length - 1, answer_idx = end;
        int[] ans = new int[nums.length];

        while (answer_idx >= 0) {
            if (square(nums[start]) >= square(nums[end]))
                ans[answer_idx--] = square(nums[start++]);
            else
                ans[answer_idx--] = square(nums[end--]);
        }

        return ans;
    }

    private static int square(int num) {
        return num * num;
    }
}

public static int[] sortedSquares(int[] nums) {
    int[] ans = new int[nums.length];
    int i = 0;
    int j = nums.length-1;
    int k= nums.length-1;
    while (i <= j) {
        int left = nums[i] * nums[i];
        int right = nums[j] * nums[j];

        if (left > right) {
            ans[k--] = left;
            i++;
        } else {
            ans[k--] = right;
            j--;
        }
    }

    return ans;
}

Leet Code 11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

package pep.Day52;

public class LeetCode_11_Container_With_Most_Water {


    public static int maxArea(int[] height) {
        int start = 0;
        int end = height.length - 1;
        int maxArea = 0;

        while (start < end) {
            maxArea = Math.max(maxArea, (end - start) * Math.min(height[start], height[end]));
            
            // this means that start is at wrong position
            if (height[start] < height[end])
                start++;
            else
                end--;

        }

        return maxArea;
    }
}

Leet Code 684. Redundant Connection

isme pehle (1,2), then (2,3) aaya

jab (1,3) aaega tab humein cycle bnege, hence, woh redundant hai

hum aab koi bhi node hata skte hain, redundancy remove krne ke lea.

But cycle to bne hi last wale edge se the i.e. (1,3)

humein woh last node return krne hai jiski wjh se cycle bne hai

package pep.Day45;

public class LeetCode_684_Redundant_Connections {
    public int[] findRedundantConnection(int[][] graph) {
        // n kese niklega?
        // no. of edges =  no. of vertices +1
        int n = graph.length;

        // 1 -> n hai to n+1 ka size hona cheye
        parent = new int[n + 1];
        size = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int[] edge : graph) {
            int u = edge[0];
            int v = edge[1];

            int p1 = findParent(u);
            int p2 = findParent(v);

            if (p1 != p2) {
                merge(p1, p2);
            } else {
                return edge;
            }
        }

        return new int[0];
    }

    int[] parent, size;

    public int findParent(int u) {

        return parent[u] == u ? u : (parent[u] = findParent(parent[u]));
    }

    public void merge(int u, int v) {

        if (size[u] >= size[v]) {
            parent[v] = u;
            size[u] += size[v];
        } else {
            parent[u] = v;
            size[v] += size[u];
        }
    }
}

Graph - Disjoint Set Union

 

package pep.Day45;

public class DSU_Introduction {
    static int[] parent, size;

    public static int findParent(int u) {
        // agr jis node ke lea hum check kr rhe hain, woh khud apna leader/parent hai
        // to return kr denge node
        // nhi to recursive code chalaenge
        //return parent[u] == u ? u : findParent(parent[u]);

        // But return krte hue hume path compression bhi krna tha,
        // hence, recorsion se jo parent aaega uko update kr denge
        return parent[u] == u ? u : (parent[u] = findParent(parent[u]));
    }

    public static void merge(int u, int v) {
        // jiska bhi size bada hoga, woh parent banega dusre ka
        // also, size bhi bhadega
        if (size[u] >= size[v]) {
            parent[v] = u;
            size[u] = size[u] + size[v];
        } else {
            parent[u] = v;
            size[v] = size[v] + size[u];
        }
    }

    public static void unionFind(int n, int[][] graph) {
        parent = new int[n];
        size = new int[n];

        // har koi apna parent khud hai
        for (int i = 0; i < n; i++)
            parent[i] = i;

        // sabka size intitially 1 hai
        for (int i = 0; i < n; i++)
            size[i] = 1;

        for (int[] edge : graph) {
            int u = edge[0];
            int v = edge[1];

            int p1 = findParent(u);
            int p2 = findParent(v);

            if (p1 != p2) {
                merge(p1, p2);
            } else {
                System.out.println("Cycle");
            }
        }
    }


    static class Edge {
        int src;
        int nbr;

        Edge(int src, int nbr) {
            this.src = src;
            this.nbr = nbr;
        }

    }
}

Leet Code 329. Longest Increasing Path in a Matrix

                                                         

package pep.Day44;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_329_Longest_Increasing_Path_in_Matrix {
    // can be done by DP, DFS  - kahn's algo
    public static int longestIncreasingPath(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] indegree = new int[n][m];

        int[][] dirns = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

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

                    if (x >= 0 && y >= 0 && x < n && y < m)
                        // merakoi bhi nbr bada milta hai toh indegree +1 kr denge
                        if (matrix[i][j] < matrix[x][y])
                            indegree[x][y]++;
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        // firse traverse krenge yeh dhundhne ke lea kiski indegree 0 hai
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (indegree[i][j] == 0)
                    queue.add(i * m + j);
            }
        }

        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- > 0) {
                int rem = queue.remove();
                int i = rem / m;
                int j = rem % m;

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

                    if (x >= 0 && y >= 0 && x < n && y < m) {
                        if (matrix[i][j] < matrix[x][y]) {
                            if (--indegree[x][y] == 0)
                                queue.add(x * m + y);
                        }
                    }

                }
            }
            level++;
        }

        return level + 1;
    }
}

Leet Code 207. Course Schedule - DFS cycle detection

https://leetcode.com/problems/course-schedule/ 

hum 3 state maintain krenge har node ki

1. state = 0: node not visited

2. state =1: node visited and is part of current path

                   Yeh cycle detect karega, agr hum dobara iss node par aa gae, jo ki visited bhi hai and current path ka part bhi hai

3. state =2: node visited but, not part of current path, 

                   Reason: iss node ko apne ans me add kr chuke hain, current path se backtrack kr chuke hain hum, to jab dobara iss node pr aaenge to kuch nhi krenge

package pep.Day44;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LeetCode_207_Course_Schedule_DFS {
    public static void main(String[] args) {
        // non-cycle
        int[][] paths = {
                {0, 1}, {1, 2}, {2, 4}, {4, 5}, {5, 6}, {5, 7}, {6, 7}, {2, 8}, {8, 5}, {0, 3}, {3, 2}
        };

        //cycle
        int[][] paths1 = {
                {0, 1}, {1, 2}, {2, 4}, {4, 5}, {5, 6}, {5, 7}, {6, 7}, {2, 8}, {8, 5}, {3, 0}, {2, 3}
        };
        System.out.println(canFinish(9, paths1));
    }

    public static boolean canFinish(int n, int[][] pre) {

        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] p : pre) {
            graph[p[0]].add(p[1]);
        }

        List<Integer> ans = new ArrayList<>();
        int[] state = new int[n];
        for (int i = 0; i < n; i++) {
            if (state[i] == 0)
                dfs(graph, i, state, ans);
        }

        return ans.size() == n;
    }

    public static boolean dfs(ArrayList<Integer>[] graph, int src, int[] state, List<Integer> ans) {
        state[src] = 1; // isko visit kr chuke hain, aur yeh humare
        // current path ka part bhi hai

        // iske neighbours
        for (int nbr : graph[src]) {
            if (state[nbr] == 1)    // visited bhi hai, current path ka hissa bhi hai, aur hum dobara aa gae iss pr
                return false;   // iska matlb cycle hai

            if (state[nbr] == 0)    // visited bhi nhi hai, to dfs call
            {
                boolean val = dfs(graph, nbr, state, ans);
                // also, agr dfs se false aa gya jab humne uske nbr ke lea call lgaya, return false
                if (val == false)
                    return false;

            }
        }
        // yha tak sab nbr ko call lag gae hai, aur hum backtrack krte hue jaa rhe hain
        state[src] = 2;
        ans.add(src);
        return true;
    }
}

Leet Code 207. Course Schedule I - Kahn's Algorithm

https://leetcode.com/problems/course-schedule/

Same as Kahn's Algorithm, here we need to return True -> if all nodes are traversed i.e. all dependencies will be resolved, else False

package pep.Day44;

import java.util.*;

public class LeetCode_207_Course_Schedule {
    public static void main(String[] args) {
        System.out.println(canFinish(2, new int[][]{{1, 0}}));
    }

    public static boolean canFinish(int n, int[][] pre) {

        ArrayList<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        int[] indegree = new int[n];

        for (int[] p : pre) {
            graph[p[0]].add(p[1]);
            indegree[p[1]]++;
        }

        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0)
                que.add(i);
        }

        ArrayList<Integer> ans = new ArrayList<Integer>();

        while (!que.isEmpty()) {
            int rem = que.remove();

            ans.add(rem);

            for (int nbr : graph[rem]) {
                if (--indegree[nbr] == 0) {
                    que.add(nbr);
                }
            }

        }

        return n == ans.size();
    }
}

Leet Code 210. Course Schedule II - Kahn's Algorithm

https://leetcode.com/problems/course-schedule-ii/

Here we need to print the topological sort using Kahn's Algo

package pep.Day44;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_210_Course_Schedule_II {
    public static void main(String[] args) {
        System.out.println(findOrder(2, new int[][]{{1, 0}}));
    }

    public static int[] findOrder(int n, int[][] pre) {
        ArrayList<Integer>[] graph = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        int[] indegree = new int[n];

        for (int[] p : pre) {
            graph[p[0]].add(p[1]);
            indegree[p[1]]++;
        }

        Queue<Integer> que = new LinkedList<>();

        for (int i = 0; i < n; i++)
            if (indegree[i] == 0)
                que.add(i);

        int[] ansArr = new int[n];
        int idx = -1;
        while (!que.isEmpty()) {
            int out = que.remove();
            ansArr[n - 1 - (++idx)] = out;
            for (int nbr : graph[out]) {
                if (--indegree[nbr] == 0)
                    que.add(nbr);
            }
        }

        return idx < n - 1 ? new int[0] : ansArr;

    }
}

Topological Order - Kahn's Algorithm

Step 1. we will calculate indegree of all nodes

indegree = kitne log dependent hai mere node pr

package pep.Day44;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Kahn_Algorithm {

    static class Edge {
        int src;
        int nbr;

        Edge(int src, int nbr) {
            this.src = src;
            this.nbr = nbr;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            graph[v1].add(new Edge(v1, v2));
            // directed graph hai to isko comment kr denge
            // graph[v2].add(new Edge(v2, v1));
        }

        kahns(graph);
    }

    public static void kahns(ArrayList<Edge>[] graph) {
        int n = graph.length;
        // first we will find indegree
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            for (Edge e : graph[i]) {
                indegree[e.nbr]++;
            }
        }

        // jin jin ki indegree 0 hai, unko queue m add kr do
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0)
                que.add(i);
        }

        LinkedList<Integer> ans = new LinkedList<>();
        while (!que.isEmpty()) {

            int remove = que.remove();
            ans.addFirst(remove);
            // jisko remove kiya, woh jis jis par dependent hai uski indegree -1 kro
            // if indegree == 0, then again add in queue
            for (Edge e : graph[remove]) {
                if (--indegree[e.nbr] == 0)
                    que.add(e.nbr);
            }
        }
        System.out.println(ans.size() == n ? ans : "cycle is present, topological sort is not possible...");
    }
}

Topological Order - DFS

 

package pep.Day42;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Topological_Order {

    static class Edge {
        int src;
        int nbr;

        Edge(int src, int nbr) {
            this.src = src;
            this.nbr = nbr;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            graph[v1].add(new Edge(v1, v2));
            // directed graph hai to isko comment kr denge
            // graph[v2].add(new Edge(v2, v1));
        }
        topologicalOrder(vtces, graph);
    }

    public static void topologicalOrder(int n, ArrayList<Edge>[] graph) {
        boolean[] visited = new boolean[n];
        // topological sort ko arrayList me fill krte hain
        ArrayList<Integer> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                // dfs ka method likhna hai, which will tell konse order me mere nodes add honge
                // i.e. post order
                topoDfs(graph, i, visited, ans);
            }
        }

        System.out.println(ans);
    }

    private static void topoDfs(ArrayList<Edge>[] graph, int src, boolean[] visited, ArrayList<Integer> ans) {

        visited[src] = true;
        for (Edge e : graph[src]) {
            if (!visited[e.nbr]) {
                topoDfs(graph, e.nbr, visited, ans);
            }
        }
        // recursion ke call lgane ke baad add krenge i.e. post order
        ans.add(src);

    }

}

Spread Of Infection

I/P:

7 8 0 1 10 1 2 10 2 3 10 0 3 10 3 4 10 4 5 10 5 6 10 4 6 10 6 3

O/P: 4

package pep.Day42;

import java.io.*;
import java.util.*;

public class Spread_Of_Infection {

    static class Edge {
        int src;
        int nbr;

        Edge(int src, int nbr) {
            this.src = src;
            this.nbr = nbr;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            graph[v1].add(new Edge(v1, v2));
            graph[v2].add(new Edge(v2, v1));
        }

        int src = Integer.parseInt(br.readLine());
        int t = Integer.parseInt(br.readLine());

        int[] visited = new int[vtces];
        Arrays.fill(visited, -1);
        System.out.println(getCount(graph, src, t, visited));

        Arrays.fill(visited, 0);
        System.out.println(getCount2(graph, src, t, visited));


    }

    private static int getCount2(ArrayList<Edge>[] graph, int src, int t, int[] visited) {
        visited[src] = 1;
        int count = 1;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(src);
        while (!queue.isEmpty()) {
            int rem = queue.remove();

            for (Edge e : graph[rem]) {
                if (visited[e.nbr] == 0) {
                    visited[e.nbr] = visited[rem] + 1;

                    if (visited[e.nbr] > t)
                        return count;
                    count++;
                    queue.add(e.nbr);
                }
            }
        }
        return count;
    }

    public static int getCount(ArrayList<Edge>[] graph, int src, int time, int[] visited) {

        int level = 1;
        int count = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(src);


        while (!queue.isEmpty()) {

            int size = queue.size();
            while (size-- > 0) {
                if (level == time + 1)
                    return count;
                int out = queue.remove();
                if (visited[out] == -1) {
                    visited[out] = level;
                    count++;
                }


                for (Edge e : graph[out]) {
                    if (visited[e.nbr] == -1) {
                        queue.add(e.nbr);
                    }
                }
            }
            level++;
        }

        return 0;
    }

}