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;

    }

}