DSA Project 1

class LeadersInArray {

    void printLeaders(int [] arr){
        int max_from_right = arr[arr.length - 1];
        System.out.print(max_from_right + " ");

        for(int i = arr.length-2; i>=0; i--){
            if(max_from_right < arr[i]){
                max_from_right = arr[i];
                System.out.print(max_from_right + " ");
            }
        }
    }

    public static void main(String[] args) {
        LeadersInArray lead = new LeadersInArray();
        int arr1[] = {16, 17, 4, 3, 5, 2};
        int arr2[] = {1, 2, 3, 4, 0};
        lead.printLeaders(arr1);
        lead.printLeaders(arr2);
    }
}

public class ReverseWordsInString {
    
    void reverseWords(String str){
        String [] words = str.split(".");
        for(int i = words.length-1; i>=0; i--){
            System.out.print(words[i]+".");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ReverseWordsInString rs = new ReverseWordsInString();
        String str = "i.like.this.program.very.much";
        String str2 = "pqr.mno";
        rs.reverseWords(str);
        rs.reverseWords(str2);
    }
}​

4. REMOVE DUPLICATES

Given a string, the task is to remove duplicates from it. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string. Original order of characters must be kept same. Complete the function that takes a string and prints the modified string without duplicates and same order of characters.

Constraints:
1 <= |string|<= 1000

A.
The idea is to keep track of visited characters from given input string through an integer array of size 256 (All possible characters).

Steps: 

1. Create an integer array of size 256 in order to keep track of all possible characters.
2. Iterate over the input string, and for each character :
3. Lookup into the array with the ASCII value of character as index: 
   • If value at index is 0, then copy the character into original input array and increase the endIndex also update the value at index as -1.
   • Else skip the character.

import java.util.Arrays;

public class RemoveDuplicatesFromString {
    static char[] removeDuplicatesFromString(String string)
    {
        //table to keep track of visited characters
        int[] table = new int[256];
        char[] chars = string.toCharArray();

        //to keep track of end index of resultant string
        int endIndex = 0;
        
        for(int i = 0; i < chars.length; i++)
        {
            if(table[chars[i]] == 0)
            {
                table[chars[i]] = -1;
                chars[endIndex++] = chars[i];
            }
        }
        
        return Arrays.copyOfRange(chars, 0, endIndex);
    }

    // Driver code
    public static void main(String[] args)
    {
        String str1 = "skilllync";
        String str2 = "skill lync courses";
        System.out.println(removeDuplicatesFromString(str1));
        System.out.println(removeDuplicatesFromString(str2));
    }
}

Output :
skilync
skil yncoure

Time Complexity : O(n) as we are looping through n elements of the string
Space Complexity : O(1). Even though we are creating an array of 256 characters and using extra space, for any amount input we get the extra space is going to be constant and so it's going to be O(1)

Video Link : https://drive.google.com/file/d/1AAxg09myFIM7dpbIwcNCaziJ73WNEv4g/view?usp=sharing

5. FINDING MIDDLE ELEMENT IN A LINKED LIST

Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3. If there are even nodes, then there would be two middle nodes, we need to print the
second middle element. For example, if given linked list is 1 ->2->3->4->5->6 then the output should be 4.

The task is to complete the function getMiddle() which takes the list reference and returns data of the middle element of the linked list.

Expected Time Complexity: O(N).
Expected Space Complexity: O(1).

Constraints:
1 <= T <= 500
1 <= N <= 5000

A. 

There are different approaches to finding the middle of a linked list. First one is to traverse through the linked list and find the length by incrementing it for each node until we reach null. And then we get the middle by diving the length obtained by 2. Next, we traverse the linked list again till we reach the middle and then print the middle node. This takes O(n) time complexity. 

Another method is by using two pointers. We keep both pointers at the head first and then we move the fast pointer by 2 while moving the slow pointer by 1 through the linked list. So the logic is that, when the fast pointer reaches the end of the linked list the slow pointer would've reached the middle. This method also has a time complexity of O(n). Below is the code implementation for the second method. 

public class FindMiddleOFLL {
    static Node head;
    int count = 0;

