Extracting information from URL

Input URL format:

http://www.{word}.{word}/{word}/{word}?username={word}&pwd={word}&profile={word}&role={word}&key={word}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // Reading input URL

        String url = scanner.nextLine().trim();

        // Extracting parameters and their values

        String[] parts = url.split("\\?");

        String[] params = parts[1].split("&");

        // Printing parameters and their values

        for (String param : params) {

            String[] keyValue = param.split("=");

            System.out.println(keyValue[0] + ": " + keyValue[1]);

        }

    }

}

Code demonstrating multiple inheritence in JAVA VIA INTERFACE

 interface A {

    void methodA();

}

interface B {

    void methodB();

}

// Class C implements both interfaces A and B

class C implements A, B {

    public void methodA() {

        System.out.println("Method A implementation");

    }

    public void methodB() {

        System.out.println("Method B implementation");

    }

}

public class Main {

    public static void main(String[] args) {

        C obj = new C();

        obj.methodA(); // Output: Method A implementation

        obj.methodB(); // Output: Method B implementation

    }

}

Static vs Non-static access

 class Car{

    void get()

    {

        System.out.println("Inside Car");

        MyClass.func(); // non-static can access static

    }

}

public class MyClass {

    public static void main(String[] args) {

        func();

        Car cr = new Car();

        cr.get();

    }

    public static void func()

    {

        System.out.println("Hello");

        //Car.get(); // static cannot access non-static

    }

}

Returning object using this keyword in Java

public class MyClass {

    private int value;

    public MyClass(int value) {

        this.value = value;

    }

    public MyClass doSomething() {

        // Perform some operation, for example, doubling the value

        this.value *= 2;

        // Return the current object

        return this;

    }

    public int getValue() {

        return this.value;

    }

    public static void main(String[] args) {

        // Create an instance of MyClass

        MyClass obj = new MyClass(5);

       

        // Call the doSomething() method and chain it with another method

        System.out.println("Hello"+ obj.doSomething());

        int result = obj.doSomething().getValue();

       

        // Output the result

        System.out.println("Value after operation: " + result); // Output: Value after operation: 10

    }

}

Merge two sorted arrays

 import java.util.*;

public class MyClass {

    public static void main(String[] args) {

    int arr1[]={1,3,5,7,9};

    int arr2[]={2,4,6,8,10};

    int ans[]=new int[10];

    ans = merge(arr1,arr2);

    for(int i=0;i<10;i++)

      {

        System.out.print(ans[i]+" ");

      }

    }

    public static int[] merge(int arr1[], int arr2[])

    {

        int i=0,j=0,k=0;

        int n1=arr1.length;int n2=arr2.length;int ans[]=new int[n1+n2];

        while (i < n1 && j < n2) {

            if (arr1[i] < arr2[j]) {

                ans[k++] = arr1[i++];

            } else {

                ans[k++] = arr2[j++];

            }

        }

   

        // Copy the remaining elements of arr1, if any

        while (i < n1) {

            ans[k++] = arr1[i++];

        }

   

        // Copy the remaining elements of arr2, if any

        while (j < n2) {

            ans[k++] = arr2[j++];

        }

   

        return ans;

    }

}

Abstract class in JAVA

 abstract class Shape {

    abstract double area(); // Abstract method to calculate area

    abstract double perimeter(); // Abstract method to calculate perimeter

    void display() {

        System.out.println("This is a shape.");

    }

}

class Circle extends Shape {

    double radius;

    Circle(double radius) {

        this.radius = radius;

    }

    @Override

    double area() {

        return Math.PI * radius * radius;

    }

    @Override

    double perimeter() {

        return 2 * Math.PI * radius;

    }

}

class Rectangle extends Shape {

    double length;

    double width;

    Rectangle(double length, double width) {

        this.length = length;

        this.width = width;

    }

    @Override

    double area() {

        return length * width;

    }

    @Override

    double perimeter() {

        return 2 * (length + width);

    }

}

public class AbstractClassExample {

    public static void main(String[] args) {

        Circle circle = new Circle(5);

        System.out.println("Area of circle: " + circle.area());

        System.out.println("Perimeter of circle: " + circle.perimeter());

        Rectangle rectangle = new Rectangle(4, 6);

        System.out.println("Area of rectangle: " + rectangle.area());

        System.out.println("Perimeter of rectangle: " + rectangle.perimeter());

        circle.display();

        rectangle.display();

    }

}

GRAPH REPRESENTATION VIA ADJACENCY LIST IN JAVA & ADD EDGES

Method 1: Add manually

import java.util.*;

public class Wind {

    public static void main(String[] args) {

        HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<>();

        // Adding nodes to the graph

        for (int i = 0; i < 4; i++) {

            adjList.put(i, new ArrayList<>());

        }

        // Adding edges to the graph

        addEdge(adjList, 0, 1);

        addEdge(adjList, 1, 3);

        addEdge(adjList, 1, 2);

        addEdge(adjList, 0, 2);

        // Print the adjacency list

        System.out.println("Adjacency List: " + adjList);

    }

    // Helper method to add an edge to the graph

    public static void addEdge(HashMap<Integer, ArrayList<Integer>> adjList, int source, int destination) {

        adjList.get(source).add(destination);

        adjList.get(destination).add(source); // If the graph is undirected

    }

}

Method 2: Add when edges pre-given in form of 2-d matrix

import java.util.*;

public class Wind {

    public static void main(String[] args) {

        HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<>();

        // Adding nodes to the graph

        for (int i = 0; i < 4; i++) {

            adjList.put(i, new ArrayList<>());

        }

       

        int prerequisite[][] = {{0,1},{1,3},{1,2},{0,2}};

        for (int[] row : prerequisite)

        {

            int v=row[1];

            int u=row[0];

            addEdge(adjList,u,v); // u --> v

        }

        /*for (int[] row : prerequisite) {

            for (int element : row) {

                // Access the current element

                System.out.print(element + " ");

            }

            System.out.println(); // Move to the next line after each row

        }*/

        // Print the adjacency list

        System.out.println("Adjacency List: " + adjList);

    }

    public static void addEdge(HashMap<Integer, ArrayList<Integer>> adjList, int source, int destination) {

        adjList.get(source).add(destination);

        //adjList.get(destination).add(source); // If the graph is undirected

    }

}

To print the longest common subsequence

Solution:

public class Dsa {

    public static void main(String[] args) {

        String s1 = "ABCDAF";

        String s2 = "ACBCF";

        int lcsLength = LCS(s1, s2);

        System.out.println("Length of Longest Common Subsequence: " + lcsLength);

    }

    public static int LCS(String s1, String s2) {

        int n1 = s1.length();

        int n2 = s2.length();

        int dp[][] = new int[n1 + 1][n2 + 1];

        for (int i = 1; i <= n1; i++) {

            for (int j = 1; j <= n2; j++) {

                if (s1.charAt(i - 1) == s2.charAt(j - 1))

                    dp[i][j] = 1 + dp[i - 1][j - 1];

                else

                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

            }

        }

        // to print lcs string

        int i = n1, j = n2;

        StringBuilder lcs = new StringBuilder();

        while (i > 0 && j > 0) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                lcs.insert(0, s1.charAt(i - 1));

                i--;

                j--;

            } else if (dp[i - 1][j] > dp[i][j - 1]) {

                i--;

            } else {

                j--;

            }

        }

        System.out.println(lcs.toString());

        return dp[n1][n2]; //returns length of lcs string

    }

}

To print the longest increasing subsequence

Solution:

import java.util.ArrayList;

import java.util.Arrays;

class Dsa {