    public Node createNode(int data, Node head){
        Node temp = head;
        Node n = new Node(data);
        if(head==null){
            head = n;
            return head;
        }
        while(head.next!=null){
            head = head.next;
        }
        head.next = n;
        return temp;
    }

    void findMiddle(Node head){
        Node slow_ptr = head;
        Node fast_ptr = head;
        if(head!=null){
            while(fast_ptr!=null && fast_ptr.next!=null){
                slow_ptr = slow_ptr.next;
                fast_ptr = fast_ptr.next.next;
            }
            System.out.println(slow_ptr.data);
        }
    }

    public static void main(String[] args) {
        FindMiddleOFLL ll = new FindMiddleOFLL();
        head = ll.createNode(1, head);
        head = ll.createNode(2, head);
        head = ll.createNode(3, head);
        head = ll.createNode(4, head);
        head = ll.createNode(5, head);
        head = ll.createNode(6, head);

        ll.findMiddle(head);
    }
}

6. REVERSE A LINKED LIST

Given a linked list of N nodes. The task is to reverse this list.

The task is to complete the function reverseList(givenList) with givenList reference and returns the list after reversing it.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 104

public class ReverseLinkedList {
    static Node head;

    // create a new node and add at end
    public Node createNode(int data, Node head){
        Node temp = head;
        Node n = new Node(data);
        if(head==null){
            head = n;
            return head;
        }
        while(head.next!=null){
            head = head.next;
        }
        head.next = n;
        return temp;
    }

    Node reverseLL(Node head){
        Node prev = null;
        Node current = head;
        Node next;

        while(current!=null){
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
        return head;
    }

    void printList(Node node){
        Node temp = node;
        while(temp!=null){
            System.out.print(temp.data + "-->");
            temp = temp.next;
        }
        System.out.print("NULL");
    }

    public static void main(String[] args) {
        ReverseLinkedList rll = new ReverseLinkedList();
        head = rll.createNode(1, head);
        head = rll.createNode(2, head);
        head = rll.createNode(3, head);
        head = rll.createNode(4, head);
        rll.printList(head);
        head = rll.reverseLL(head);
        System.out.println();
        rll.printList(head);
    }
}

7. PAIRWISE SWAP ELEMENTS OF A LINKED LIST

Given a singly linked list of size N. The task is to swap elements in the linked list pairwise. For example, if the input list is 1 2 3 4, the resulting list after swaps will be 2 1 4 3.

Complete the function pairWiseSwap() which takes the the linked list and retu rns the modified linked list after swapping pairwise nodes.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 103

A. 

We start from the head node and traverse the list. While traversing we swap data of each node with its next node’s data. 

public class PairwiseSwapLL {
    static Node head;

    Node pairwiseSwap(Node head){
        Node temp = head;

        while(temp !=null && temp.next != null){
            swap(temp, temp.next);
            temp = temp.next.next;
        }
        return head;
    }

    void swap(Node n1, Node n2){
        int temp = n1.data;
        n1.data = n2.data;
        n2.data = temp;
    }

    public Node createNode(int data, Node head){
        Node temp = head;
        Node n = new Node(data);
        if(head==null){
            head = n;
            return head;
        }
        while(head.next!=null){
            head = head.next;
        }
        head.next = n;
        return temp;
    }

    public void printList(Node head){
        while(head!=null){
            System.out.print(head.data + "-->");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        PairwiseSwapLL ps = new PairwiseSwapLL();
        head = ps.createNode(1, head);
        head = ps.createNode(2, head);
        head = ps.createNode(3, head);
        head = ps.createNode(4, head);

        ps.printList(head);
        ps.pairwiseSwap(head);
        ps.printList(head);
    }

}

Output :
1-->2-->3-->4-->NULL
2-->1-->4-->3-->NULL

Time Complexity : O(n) as we traverse through n nodes of a linked list 
Space Complexity : O(1) as we do not use any extra space

Video Link : https://drive.google.com/file/d/1phz66wYQGtwUJAfRyC8WyZcIZk4ke4wP/view?usp=sharing

8. ADD TWO NUMBERS REPRESENTED BY LINKED LISTS

Given two numbers represented by two linked lists of size N and M. The task is to return a sum list. The sum list is a linked list representation of the addition of two input numbers.

Complete the function addTwoLists() which takes both the linked lists and returns the new list.

Expected Time Complexity: O(N) + O(M)
Expected Auxiliary Space: O(N) + O(M)

Constraints:
1 <= N, M <= 5000

A.

We solve this problem like how we solved addition of two numbers in elementary school where we hold our fingers in our hands and then count them all together to add up both the numbers. If the sum was of a two digit number, we first add the untits place numbers and then if the sum goes more than 9 we have a carry over in our mind and we write down just the units sum. And then we add that carry over along with the sum of the numbers in the tens place. The idea to solve this problem is the same. We traverse both lists and one by one pick nodes of both lists and add the values. If the sum is more than 9 then make carry as 1 and reduce sum. If one list has more elements than the other then consider the remaining values of this list as 0. 

Steps :
1. First reverse both the linked lists. Then call the addTwoLists() method on the reversed lista.
2. Traverse the two linked lists from start to end
2. Add the two digits each from respective linked lists.
3. If one of the lists has reached the end then take 0 as its digit.
4. Continue it until both the end of the lists.
5. If the sum of two digits is greater than 9 then set carry as 1 and the current digit as sum % 10
6. Finally we reverse the output list back default order.

class Node{
    int data;
    Node next;

    Node(int data){
        this.data = data;
        this.next = null;
    }
}


public class addTwoNosRepresentedByLL {
    static Node head1, head2, head3, head4;

    // create the lists by adding nodes to the end
    public Node createNode(int data, Node head){
        Node temp = head;
        Node n = new Node(data);
        if(head==null){
            head = n;
            return head;
        }
        while(head.next!=null){
            head = head.next;
        }
        head.next = n;
        return temp;
    }
    