    public static int lengthOfLIS() {

        int arr[]={5,4,11,1,16,8};

        int n=arr.length;

        int dp[]=new int[n];int hash[]=new int[n];

        Arrays.fill(dp,1);

        for(int i=1;i<n;i++)

        {

            hash[i]=i;

            for(int j=0;j<i;j++)

            {

                if(arr[i]>arr[j])

                {

                    if(dp[j]+1>dp[i])

                    {

                        dp[i]=dp[j]+1;

                        hash[i]=j;

                    }

                }

            }

        }

        int maxIdx=0;int lastIndex=-1;

        for(int i=0;i<n;i++)

        {

            if(dp[i]>dp[maxIdx])

            {

                maxIdx=i;

                //maxIdx=i;

                lastIndex=i;

            }

        }

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

    temp.add(arr[lastIndex]);

    

    while(hash[lastIndex] != lastIndex){ // till not reach the initialization value

        lastIndex = hash[lastIndex];

        temp.add(arr[lastIndex]);    

    }

    

    // reverse the array 

    

    System.out.print("The subsequence elements are ");

    

    for(int i=temp.size()-1; i>=0; i--){

        System.out.print(temp.get(i)+" ");

    }

    System.out.println();

        return dp[maxIdx];

    }

    public static void main(String[] args) {

        lengthOfLIS();

    }

}

Collections.binarySearch in JAVA

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

public class BinarySearchExample {

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9));

        int key = 5;

        int index = Collections.binarySearch(list, key);

        if (index >= 0) {

            System.out.println("Element found at index: " + index);

        } else {

            System.out.println("Element not found. Insertion point: " + (-index - 1));

        }

    }

}

// If you are working with arrays, you would use Arrays.binarySearch.

Problem statement: https://leetcode.com/problems/product-of-array-except-self/description/

Solution:

in O(1) space , if ans array is not considered as extra space

class Solution {

    public int[] productExceptSelf(int[] nums) {

        int n = nums.length;

        int[] ans = new int[n];

        

        ans[0] = 1;

        for (int i = 1; i < n; i++) {

            ans[i] = ans[i - 1] * nums[i - 1];

        }

        

        int right = 1; 

        for (int i = n - 1; i >= 0; i--) {

            ans[i] *= right;

            right *= nums[i];

        }

        

        return ans;

    }

}

Next Permutation by O(n)

import java.util.*;

public class Solution {

    public static List< Integer > nextGreaterPermutation(List< Integer > A) {

        // Write your code here

        int n= A.size();

        int dip_idx = -1;

        for(int i=n-2; i>=0; i--)

        {

            if(A.get(i)<A.get(i+1))

            {

                dip_idx = i;

                break;

            }

        }

        if(dip_idx== -1)

        {

            Collections.reverse(A);

        }

        for(int i=n-1;i>=dip_idx;i--)

        {

            if(A.get(i)>A.get(dip_idx))

            {

                int temp=A.get(dip_idx);

                A.set(dip_idx,A.get(i));

                A.set(i,temp);

                break;

            }

        }

        Collections.reverse(A.subList(dip_idx+1, n));

        return A;

    }

}

BigInteger class is not in java.util.*
Hence you have to import it

import java.math.BigInteger;

public class MyFirstClass {

    public static void main(String[] args) {

        BigInteger sm = new BigInteger("4");

        System.out.println(sm);

    }

}

 longest Subarray with maximum sum as k

import java.util.*;

public class MyFirstClass {

    public static void main(String[] args) {

        int[] a = {2, 3, 1, 1, 2, 4, 2, 9};

        long k = 10;

        int len = getLongestSubarray(a, k);

        System.out.println("The length of the longest subarray is: " + len);

    }

public static int getLongestSubarray(int []a, long k) {

        int n = a.length; // size of the array.

        Map<Long, Integer> preSumMap = new HashMap<>();

        long sum = 0;

        int maxLen = 0;

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

            //calculate the prefix sum till index i:

            sum += a[i];

            // if the sum = k, update the maxLen:

            if (sum == k) {

                maxLen = Math.max(maxLen, i + 1);

            }

            // calculate the sum of remaining part i.e. x-k:

            long rem = sum - k;

            //Calculate the length and update maxLen:

            if (preSumMap.containsKey(rem)) {

                int len = i - preSumMap.get(rem);

                maxLen = Math.max(maxLen, len);

            }

            //Finally, update the map checking the conditions:

            if (!preSumMap.containsKey(sum)) {

                preSumMap.put(sum, i);

            }

        }

        return maxLen;

    }

}

 Intersection of two sorted arrays code in java

import java.util.*;

public class MyFirstClass {

    public static void main(String[] args) {

        int arr1[] = {1,1,2,3,4,4,5};

int arr2[] = {2,3,4,4,5,10,20,100};

int n1 = arr1.length; int n2=arr2.length;

int leng = n1+n2;

int i=0;int j=0;

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

while(i<n1 && j<n2)

{

if(arr1[i]<arr2[j])

{

i++;

}

else if(arr2[j] < arr1[i])

{

j++;

}

else

{

Intersection.add(arr1[i]);

i++;

j++;

}

}

System.out.println(Intersection);

    }

}

 Union of two sorted arrays code in java

import java.util.*;

public class MyFirstClass {

    public static void main(String[] args) {

        int arr1[] = {1,1,2,3,4,5};

int arr2[] = {2,3,4,4,5,10,20,100};

int n1 = arr1.length; int n2=arr2.length;

int leng = n1+n2;

int i=0;int j=0;

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

while(i<n1 && j<n2)

{

if (arr1[i] <= arr2[j]) // Case 1 and 2

{

  if (Union.size() == 0 || Union.get(Union.size()-1) != arr1[i])

Union.add(arr1[i]);

  i++;

} else // case 3

{

  if (Union.size() == 0 || Union.get(Union.size()-1) != arr2[j])

Union.add(arr2[j]);

  j++;

}

  }

while(j<n2)

{

if (Union.size() == 0 || Union.get(Union.size()-1) != arr2[j])

        Union.add(arr2[j]);

      j++;

}

while(i<n1)

{

if (Union.size() == 0 || Union.get(Union.size()-1) != arr1[i])

        Union.add(arr1[i]);

      i++;

}

System.out.println(Union);

    }

}

Highest / Lowest Frequency Elements

Coding Ninjas Problem Link

import java.util.HashMap;

import java.util.Map;

import java.util.Arrays;

import java.util.Scanner;

public class MyFirstClass {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int v[] = {11,13,3,14,17,3,7,9,1,11,9,15,5,2,2,3,11,2};

        int r[] = getFrequencies(v);

        for (int i : r) {

            System.out.print(i+" ");

        }

    }

    public static int[] getFrequencies(int []v) {

        // Write Your Code Here

        HashMap<Integer,Integer> mp = new HashMap<>();

        int n = v.length;

        //int result[] = new int[n];

        for(int i=0; i<v.length; i++)

        {

            int freq = 0;

            if(mp.containsKey(v[i])) 

            {

                freq = mp.get(v[i]);

            }

            freq += 1;

            mp.put(v[i],freq);

        }

        int maxele=0;int minele=0;

        int minfreq=n;

        int maxfreq = 0;

        for(HashMap.Entry<Integer,Integer> entry : mp.entrySet())

        {

            int element = entry.getKey();

            int count = entry.getValue();

            if(count>=maxfreq)

            {

                if(count==maxfreq) maxele = Math.min(maxele, element);

                else maxele = element;

                maxfreq = count;

            }

            if(count<=minfreq)

            {

                //minele = Math.min(element,minele);

                if(count==minfreq) minele = Math.min(minele, element);

                else minele = element;

                minfreq = count;

            }

        }

        int result[] = new int[2];

        result[0] = maxele;

        result[1] = minele;

        return result;

    }

}

Count Frequency in a range

Coding Ninjas Link

import java.util.HashMap;

public class Solution {