    // reverse the linked list
    static Node reverseLL(Node head){
        Node prev = null;
        Node current = head;
        Node next;

        while(current!=null){
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
        return head;
    }

   
    /* Adds contents of two linked lists and return the head node of resultant list */
    Node addTwoLists(Node first, Node second)
    {
        // res is head node of the resultant list
        Node res = null;
        Node prev = null;
        Node temp = null;
        int carry = 0, sum;
 
        // while both lists exist
        while (first != null || second != null) {
            // Calculate value of next digit in resultant list. The next digit is sum of following things :
            // (i)  Carry
            // (ii) Next digit of first list (if there is a next digit)
            // (ii) Next digit of second list (if there is a next digit)
            sum = carry + (first != null ? first.data : 0) + (second != null ? second.data : 0);
 
            // update carry for next calulation
            carry = (sum >= 10) ? 1 : 0;
 
            // update sum if it is greater than 10
            sum = sum % 10;
 
            // Create a new node with sum as data
            temp = new Node(sum);
 
            // if this is the first node then set it as head of the resultant list
            if (res == null) {
                res = temp;
            }
 
            // If this is not the first node then connect it to the rest.
            else {
                prev.next = temp;
            }
 
            // Set prev for next insertion
            prev = temp;
 
            // Move first and second pointers
            // to next nodes
            if (first != null) {
                first = first.next;
            }
            if (second != null) {
                second = second.next;
            }
        }
 
        if (carry > 0) {
            temp.next = new Node(carry);
        }
 
        // return head of the resultant list
        return res;
    }
 
    void printList(Node head)
    {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println("");
    }
 
    public static void main(String[] args)
    {
        addTwoNosRepresentedByLL list = new addTwoNosRepresentedByLL();
 
        // creating first list
        head1 = list.createNode(4, head1);
        head1 = list.createNode(5, head1);
        System.out.print("First List is ");
        list.printList(head1);
 
        // creating seconnd list
        head2 = list.createNode(3, head2);
        head2 = list.createNode(4, head2);
        head2 = list.createNode(5, head2);
        System.out.print("Second List is ");
        list.printList(head2);

        Node Rhead1 = reverseLL(head1);
        Node Rhead2 = reverseLL(head2);
 
        // add the two lists and see the result
        Node rs = list.addTwoLists(Rhead1, Rhead2);
        Node result = reverseLL(rs);
        System.out.print("Resultant List is ");
        list.printList(result);

        System.out.println();

        addTwoNosRepresentedByLL list2 = new addTwoNosRepresentedByLL();
 
        // creating first list
        head3 = list2.createNode(6, head3);
        head3 = list2.createNode(3, head3);
        System.out.print("First List is ");
        list.printList(head3);
 
        // creating seconnd list
        head4 = list2.createNode(7, head4);
        System.out.print("Second List is ");
        list.printList(head4);

        Node Rhead3 = reverseLL(head3);
        Node Rhead4 = reverseLL(head4);
 
        // add the two lists and see the result
        Node rs2 = list.addTwoLists(Rhead3, Rhead4);
        Node result2 = reverseLL(rs2);
        System.out.print("Resultant List is ");
        list.printList(result2);
    }
}

Output :
First List is 4 5
Second List is 3 4 5
Resultant List is 3 9 0

First List is 6 3
Second List is 7
Resultant List is 7 0

Time Complexity: O(m + n), where m and n are numbers of nodes in first and second lists respectively. The lists need to be traversed only once.
Space Complexity: O(m + n) as a temporary linked list is needed to store the output number

Video Link : https://drive.google.com/file/d/19j4Q2TDGt7j1GqsTlx7pcqUYbej_eKcm/view?usp=sharing

9. BINARY TREE TO DLL

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In -Place. The left and right references in nodes are to be used as previous and next references respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.

Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL .

Expected Time Complexity: O(N).
Expected Space Complexity : O(H). H is the height of the tree and this space is used implicitly for recursion stack.

Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000

A.

We perform in order traversal of the binary tree and while doing so, keep track of the previously visited node in a variable prev. For every visited node, we make it next to the prev and previous of this node as prev. 

class Node {
    int key;
    Node left, right;

    public Node(int key){
        this.key = key;
        left = right = null;
    }
}

public class BinaryTreeToDLL {
    Node root, head;
      
    // Initialize previously visited node as NULL. Since this is static it is the same value that's is accessible in all recursive calls
    static Node prev = null;
  

    void BinaryTree2DoubleLinkedList(Node root){
        // Base case
        if (root == null)
            return;
  
        // Recursively convert left subtree
        BinaryTree2DoubleLinkedList(root.left);
  
        // Now convert this node
        if (prev == null)
            head = root;
        else
        {
            root.left = prev;
            prev.right = root;
        }
        prev = root;
  
        // Finally convert right subtree
        BinaryTree2DoubleLinkedList(root.right);
    }
  
    void printList(Node node)
    {
        while (node != null)
        {
            System.out.print(node.key + "==");
            node = node.right;
        }
    }
  
    // Driver program to test above functions
    public static void main(String[] args)
    {
        BinaryTreeToDLL tree = new BinaryTreeToDLL();
        tree.root = new Node(10);
        tree.root.left = new Node(12);
        tree.root.right = new Node(15);
        tree.root.left.left = new Node(25);
        tree.root.left.right = new Node(30);
        tree.root.right.left = new Node(36);
  
        tree.BinaryTree2DoubleLinkedList(tree.root);
          
        tree.printList(tree.head);
  
    }
}

Output :
25==12==30==10==36==15

Time Complexity : O(n) as we are doing a simple in order traversal where n is number of nodes in given binary tree
Space Complexity : O(h) where h is the height of the tree and this space is used implicitly for recursion stack.

Video Link : https://drive.google.com/file/d/1poNtMoSuYtYvQb5kXzPAii2rracdsTp7/view?usp=sharing

10. BELLMAN FORD ALGORITHM

Implement the Bellman Ford Algorithm to find Shortest paths to all vertices from a single source.

Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.

If there is a negative weight cycle then print -1

Expected Time Complexity- O(VE)

A.

Bellman-Ford algorithm is used to find shortest distance to all vertices when there are negative weights in a graph. We have already discussed Dijkstra’s algorithm, which is a Greedy algorithm. Dijkstra doesn’t work for Graphs with negative weight edges, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems. Bellman ford follows similar steps like Dijkstra’s algorithm, the main difference being all edges would be processed through relaxation for |V| - 1 times, instead of just once. 

Steps :
1. We initializes distances from the source to all vertices as infinite and distance to the source itself as 0. We create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.
2. For calculating shortest distances, we do the following |V|-1 times where |V| is the number of vertices in given
graph :
a) If dist[v] > dist[u] + weight of edge uv, then we update dist[v] = dist[u] + weight of edge uv

3. Next we also check for negative weight cycles in the graph. step 2 guarantees the shortest distances if the graph doesn’t contain a negative weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative weight cycle. So we check if dist[v] > dist[u] + weight of edge uv, then Graph contains negative weight cycle and we print -1. 

This algorithm calculates shortest paths in a bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on. After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edge

class Graph {
    // A class to represent a weighted edge in graph
    class Edge {
        int src, dest, weight;
        Edge()
        {
            src = dest = weight = 0;
        }
    };
 
    int V, E;
    Edge edge[];
 
    // Creates a graph with V vertices and E edges
    Graph(int v, int e)
    {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i < e; ++i){
            edge[i] = new Edge();
        }
    }
 
    // The main function that finds shortest distances from src
    // to all other vertices using Bellman-Ford algorithm. The
    // function also detects negative weight cycle
    void BellmanFord(Graph graph, int src)
    {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];
 
        // Step 1: Initialize distances from src to all other
        // vertices as INFINITE
        for (int i = 0; i < V; ++i){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[src] = 0;
 
        // Step 2: Relax all edges |V| - 1 times. A simple
        // shortest path from src to any other vertex can
        // have at-most |V| - 1 edges
        for (int i = 1; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]){
                    dist[v] = dist[u] + weight;
                }
            }
        }
 
        // Step 3: check for negative-weight cycles. The above
        // step guarantees shortest distances if graph doesn't
        // contain negative weight cycle. If we get a shorter
        // path, then there is a cycle.
        for (int j = 0; j < E; ++j) {
            int u = graph.edge[j].src;
            int v = graph.edge[j].dest;
            int weight = graph.edge[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println(-1);
                return;
            }
        }
        printArr(dist, V);
    }
 
    // A utility function used to print the solution
    void printArr(int dist[], int V)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; ++i)
            System.out.println(i + "tt" + dist[i]);
    }
 
    // Driver method to test above function
    public static void main(String[] args)
    {
        int V = 5; // Number of vertices in graph
        int E = 8; // Number of edges in graph
 
        Graph graph = new Graph(V, E);
 
        // add edge 0-1 (or A-B in above figure)
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = -1;
 
        // add edge 0-2 (or A-C in above figure)
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 4;
 
        // add edge 1-2 (or B-C in above figure)
        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = 3;
 
        // add edge 1-3 (or B-D in above figure)
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 2;
 
        // add edge 1-4 (or A-E in above figure)
        graph.edge[4].src = 1;
        graph.edge[4].dest = 4;
        graph.edge[4].weight = 2;
 
        // add edge 3-2 (or D-C in above figure)
        graph.edge[5].src = 3;
        graph.edge[5].dest = 2;
        graph.edge[5].weight = 5;
 
        // add edge 3-1 (or D-B in above figure)
        graph.edge[6].src = 3;
        graph.edge[6].dest = 1;
        graph.edge[6].weight = 1;
 
        // add edge 4-3 (or E-D in above figure)
        graph.edge[7].src = 4;
        graph.edge[7].dest = 3;
        graph.edge[7].weight = -3;
 
        graph.BellmanFord(graph, 0);
    }
}