    public static int[] countFrequency(int n, int x, int []nums){

        HashMap<Integer,Integer> mp = new HashMap<>();

        int result[] = new int[n];

        for(int i=0; i<nums.length; i++)

        {

            int freq = 0;

            if(mp.containsKey(nums[i])) 

            {

                freq = mp.get(nums[i]);

            }

            freq += 1;

            mp.put(nums[i],freq);

        }

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

            mp.putIfAbsent(i, 0);

        }

        for(int i=0; i<n; i++)

        {

            result[i] = mp.get(i+1);

        }

        return result;

    }

}

HashMap and Entry Interface code in JAVA

import java.util.HashMap;

import java.util.Map;

import java.util.Arrays;

import java.util.Scanner;

public class MyFirstClass {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        HashMap<Integer,String> m = new HashMap<>();

        System.out.println(m);

        m.put(101,"John");

        m.put(102,"Aman");

        m.put(103,"Satyam");

        m.put(104,"Aryaman");

        System.out.println(m);

        System.out.println("=======");

        System.out.println(m.entrySet());

        System.out.println(m.keySet().size());

        for(int i: m.keySet())

        {

            System.out.println(i);

        }

        for(String i: m.values())

        {

            System.out.println(i);

        }

        for(int i: m.keySet())

        {

            System.out.println(i+" "+m.get(i));

        }

    }

}

Question: Find the highest/lowest frequency element.If there are multiple elements that have the highest frequency or lowest frequency then pick the smallest element.

Coding Ninjas Problem link 

import java.util.HashMap;

import java.util.Map;

import java.util.TreeSet;

public class Solution {

    public static int[] getFrequencies(int[] v) {

        int n = v.length;

        return frequency(v, n);

    }

    public static int[] frequency(int[] arr, int n) {

        HashMap<Integer, Integer> map = new HashMap<>();

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

            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);

        }

        TreeSet<Integer> maxFreqElements = new TreeSet<>();

        TreeSet<Integer> minFreqElements = new TreeSet<>();

        int maxFreq = 0, minFreq = n;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

            int count = entry.getValue();

            int element = entry.getKey();

            if (count > maxFreq) {

                maxFreqElements.clear();

                maxFreqElements.add(element);

                maxFreq = count;

            } else if (count == maxFreq) {

                maxFreqElements.add(element);

            }

            if (count < minFreq) {

                minFreqElements.clear();

                minFreqElements.add(element);

                minFreq = count;

            } else if (count == minFreq) {

                minFreqElements.add(element);

            }

        }

        int[] res = new int[2];

        res[1] = minFreqElements.first(); // Smallest element with minimum frequency

        if (maxFreqElements.size() > 1) {

            res[0] = maxFreqElements.first(); // Smallest element with maximum frequency

        } else {

            res[0] = maxFreqElements.pollFirst();

        }

        return res;

    }

}

         L 

      L L L 

   L L L L L 

  L L L L L L L 

L L L L L L L L L

import java.util.*;

public class MyFirstClass {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i = 1 ; i<=n ; i++)

        { 

            for(int j = i+1; j<=n; j++)

            {

                System.out.print(" ");

            }

            for(int j = 1; j<=i; j++)

            {

                System.out.print("L");

            }

            for(int j = 1; j<i; j++)

            {

                System.out.print("L");

            }

            System.out.println();

        }

    }

}

Pass by value vs Pass by reference in JAVA 

Theory:

Java is strictly pass-by-value. In Java, you can't directly pass variables by reference as you would in languages like C/C++. However, you can achieve a similar effect by passing an array or an object reference.

Code:

import java.util.*;

public class MyFirstClass {

    public static void main(String[] args) {

        //Pass by value example in JAVA

        System.out.println("PASS by value example in JAVA");

        int n = 1;

        passByValue(n);

        System.out.println(n); // You can see O/P of n is unmodified by passByValue func

        System.out.println("PASS by reference example in JAVA");

        // Pass by reference example in JAVA

        int num[] = new int[1];

        num[0] = 10;

        doSomething(num); // Passing the array reference

        System.out.println(num[0]); // Print the modified value

    }

    // Pass by value example in JAVA

    public static void passByValue(int num)

    {

        num = num + 10;

        System.out.println(num);

    }

    // Pass by reference example in JAVA

    public static void doSomething(int num[]) {

        num[0] = num[0] + 10;

        System.out.println(num[0]);

    }

}

 // Grid Unique Paths-->2-D dp concept(space optimised)

// tc = O(mxn) 

// sc = O(n) --> array

import java.util.*;

class dp {

     public static int f(int m, int n)

     {

        int prev[] = new int[n];

        for(int i=0;i<m;i++)

        {

            int temp[] = new int[n];

            for(int j=0;j<n;j++)

            {

                if(i==0&&j==0) {temp[j] = 1;continue;}

            else

            {

                int up=0;int left=0;

               if(i>0)

               up = prev[j];

                if(j>0)

                left = temp[j - 1];

                temp[j] = up + left;

            }

            }

            prev = temp;

        }

        return prev[n - 1];

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

        System.out.println(f(m,n));

    }

}

// Grid Unique Paths-->2-D dp concept(Tabulation)

// tc = O(mxn) 

// sc = O(mxn) --> extra dp array

import java.util.*;

class dp {

     public static int f(int dp[][], int m, int n)

     {

        for(int i=0;i<m;i++)

        {

            for(int j=0;j<n;j++)

            {

                if(i==0&&j==0) {dp[0][0]=1;continue;}

            else

            {

                int up=0;int left=0;

               if(i>0)

                up = dp[i-1][j];

                if(j>0)

                left = dp[i][j-1];

                dp[i][j] = up+left;

            }

            }

        }

        return dp[m-1][n-1];

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

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

        // Initialize the DP array with -1 to indicate uncomputed values

        for (int[] row : dp)

            Arrays.fill(row, -1);

        System.out.println(f(dp,m,n));

    }

}

 

 // Count Grid Unique Paths-->2-D dp concept(Memoization)

// tc = O(mxn) -->at max there will be n*m calls of recursion

// sc = O((n-1)+(m-1)) + O(mxn) --> stack space + extra dp array

import java.util.*;

class dp {

     public static int f(int i , int j, int dp[][])

     {

        if(i==0&&j==0) return 1;

        if(i<0||j<0) return 0;

        if(dp[i][j]!=-1) return dp[i][j];

        int up = f(i-1,j,dp);

        int left = f(i,j-1,dp);

        return dp[i][j]=up+left;

     }

    public static void main(String args[]) {

        int m = 3;

        int n = 2;

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

        // Initialize the DP array with -1 to indicate uncomputed values

        for (int[] row : dp)

            Arrays.fill(row, -1);

        System.out.println(f(m-1,n-1,dp));

    }

}

 // Ninja's Training-->2-D dp concept(Memoization)

// tc = O(nx4x3)

// sc = O(n) + O(nx4) --> stack space + extra dp array

import java.util.*;

class dp {

    // Recursive function to calculate the maximum points for the ninja training

    static int f(int day, int last, int[][] points, int[][] dp) {

        // If the result is already calculated, return it

        if (dp[day][last] != -1) return dp[day][last];

        // Base case: When it's the first day (day == 0)

        if (day == 0) {

            int maxi = 0;

            for (int i = 0; i <= 2; i++) {

                if (i != last)

                    maxi = Math.max(maxi, points[0][i]);

            }

            return dp[day][last] = maxi; // Store and return the result

        }

        int maxi = 0;

        // Loop through the three activities on the current day

        for (int i = 0; i <= 2; i++) {

            if (i != last) {

                // Calculate the points for the current activity and recursively

                // calculate the maximum points for the previous day

                int activity = points[day][i] + f(day - 1, i, points, dp);

                maxi = Math.max(maxi, activity); // Update the maximum points

            }

        }

        return dp[day][last] = maxi; // Store and return the result

    }

    // Function to find the maximum points for ninja training