Output :
Vertex Distance from Source
0   0
1   -1
2   2
3   -2
4   1

Time Complexity : O(VE) where V is the vertices of the graph and E are the edges of the graph
Space Complexity : O(V) as we are creating a dist array with size of V where V is number of vertices. 

Video Link : https://drive.google.com/file/d/1bgADBVWt6rV6en03meCAKSWG7PdDeb-1/view?usp=sharing

11. MINIMUM SWAPS TO SORT

Given an array of integers. Find the minimum number of swaps required to sort the array in non-decreasing order.
Complete the function minSwaps() which takes the array arr[] and prints the minimum number of swaps required to sort the array. If the array is already sorted, return 0.

Constraints:
1 <= size of A <= 105
1 <= A[] <= 106

Expected Time Complexity: O(NlogN).
Expected Space Complexity : O(N).

A.

This problem can be solved by visualizing it as a graph. We have n nodes and an edge directed from node i to j, if the element at i'th index must be present at j'th index in the sorted array. Thus, the graph will contain many non intersecting cycles. Now a cycle with 2 nodes will inly require 1 swap to reach the correct ordering and a cycle with 3 nodes will require 2 swaps and so on. So first we store the indexes of the elements given in the array in a hashmap. Next, we sort this array. Now we go over every element to check if it has been already visited or if it is present in the right place. If any of these is true, we go on over to the next iteration. If both are false, we check for cycle by moving to the next node from one node. If cycle is greater than 0 we say answer = answer + (cycles - 1). We check this for all elements and then finally return the answer. 

import java.util.Arrays;
import java.util.HashMap;

public class MinNumberOfSwaps {
    public static int minSwaps(int[] nums)
    {
        int len = nums.length;
        HashMap<Integer, Integer> hM = new HashMap<>();
        for(int i=0;i<len;i++){
            hM.put(nums[i], i);
        }
             
        Arrays.sort(nums);  
         
        // To keep track of visited elements. Initialize all elements as not visited or false.
        boolean[] visited = new boolean[len];
        Arrays.fill(visited, false);
         
          // Initialize result
        int ans = 0;
        for(int i=0;i<len;i++) {
            // already swapped and corrected or already present at correct pos
            if(visited[i] || hM.get(nums[i]) == i){
                continue;
            }
                    
            int j = i, cycle_size = 0;
            while(!visited[j]) {
                visited[j] = true;
                    
                // move to next node
                j = hM.get(nums[j]);
                cycle_size++;
            }
                
            // Update answer by adding current cycle.
            if(cycle_size > 0) {
                ans += (cycle_size - 1);
            }
        }
        return ans;
    }
    public static void main(String[] args){
        int []a = {1, 5, 4, 3, 2};
        System.out.println(minSwaps(a));
        int []b = {8, 9, 16, 15};
        System.out.println(minSwaps(b));
    }
}

Output :
2
1

Time Complexity : O(nlogn) as we are sorting the array using a dual pivot quick sort algorithm
Space Complexity : O(n) as we are creating a hash map of n elements and also a boolean visited array

Video Link : https://drive.google.com/file/d/17x09JUfg-R7r_uKFLYoQSRY5LcGNwbNg/view?usp=sharing

12. GET MINIMUM ELEMENT FROM STACK

You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.

Complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer popped out from the stack and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)

Expected Time Complexity : O(1) for all the 3 methods.
Expected Space Complexity : O(1) for all the 3 methods.

Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

A. 

In this problem, we define a variable minEle that stores the current minimum element in the stack. To handle the case when the minimum element is removed, we push “2x – minEle” into the stack instead of x so that previous minimum element can be retrieved using current minEle and its value stored in stack. Below are detailed steps and explanation of working.

Push(x) : Inserts x at the top of stack. 

• If stack is empty, insert x into the stack and make minEle equal to x.
• If stack is not empty, compare x with minEle. Two cases arise:
  • If x is greater than or equal to minEle, simply insert x.
  • If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x. For example, let previous minEle was 3. Now we want to insert 2. We update minEle as 2 and insert 2*2 – 3 = 1 into the stack.

Pop() : Removes an element from top of stack. 

• Remove element from top. Let the removed element be y. Two cases arise:
  • If y is greater than or equal to minEle, the minimum element in the stack is still minEle.
  • If y is less than minEle, the minimum element now becomes (2*minEle – y), so update (minEle = 2*minEle – y). This is where we retrieve previous minimum from current minimum and its value in stack. For example, let the element to be removed be 1 and minEle be 2. We remove 1 and update minEle as 2*2 – 1 = 3.

 import java.util.Stack;

public class getMinElement {
    Stack s;
    Integer minEle;
 
    // Constructor
    getMinElement() { 
        s = new Stack(); }
 
    // Prints minimum element of MyStack
    void getMin()
    {
        // Get the minimum number in the entire stack
        if (s.isEmpty()){
            System.out.println("Stack is empty");
        }
 
        // variable minEle stores the minimum element
        // in the stack.
        else{
            System.out.println("Minimum Element in the " + " stack is: " + minEle);
        }
    }
 
    // prints top element of MyStack
    void peek(){
        if (s.isEmpty()){
            System.out.println("Stack is empty ");
            return;
        }
 
        Integer t = s.peek(); // Top element.
 
        System.out.print("Top Most Element is: ");
 
        // If t < minEle means minEle stores value of t.
        if (t < minEle){
            System.out.println(minEle);
        }
        else{
            System.out.println(t);
        }
    }
 
    // Removes the top element from MyStack
    void pop(){
        if (s.isEmpty()){
            System.out.println("Stack is empty");
            return;
        }
 
        System.out.print("Top Most Element Removed: ");
        Integer t = s.pop();
 
        // Minimum will change as the minimum element of the stack is being removed.
        if (t < minEle){
            System.out.println(minEle);
            minEle = 2*minEle - t;
        }
 
        else{
            System.out.println(t);
        }
    }
 
    // Insert new number into MyStack
    void push(Integer x){
        if (s.isEmpty()){
            minEle = x;
            s.push(x);
            System.out.println("Number Inserted: " + x);
            return;
        }
 
        // If new number is less than original minEle
        if (x < minEle){
            s.push(2*x - minEle);
            minEle = x;
        }
 
        else{
            s.push(x);
        }
 
        System.out.println("Number Inserted: " + x);
    }
    public static void main(String[] args)
    {
        getMinElement s = new getMinElement();
        s.push(2);
        s.push(3);
        s.pop();
        s.getMin();
        s.push(1);
        s.getMin();
    }
}

Output :
Number Inserted: 2
Number Inserted: 3
Top Most Element Removed: 3
Minimum Element in the stack is: 2
Number Inserted: 1
Minimum Element in the stack is: 1

Time Complexity and Space Complexity : O(1) for push, pop and getMin() methods. 

Video Link : https://drive.google.com/file/d/1ktGWif8DqBOIOdRep5hPG-uwb_CwAm6b/view?usp=sharing