    static int ninjaTraining(int n, int[][] points) {

        // Initialize a memoization table with -1 values

        int dp[][] = new int[n][4];

        for (int[] row : dp)

            Arrays.fill(row, -1);

        // Start the recursive calculation from the last day (n - 1) with the last activity (3)

        return f(n - 1, 3, points, dp);

    }

    public static void main(String args[]) {

        // Define the points for each activity on each day

        int[][] points = {{10, 40, 70},

                          {20, 50, 80},

                          {30, 60, 90}};

        int n = points.length; // Get the number of days

        System.out.println(ninjaTraining(n, points)); // Calculate and print the maximum points

    }

}

 // Maximum Sum of Non-Adjacent Elements(Memoization)

// tc = O(n)

// sc = O(n) + O(n) --> stack space + extra dp array

import java.util.*;

public class dp {

    public static int func(int index, int arr[],int dp[])

    {

        if(index==0) return arr[index];

        if(index<0) return 0;

        if(dp[index] !=-1) return dp[index];

        int pick = func(index-2, arr,dp) + arr[index];

        int notpick = func(index-1, arr, dp) + 0;

        return dp[index] = Math.max(pick,notpick);

    }

    public static void main(String[] args) {

         int arr[] = {2,1,4,9};

         int n = 3; // or, n=arr.length

         int dp[] = new int[n+1]; // then n

         Arrays.fill(dp,-1);

         System.out.println(func(n,arr,dp));

    }

}

// Frog Jump via Bottom-up(Tabulation)

// tc = O(n)

// sc = O(n) --> extra dp array

import java.util.*;

public class dp {

     

    public static void main(String[] args) {

        int height[]={30,10,60,10,60,50};

        int n = 5; // or when --> n = height.length

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1);

        dp[0] = 0;

        for(int i = 1;i<n+1;i++)

        {

            int left_jmpOne = dp[i-1] + Math.abs(height[i] - height[i-1]);

            int right_jmpTwo = Integer.MAX_VALUE;

            if(i>1){

            right_jmpTwo = dp[i-2] + Math.abs(height[i] - height[i-2]);

             }

            dp[i] = Math.min(left_jmpOne,right_jmpTwo);

        }

        System.out.println(dp[n]); // then n-1

    }

}

// Frog Jump via Memoization

// tc = O(n)

// sc = O(n) + O(n) --> stack space + extra dp array

import java.util.*;

public class dp {

    public static int func(int index, int height[], int dp[]) {

        if(index==0) return 0;

        if(dp[index] != -1) return dp[index];

        int left_jmpOne = func(index-1,height,dp) + Math.abs(height[index] - height[index-1]);

        int right_jmpTwo = Integer.MAX_VALUE;

        if(index>1)

        {

            right_jmpTwo = func(index-2,height,dp) + Math.abs(height[index] - height[index-2]);

        }

        return dp[index] = Math.min(left_jmpOne,right_jmpTwo);

    }

    public static void main(String[] args) {

        int height[]={30,10,60,10,60,50};

        int n = 5; // n = height.length

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1);

        System.out.println(func(n,height,dp)); // then n-1 here

    }

}

 

// Climbing Stairs | How to Write 1D Recurrence Relations

// tc = O(n)

// sc = O(n) --> stack space

import java.util.*;

public class dp {

    public static int func(int index) {

        if (index == 0) return 1;

        if (index == 1) return 1;

        int left = func(index - 1);

        int right = func(index - 2);

        return left + right;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of stairs: ");

        int n = scanner.nextInt();

        int ways = func(n);

        System.out.println("Number of ways to climb " + n + " stairs: " + ways);

    }

}

 

// Program to convert recursive fibonacci into dp by tabulation method(bottom-up)

// tc= O(n)

// sc= O(1) = extra array space is also removed

import java.util.*;

public class dp {

    public static void main(String[] args) {

       int n = 5;

       //int dp[] = new int[n+1];

       int prev2 = 0;

       int prev = 1;

       System.out.println(prev2);

       System.out.println(prev);

       for(int i = 2; i<n+1;i++)

       {

         int curr = prev + prev2;

         System.out.println(curr);

         prev2 = prev;

         prev = curr;

       }

       //System.out.println(prev);

    }

}

// Program to convert recursive fibonacci into dp

// tc= O(n)

// sc= O(n) + O(n) = stack space + extra array space respectively

import java.util.*;

public class dp {

    public static int func(int n, int[] dp)

    {

         if(n<=1) return n; //base case

         if(dp[n] != -1) return dp[n]; //memoization

         return dp[n]= func(n-1,dp) + func(n-2,dp); //compute

    }

    public static void main(String[] args) {

        int n = 5;

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1); // initialise all with -1

        for (int i : dp) {

            System.out.print(i+" "); // output is -1,-1,-1,-1,-1,-1

        }

        System.out.println();

        System.out.println("----");

        System.out.println(func(n,dp)); // output is 5

        System.out.println("----");

         for (int i : dp) {

            System.out.print(i+" "); // output is: -1,-1,1,2,3,5

        }

    }

}

// Program to convert recursive fibonacci into dp by tabulation method(bottom-up)

// tc= O(n)

// sc= O(n) = extra array space respectively (stack space is removed)

import java.util.*;

public class dp {

    public static void main(String[] args) {

       int n = 5;

       int dp[] = new int[n+1];

       dp[0] = 0;

       dp[1] = 1;

       for(int i = 2; i<n+1;i++)

       {

        dp[i] = dp[i-2] + dp[i-1];

       }

       for (int i : dp) {

         System.out.print(i+" ");

       }

    }

}

Shortest Path in undirected Graph with unit weights (code in JAVA)

import java.util.*;

import java.lang.*;

import java.io.*;

class dist{

    

    public static void main(String[] args) throws IOException{

        int n=9, m=10;

        int[][] edge = {{0,1},{0,3},{3,4},{4,5},{5,6},{1,2},{2,6},{6,7},{7,8},{6,8}};

          

        Solution obj = new Solution();

        int res[] = obj.shortestPath(edge,n,m,0);

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

            System.out.print(res[i]+" ");

        }

        System.out.println();

    }

}

class Solution {

    

    public int[] shortestPath(int[][] edges,int n,int m ,int src) {

    //Create an adjacency list of size N for storing the undirected graph.

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

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

            adj.add(new ArrayList<>()); 

        }

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

            adj.get(edges[i][0]).add(edges[i][1]); 

            adj.get(edges[i][1]).add(edges[i][0]); 

        }

    //A dist array of size N initialised with a large number to 

    //indicate that initially all the nodes are untraversed. 

        int dist[] = new int[n];

        for(int i = 0;i<n;i++) dist[i] = (int)1e9;

        dist[src] = 0; 

    // BFS Implementation

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

        q.add(src); 

        while(!q.isEmpty()) {

            int node = q.peek(); 

            q.remove(); 

            for(int it : adj.get(node)) {

                if(dist[node] + 1 < dist[it]) {

                    dist[it] = 1 + dist[node]; 

                    q.add(it); 

                }

            }

        }

        // Updated shortest distances are stored in the resultant array ‘ans’.

        // Unreachable nodes are marked as -1. 

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

            if(dist[i] == 1e9) {

                dist[i] = -1; 

            }

        }

        return dist; 

    }

}

Shortest Path in directed acyclic graph via topological sort. Remember this method of topological sort to find the shortest distance do not work for graph containing cycle and in that case we use Dijkstra's Algorithm. (code in JAVA)

import java.util.*;

import java.lang.*;

import java.io.*;

class dist {

  public static void main(String[] args) throws IOException {

    int n = 6, m = 7;

    int[][] edge = {{0,1,2},{0,4,1},{4,5,4},{4,2,2},{1,2,3},{2,3,6},{5,3,1}};

    Solution obj = new Solution();

    int res[] = obj.shortestPath(n, m, edge);

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

      System.out.print(res[i] + " ");

    }

    System.out.println();

  }

}

class Pair {

  int first, second;

  Pair(int _first, int _second) {

    this.first = _first;

    this.second = _second;

  }

}

//User function Template for Java

class Solution {

  private void topoSort(int node, ArrayList < ArrayList < Pair >> adj,

    int vis[], Stack < Integer > st) {

    //This is the function to implement Topological sort. 

    vis[node] = 1;

    for (int i = 0; i < adj.get(node).size(); i++) {

      int v = adj.get(node).get(i).first;

      if (vis[v] == 0) {

        topoSort(v, adj, vis, st);

      }

    }

    st.add(node);

  }

  public int[] shortestPath(int N, int M, int[][] edges) {

    ArrayList < ArrayList < Pair >> adj = new ArrayList < > ();

    for (int i = 0; i < N; i++) {

      ArrayList < Pair > temp = new ArrayList < Pair > ();

      adj.add(temp);

    }

    //We create a graph first in the form of an adjacency list.

    for (int i = 0; i < M; i++) {

      int u = edges[i][0];

      int v = edges[i][1];

      int wt = edges[i][2];

      adj.get(u).add(new Pair(v, wt));

    }

    int vis[] = new int[N];

    //Now, we perform topo sort using DFS technique 

    //and store the result in the stack st.

    Stack < Integer > st = new Stack < > ();

    for (int i = 0; i < N; i++) {

      if (vis[i] == 0) {

        topoSort(i, adj, vis, st);

      }

    }

    //Further, we declare a vector ‘dist’ in which we update the value of the nodes’

    //distance from the source vertex after relaxation of a particular node.

    int dist[] = new int[N];

    for (int i = 0; i < N; i++) {

      dist[i] = (int)(1e9);

    }

    dist[0] = 0;

    while (!st.isEmpty()) {

      int node = st.peek();

      st.pop();

      for (int i = 0; i < adj.get(node).size(); i++) {

        int v = adj.get(node).get(i).first;

        int wt = adj.get(node).get(i).second;

        if (dist[node] + wt < dist[v]) {

          dist[v] = wt + dist[node];

        }

      }

    }

    for (int i = 0; i < N; i++) {

      if (dist[i] == 1e9) dist[i] = -1;

    }

    return dist;

  }

}

Topological Sort using Kanh's Algorithm (code in JAVA)

import java.util.*;

import org.w3c.dom.Node;

public class graph {

    // Function to return Breadth First Traversal of given graph.

    public static ArrayList<Integer> bfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {

        ArrayList < Integer > bfs = new ArrayList < > (); // stores ans

        boolean vis[] = new boolean[numNodes + 1];

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

        // keep any node from where you want to start your bfs

        q.add(1); // keep value of node here, if your node has 0 then you should keep it

        vis[1] = true;

        while (!q.isEmpty()) {

            int levelSize = q.size(); // Number of nodes at the current level

            for (int i = 0; i < levelSize; i++) {

                Integer node = q.poll();

                bfs.add(node);

                for (Integer it : adj.get(node)) {

                    if (!vis[it]) {

                        vis[it] = true;

                        q.add(it);

                    }

                }

            }

            bfs.add(-1); // Add a marker (-1) to separate levels

        }

        return bfs;

    }

    // Function to return a list containing the DFS traversal of the graph.

    public static void dfs(int node, boolean vis[], ArrayList<ArrayList<Integer>> adj, 

    ArrayList<Integer> ls) {

        

        //marking current node as visited

        vis[node] = true;

        ls.add(node);

        

        //getting neighbour nodes

        for(Integer it: adj.get(node)) {

            if(vis[it] == false) {

                dfs(it, vis, adj, ls);

            }

        }

    }

    public static ArrayList<Integer> dfsOfGraph(int numNodes, ArrayList<ArrayList<Integer>> adj) {

        //boolean array to keep track of visited vertices

        boolean vis[] = new boolean[numNodes+1];

        vis[1] = true; 

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

        dfs(1, vis, adj, ls); 

        return ls; 

    }

 

    // Total number of provinces in given graph 

    public static void dfs(int node, 

       ArrayList<ArrayList<Integer>> adjLs , 

       int vis[]) {

        vis[node] = 1; 

        for(Integer it: adjLs.get(node)) {

            if(vis[it] == 0) {

                dfs(it, adjLs, vis); 

            }

        }

    }

    public static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {

        int vis[] = new int[V + 1]; // +1

        int cnt = 0;

        for (int i = 1; i < V+1; i++) { // Start from vertex 1 (assuming 1-based indexing)

            if (vis[i] == 0) {

                cnt++;

                dfs(i, adj, vis);

            }

        }

        return cnt;

    }

        // Count number of islands

        public static class Pair {

            public int first;

            public int second;

        

            public Pair(int first, int second) {

                this.first = first;

                this.second = second;

            }

        }

        public static void bfs(int ro, int co, int[][] vis, char[][] grid) {

            vis[ro][co] = 1; 

            Queue<Pair> q = new LinkedList<Pair>();

            q.add(new Pair(ro, co)); 

            int n = grid.length; 

            int m = grid[0].length; 

            

            // until the queue becomes empty

            while(!q.isEmpty()) {

                int row = q.peek().first; 

                int col = q.peek().second; 

                q.remove(); 

                

                // traverse in the neighbours and mark them if its a land 

                for(int delrow = -1; delrow<=1;delrow++) {

                    for(int delcol = -1; delcol <= 1; delcol++) {

                        int nrow = row + delrow; 

                        int ncol = col + delcol; 

                // check if neighbour row and column is valid, and is an unvisited land

                        if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m 

                        && grid[nrow][ncol] == '1' && vis[nrow][ncol] == 0) {

                            vis[nrow][ncol] = 1; 

                            q.add(new Pair(nrow, ncol)); 

                        }

                    }

                }

            }

        }

      

          // Function to find the number of islands.

          public static int numIslands(char[][] grid) {

              int n = grid.length; 

              int m = grid[0].length; 

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

              int cnt = 0; 

              for(int row = 0; row < n ; row++) {

                  for(int col = 0; col < m ;col++) {

                      // if not visited and is a land

                      if(vis[row][col] == 0 && grid[row][col] == '1') {

                          cnt++; 

                          bfs(row, col, vis, grid); 

                      }

                  }

              }

              return cnt; 

          }

          

    // Flood-Fill Algorithm

    public static void dfs_floodfill(int row, int col, 

    int[][] ans,

    int[][] image, 

    int newColor, int delRow[], int delCol[],

    int iniColor) {

       // color with new color

       ans[row][col] = newColor; 

       int n = image.length;

       int m = image[0].length; 

       // there are exactly 4 neighbours

       for(int i = 0;i<4;i++) {

           int nrow = row + delRow[i]; 

           int ncol = col + delCol[i]; 

           // check for valid coordinate 

           // then check for same initial color and unvisited pixel

           if(nrow>=0 && nrow<n && ncol>=0 && ncol < m && 

           image[nrow][ncol] == iniColor && ans[nrow][ncol] != newColor) {

               dfs_floodfill(nrow, ncol, ans, image, newColor, delRow, delCol, iniColor); 

           }

       }

   }

   public static int[][] floodFill(int[][] image, int sr, int sc, int newColor)

   {

       // get initial color

       int iniColor = image[sr][sc]; 

       int[][] ans = image; 

       // delta row and delta column for neighbours

       int delRow[] = {-1, 0, +1, 0};

       int delCol[] = {0, +1, 0, -1}; 

       dfs_floodfill(sr, sc, ans, image, newColor, delRow, delCol, iniColor); 

       return ans;  

   }

   // Rotten oranges

   public static class Pair_rottenOranges {

    int row;

    int col;

    int tm;

    Pair_rottenOranges(int _row, int _col, int _tm) {

      this.row = _row;

      this.col = _col;

      this.tm = _tm;

    }

  }

   //Function to find minimum time required to rot all oranges. 

   public static int orangesRotting(int[][] grid) {

    // figure out the grid size

    int n = grid.length;

    int m = grid[0].length;

    // n x m 

    Queue < Pair_rottenOranges > q = new LinkedList < > ();

    // n x m 

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

    int cntFresh = 0;

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

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

        // if cell contains rotten orange

        if (grid[i][j] == 2) {

          q.add(new Pair_rottenOranges(i, j, 0));

          // mark as visited (rotten) in visited array

          vis[i][j] = 2;

        }

        // if not rotten

        else {

          vis[i][j] = 0;

        }

        // count fresh oranges

        if (grid[i][j] == 1) cntFresh++;

      }

    }

    int tm = 0;

    // delta row and delta column

    int drow[] = {-1, 0, +1, 0};

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

    int cnt = 0;

    // until the queue becomes empty

    while (!q.isEmpty()) {

      int r = q.peek().row;

      int c = q.peek().col;

      int t = q.peek().tm;

      tm = Math.max(tm, t);

      q.remove();

      // exactly 4 neighbours

      for (int i = 0; i < 4; i++) {

        int nrow = r + drow[i];

        int ncol = c + dcol[i];

        // check for valid coordinates and 

        // then for unvisited fresh orange

        if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&

          vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {

          // push in queue with timer increased

          q.add(new Pair_rottenOranges(nrow, ncol, t + 1));

          // mark as rotten

          vis[nrow][ncol] = 2;

          cnt++;

        }

      }

    }

    // if all oranges are not rotten

    if (cnt != cntFresh) return -1;

    return tm;

  }

  // To detect cycle in graph using bfs

  public static class Node {

    int first;

    int second;

    public Node(int first, int second) {

        this.first = first;

        this.second = second; 

    }

}

  public static boolean checkForCycle(ArrayList<ArrayList<Integer>> adj, int s,

            boolean vis[], int parent[])

    {

       Queue<Node> q =  new LinkedList<>(); //BFS

       q.add(new Node(s, -1));

       vis[s] =true;

       

       // until the queue is empty

       while(!q.isEmpty())

       {

           // source node and its parent node

           int node = q.peek().first;

           int par = q.peek().second;

           q.remove(); 

           

           // go to all the adjacent nodes

           for(Integer it: adj.get(node))

           {

               if(vis[it]==false)  

               {

                   q.add(new Node(it, node));

                   vis[it] = true; 

               }

        

                // if adjacent node is visited and is not its own parent node

               else if(par != it) return true;

           }

       }

       

       return false;

    }

    

    // function to detect cycle in an undirected graph

    public static boolean isCycle(int numNodes, ArrayList<ArrayList<Integer>> adj)

    {

        boolean vis[] = new boolean[numNodes+1];

        Arrays.fill(vis,false);

        int parent[] = new int[numNodes+1];

        Arrays.fill(parent,-1);  

        

        for(int i=1;i<numNodes+1;i++)

            if(vis[i]==false) 

                if(checkForCycle(adj, i,vis, parent)) 

                    return true;

    

        return false;

    }

    // detect cycle in graph via dfs

    public static  boolean dfs_cycle(int node, int parent, int vis[], ArrayList<ArrayList<Integer>> 

    adj) {

        vis[node] = 1; 

        // go to all adjacent nodes

        for(int adjacentNode: adj.get(node)) {

            if(vis[adjacentNode]==0) {

                if(dfs_cycle(adjacentNode, node, vis, adj) == true) 

                    return true; 

            }

            // if adjacent node is visited and is not its own parent node

            else if(adjacentNode != parent) return true; 

        }

        return false; 

    }

    // Function to detect cycle in an undirected graph.

    public static boolean isCycle_dfs(int numNode, ArrayList<ArrayList<Integer>> adj) {

       int vis[] = new int[numNode+1]; 

       for(int i = 1;i<numNode+1;i++) {

           if(vis[i] == 0) {

               if(dfs_cycle(i, -1, vis, adj) == true) return true; 

           }

       }

       return false; 

    }

    // Distance of nearest cell having 1 | 0/1 Matrix

    //Function to find distance of nearest 1 in the grid for each cell.

    public static class Node_dist {

        int first;

        int second;

        int third; 

        Node_dist(int _first, int _second, int _third) {

            this.first = _first; 

            this.second = _second; 

            this.third = _third; 

        }

    }

     public static int[][] nearest(int[][] grid)

     {

         int n = grid.length; 

         int m = grid[0].length; 

         // visited and distance matrix

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

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

         // <coordinates, steps>

         Queue<Node_dist> q = new LinkedList<Node_dist>();

         // traverse the matrix

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

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

             // start BFS if cell contains 1

                 if(grid[i][j] == 1) {

                     q.add(new Node_dist(i, j, 0)); 

                     vis[i][j] = 1; 

                 }

                 else {

                     // mark unvisted 

                     vis[i][j] = 0; 

                 }

             }

         }

         

         

         

         int delrow[] = {-1, 0, +1, 0}; 

         int delcol[] = {0, +1, 0, -1}; 

         

         

         // n x m x 4 

         // traverse till queue becomes empty

         while(!q.isEmpty()) {

             int row = q.peek().first; 

             int col = q.peek().second; 

             int steps = q.peek().third; 

             q.remove(); 

             dist[row][col] = steps; 

             // for all 4 neighbours

             for(int i = 0;i<4;i++) {

                 int nrow = row + delrow[i]; 

                 int ncol = col + delcol[i]; 

                 // check for valid unvisited cell

                 if(nrow >= 0 && nrow < n && ncol >= 0 && ncol < m

                 && vis[nrow][ncol] == 0)  {

                         vis[nrow][ncol] = 1; 

                     q.add(new Node_dist(nrow, ncol, steps+1));  

                 } 

                 }

             }

         

         // return distance matrix

         return dist; 

     }

     // Surrounded regions replace '0s' with 'X'

     static void dfs(int row, int col,int vis[][], 

    char mat[][], int delrow[], int delcol[]) {

        vis[row][col] = 1; 

        int n = mat.length;

        int m = mat[0].length;

        

        // check for top, right, bottom, left 

        for(int i = 0;i<4;i++) {

            int nrow = row + delrow[i];

            int ncol = col + delcol[i]; 

            // check for valid coordinates and unvisited Os

            if(nrow >=0 && nrow <n && ncol >= 0 && ncol < m 

            && vis[nrow][ncol] == 0 && mat[nrow][ncol] == 'O') {

                dfs(nrow, ncol, vis, mat, delrow, delcol); 

            }

        }

    }

    static char[][] fill(int n, int m, char mat[][])

    {

        int delrow[] = {-1, 0, +1, 0};

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

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

        // traverse first row and last row 

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

            // check for unvisited Os in the boundary rws

            // first row 

            if(vis[0][j] == 0 && mat[0][j] == 'O') {

                dfs(0, j, vis, mat, delrow, delcol); 

            }

            

            // last row 

            if(vis[n-1][j] == 0 && mat[n-1][j] == 'O') {

                dfs(n-1,j,vis,mat, delrow, delcol); 

            }

        }

        

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

            // check for unvisited Os in the boundary columns

            // first column 

            if(vis[i][0] == 0 && mat[i][0] == 'O') {

                dfs(i, 0, vis, mat, delrow, delcol); 

            }

            

            // last column

            if(vis[i][m-1] == 0 && mat[i][m-1] == 'O') {

                dfs(i, m-1, vis, mat, delrow, delcol); 

            }

        }

        

        // if unvisited O then convert to X

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

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

                if(vis[i][j] == 0 && mat[i][j] == 'O') 

                    mat[i][j] = 'X'; 

            }

        }

        

        return mat;

    }

    // Number of Enclaves

    public static int numberOfEnclaves(int[][] grid) {

        Queue<Pair> q = new LinkedList<Pair>();

        int n = grid.length; 

        int m = grid[0].length; 

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

        // traverse boundary elements

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

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

                // first row, first col, last row, last col 

                if(i == 0 || j == 0 || i == n-1 || j == m-1) {

                    // if it is a land then store it in queue

                    if(grid[i][j] == 1) {

                        q.add(new Pair(i, j)); 

                        vis[i][j] = 1; 

                    }

                }

            }

        }

        

        int delrow[] = {-1, 0, +1, 0};

        int delcol[] = {0, +1, +0, -1}; 

        

        while(!q.isEmpty()) {

            int row = q.peek().first; 

            int col = q.peek().second; 

            q.remove(); 

            

            // traverses all 4 directions

            for(int i = 0;i<4;i++) {

                int nrow = row + delrow[i];

                int ncol = col + delcol[i]; 

                // check for valid coordinates and for land cell

                if(nrow >=0 && nrow <n && ncol >=0 && ncol < m 

                && vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {

                    q.add(new Pair(nrow, ncol));

                    vis[nrow][ncol] = 1; 

                }

            }

            

        }

        int cnt = 0;

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

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

                // check for unvisited land cell

                if(grid[i][j] == 1 & vis[i][j] == 0) 

                    cnt++; 

            }

        }

        return cnt;

    }

    // Number of distinct islands

    public static void dfs_islands(int row, int col, int[][] vis,

    int[][] grid, ArrayList < String > vec, int row0, int col0) {

    // mark the cell as visited

    vis[row][col] = 1;

    // coordinates - base coordinates

    vec.add(toString(row - row0, col - col0));

    int n = grid.length;

    int m = grid[0].length;

    // delta row and delta column

     int delrow[] = {-1, 0, +1, 0}; 

     int delcol[] = {0, -1, 0, +1}; 

    // traverse all 4 neighbours

    for (int i = 0; i < 4; i++) {

      int nrow = row + delrow[i];

      int ncol = col + delcol[i];

      // check for valid unvisited land neighbour coordinates

      if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&

        vis[nrow][ncol] == 0 && grid[nrow][ncol] == 1) {

        dfs_islands(nrow, ncol, vis, grid, vec, row0, col0);

      }

    }

  }

  public static String toString(int r, int c) {

    return Integer.toString(r) + " " + Integer.toString(c);

  }

  public static int countDistinctIslands(int[][] grid) {

    int n = grid.length;

    int m = grid[0].length;

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

    HashSet < ArrayList < String >> st = new HashSet < > ();

    // traverse the grid

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

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

        // if not visited and is a land cell

        if (vis[i][j] == 0 && grid[i][j] == 1) {

          ArrayList < String > vec = new ArrayList < > ();

          dfs_islands(i, j, vis, grid, vec, i, j);

          // store it in HashSet

          st.add(vec);

        }

      }

    }

    return st.size();

  }

  // Bipartite Graph using bfs

  public static boolean check(int start, int numNodes, 

    ArrayList<ArrayList<Integer>>adj, int color[]) {

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

    q.add(start); 

    color[start] = 0; 

    while(!q.isEmpty()) {

        int node = q.peek();

        q.remove(); 

        

        for(int it : adj.get(node)) {

            // if the adjacent node is yet not colored

            // you will give the opposite color of the node 

            if(color[it] == -1) {

                

                color[it] = 1 - color[node]; 

                q.add(it); 

            }

            // is the adjacent guy having the same color 

            // someone did color it on some other path 

            else if(color[it] == color[node]) {

                return false; 

            }

        }

    }

    return true; 

    }

    public static boolean isBipartite(int numNodes, ArrayList<ArrayList<Integer>>adj)

    {

        int color[] = new int[numNodes+1]; 

    for(int i = 1;i<numNodes+1;i++) color[i] = -1; 

    

    for(int i = 1;i<numNodes+1;i++) {

        if(color[i] == -1) {

            if(check(i, numNodes, adj, color) == false) {

                return false; 

            }

        }

    }

    return true; 

    }

    // Bipartite Graph(using DFS)

    public static boolean dfs_bipartite(int node, int col, int color[], 

    ArrayList<ArrayList<Integer>>adj) {

        

        color[node] = col; 

        

        // traverse adjacent nodes

        for(int it : adj.get(node)) {

            // if uncoloured

            if(color[it] == -1) {

                if(dfs_bipartite(it, 1 - col, color, adj) == false) return false; 

            }

            // if previously coloured and have the same colour

            else if(color[it] == col) {

                return false; 

            }

        }

        

        return true; 

    }

    public static boolean isBipartite_dfs(int numNodes, ArrayList<ArrayList<Integer>>adj)

    {

        int color[] = new int[numNodes + 1];

    for(int i = 1;i<numNodes+1;i++) color[i] = -1; 

    

    // for connected components

    for(int i = 1;i<numNodes+1;i++) {

        if(color[i] == -1) {

            if(dfs_bipartite(i, 0, color, adj) == false) return false; 

        }

    }

    return true; 

    }

    // Detect cycle in a directed graph (using DFS)

    public static boolean dfsCheck_directedG(int node, ArrayList<ArrayList<Integer>> adj, int vis[], int pathVis[]) {

        vis[node] = 1; 

        pathVis[node] = 1; 

        

        // traverse for adjacent nodes 

        for(int it : adj.get(node)) {

            // when the node is not visited 

            if(vis[it] == 0) {

                if(dfsCheck_directedG(it, adj, vis, pathVis) == true) 

                    return true; 

            }

            // if the node has been previously visited

            // but it has to be visited on the same path 

            else if(pathVis[it] == 1) {

                return true; 

            }

        }

        

        pathVis[node] = 0; 

        return false; 

    }

    // Function to detect cycle in a directed graph via DFS

    public static boolean isCyclic_directedG(int numNodes, ArrayList<ArrayList<Integer>> adj) {

        int vis[] = new int[numNodes+1];

        int pathVis[] = new int[numNodes+1];

        

        for(int i = 1;i<numNodes+1;i++) {

            if(vis[i] == 0) {

                if(dfsCheck_directedG(i, adj, vis, pathVis) == true) return true; 

            }

        }

        return false; 

    }

    // Find eventual safe states

    public static boolean dfsCheck_safeStates(int node, ArrayList<ArrayList<Integer>> adj, int vis[], 

    int pathVis[], int check[]) {

        vis[node] = 1;

        pathVis[node] = 1;

        check[node] = 0;

        // traverse for adjacent nodes

        for (int it : adj.get(node)) {

            // when the node is not visited

            if (vis[it] == 0) {

                if (dfsCheck_safeStates(it, adj, vis, pathVis, check) == true)

                    return true;

            }

            // if the node has been previously visited

            // but it has to be visited on the same path

            else if (pathVis[it] == 1) {

                return true;

            }

        }

        check[node] = 1;

        pathVis[node] = 0;

        return false;

    }

    public static List<Integer> eventualSafeNodes(int numNodes, ArrayList<ArrayList<Integer>> adj) {

        int vis[] = new int[numNodes+1];

        int pathVis[] = new int[numNodes+1];

        int check[] = new int[numNodes+1];

        for (int i = 1; i < numNodes+1; i++) {

            if (vis[i] == 0) {

                dfsCheck_safeStates(i, adj, vis, pathVis, check);

            }

        }

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

        for (int i = 1; i < numNodes+1; i++) {

            if (check[i] == 1)

                safeNodes.add(i);

        }

        return safeNodes;

    }

    // Topological Sort

     public static void dfs_topo(int node, int vis[], Stack<Integer> st,

            ArrayList<ArrayList<Integer>> adj) {

        vis[node] = 1;

        for (int it : adj.get(node)) {

            if (vis[it] == 0)

                dfs_topo(it, vis, st, adj);

        }

        st.push(node);

    }

    // Function to return list containing vertices in Topological order.

    public static int[] topoSort(int numNodes, ArrayList<ArrayList<Integer>> adj) {

        int vis[] = new int[numNodes+1];

        Stack<Integer> st = new Stack<Integer>();

        for (int i = 1; i < numNodes+1; i++) {

            if (vis[i] == 0) {

                dfs_topo(i, vis, st, adj);

            }

        }

        int ans[] = new int[numNodes];

        int i = 0;

        while (!st.isEmpty()) {

            ans[i++] = st.peek();

            st.pop();

        }

        return ans;

    }

    // Topological Sort using Kanh's Algorithm

     // Function to return list containing vertices in Topological order.

     public static int[] topoSort_Kanhs(int numNodes, ArrayList<ArrayList<Integer>> adj) {

        int indegree[] = new int[numNodes+1];

        for (int i = 1; i < numNodes+1; i++) {

            for (int it : adj.get(i)) {

                indegree[it]++;

            }

        }

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

        for (int i = 1; i < numNodes+1; i++) {

            if (indegree[i] == 0) {

                q.add(i);

            }

        }

        int topo[] = new int[numNodes];

        int i = 0;

        while (!q.isEmpty()) {

            int node = q.peek();

            q.remove();

            topo[i++] = node;

            // node is in your topo sort

            // so please remove it from the indegree

            for (int it : adj.get(node)) {

                indegree[it]--;

                if (indegree[it] == 0) {

                    q.add(it);

                }

            }

        }

        return topo;

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // Input the number of nodes.

        System.out.print("Enter the number of nodes: ");

        int numNodes = scanner.nextInt();

        // Create an adjacency list.

        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(numNodes);

        for (int i = 0; i < numNodes + 1; i++) { // numNodes + 2 only if remove empty zero index 

            adjList.add(new ArrayList<>());

        }

        // Input the number of edges.

        System.out.print("Enter the number of edges: ");

        int numEdges = scanner.nextInt();

        // Input the edges (connections between nodes).

        System.out.println("Enter the edges (startNode endNode):");

        for (int i = 0; i < numEdges; i++) {

            int startNode = scanner.nextInt();

            int endNode = scanner.nextInt();

            // Add an edge from startNode to endNode (for directed graph).

            adjList.get(startNode).add(endNode);

            // For undirected graph, add the reverse edge as well.

            // adjList.get(endNode).add(startNode); // Uncomment this line for an undirected graph.

        }

        // Print the adjacency list.

        System.out.println("Adjacency List:");

        for (int i = 1; i < numNodes + 1; i++) { // if start from zero then empty list will also be seen

            System.out.print(i + " -> ");

            for (int neighbor : adjList.get(i)) {

                System.out.print(neighbor + " ");

            }

            System.out.println();

        }

        // BFS of graph

        System.out.println("The bfs of the given graph is:");

        ArrayList<Integer> bfsResult = bfsOfGraph(numNodes, adjList);

        for (Integer node : bfsResult) {

            if (node == -1) {

                System.out.println(); // Print a newline for each level

            } else {

                System.out.print(node + " ");

            }

        }

        // DFS of graph

        System.out.println("The dfs of the given graph is:");

        System.out.println(dfsOfGraph(numNodes, adjList));

        // number of provinces

        System.out.println("The total number of provinces in your graph is: "+numProvinces(adjList, numNodes));

        // count number of islands from the given graph(grid)--> 2D Matrix

        char[][] grid =  {

            {'0', '1', '1', '1', '0', '0', '0'},

            {'0', '0', '1', '1', '0', '1', '0'}

        };

        System.out.println("The total number of island in the grid is: "+numIslands(grid));       

        // Flood Fill algorithm

        System.out.println("The matix after flood fill is below:");

        int[][] image =  {

        {1,1,1},

        {1,1,0},

        {1,0,1}

    };

        // sr = 1, sc = 1, newColor = 2       

        int[][] ans = floodFill(image, 1, 1, 2);

        for(int i = 0; i < ans.length; i++){

            for(int j = 0; j < ans[i].length; j++)

                System.out.print(ans[i][j] + " ");

            System.out.println();

        }

        // Rotten Oranges

        int[][] grid_rottenOranges =  {{0,1,2},{0,1,1},{2,1,1}};

        System.out.println("The minimum time required to rot all the oranges are: "+orangesRotting(grid_rottenOranges));

        // Cycle in graph via BFS

        System.out.println("Is the graph contain cycle(via BFS)? "+isCycle(numNodes,adjList));

         // Cycle in graph via DFS

        System.out.println("Is the graph contain cycle(via DFS)? "+isCycle_dfs(numNodes,adjList));

        // Distance of nearest cell having 1

        int[][] grid_dist = {

            {0,1,1,0},

            {1,1,0,0},

            {0,0,1,1}

        };

        int ans_dist[][] = nearest(grid_dist);

        System.out.println("The nearest distance matrix is as below:");

        for(int i = 0; i < ans_dist.length; i++){

            for(int j = 0; j < ans_dist[i].length; j++){

                System.out.print(ans_dist[i][j] + " "); 

            }

            System.out.println();

        }

        // Surrounded region replace O with X

        System.out.println("Surrounded region matrix after is as below:");

        char mat[][] = {

            {'X', 'X', 'X', 'X'}, 

            {'X', 'O', 'X', 'X'}, 

            {'X', 'O', 'O', 'X'}, 

            {'X', 'O', 'X', 'X'}, 

            {'X', 'X', 'O', 'O'}};

    

            // n = 5, m = 4

            char[][] ans_surround = fill(5, 4, mat);

            for(int i = 0;i < 5;i++) {

                for(int j = 0;j < 4;j++) {

                    System.out.print(ans_surround[i][j] + " ");

                }

                System.out.println();

            }

        // Number of Enclaves

        int grid_enclaves[][] = {

            {0, 0, 0, 0},

            {1, 0, 1, 0},

            {0, 1, 1, 0},

            {0, 0, 0, 0}};

            int ans_enclaves = numberOfEnclaves(grid_enclaves);

            System.out.println("The total number of enclaves are: "+ans_enclaves);

        // Number of distinct islands

        int grid_islands[][] = {

            {1, 1, 0, 1, 1},

            {1, 0, 0, 0, 0},

            {0, 0, 0, 0, 1},

            {1, 1, 0, 1, 1}};

        int ans_islands = countDistinctIslands(grid_islands);

        System.out.println("The total number of distinct islands are: "+ans_islands);

        // Bipartite Graph using bfs

        System.out.println("Is the graph Bipartite(using bfs): "+isBipartite(numNodes, adjList));

        // Bipartite Graph using dfs

        System.out.println("Is the graph Bipartite(using dfs): "+isBipartite_dfs(numNodes, adjList));

        // CYCLE DTECTION IN DIRECTED GRAPH VIA DFS

        System.out.println("Is the directed graph contains cycle: "+isCyclic_directedG(numNodes,adjList));

        // Eventual safe nodes

        System.out.println("The eventual safe nodes are: "+eventualSafeNodes(numNodes,adjList));

        // Topological Sort

        System.out.println("The topological sort of the graph is:");

        int[] ans_topo = topoSort(numNodes, adjList);

        for (int node : ans_topo) {

            System.out.print(node + " ");

        }

        System.out.println("");

        // Topological Sort using Kanh's Algorithm

        int[] ans_topo_kanhs = topoSort(numNodes, adjList);

        System.out.println("The topological sort of the graph using Kanh's Algorithm is:");

        for (int node : ans_topo_kanhs) {

            System.out.print(node + " ");

        }

        System.out.println("");

        scanner.close();

    }

}