Topologial sort : Java Implementation

Hello Friends,

I am here with you with another algorithm. Its Topological sorting of a directed graph. Suppose we have few tasks which are interdependent. Lets represent this system in a graph. Each task is represented by a Vertex and will be connected to the Vertices with which it has dependency relation. All Vertices connected to a Vertex V with INCOMING edges on V will be the vertices on  which  Vertex V is dependent upon. So all the tasks represented by the such vertices should be performed before task represented by Vertex V is completed.


A such system represented as graph is as below :





Here for example Before task represented by C is performed , Tasks represented by  A and B must be performed as C has dependency on A and B.

Friends Please find below the code for the same. I have used my own custom HashMap and Stack for its implementation, so you can see a basic internal working of HashMap and Stack also.

public class TopologicalSort {

    public static class Graph {
        int maxSize;
        int size;
        Vertex vertices[];
        HashMap map;
        Stack stack;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            vertices = new Vertex[maxSize];
            map = new HashMap();
            stack = new Stack(maxSize);
        }

        public static class Vertex {
            char name;
            Neighbour adj;
            State state = State.NEW;

            public Vertex(char name) {
                this.name = name;
            }
        }

        public enum State {
            NEW, INPROGRESS, VISITED
        }

        public static class Neighbour {
            Vertex vertex;
            Neighbour next;

            public Neighbour(Vertex vertex, Neighbour next) {
                this.vertex = vertex;
                this.next = next;
            }
        }

        public void invokeTopologicalSorting() {
            for (int i = 0; i < maxSize; i++) {
                exploreVertex(vertices[i]);
            }
            for (int i = 0; !stack.isEmpty(); i++) {
                System.out.println(stack.pop().name);
            }
        }

        /**
         * 
         * The basic idea in this method is to fully explore the vertex, and
         * check if its any Neighbor has been left un explored, if so then need
         * to explore the Neighbor by recursive call to this method. After fully
         * exploring we need to add the vertex to the stack. Thus first the
         * leaves will be pushed to the stack and then when the vertex is re
         * visited by recurrence stack then we see if there are any more
         * neighbor left un explored , if so we need to repeat the process else
         * we come out of the while loop and push the explored vertex in the
         * stack.
         * 
         * Point to note here is: A vertex if considered a Task has dependencies
         * on the vertices which are connected to it by In-coming edges. So for
         * any Vertex, V we need to explore its neighbor first so that they are
         * pushed to the stack first (and will be popped after the current
         * vertex, V).
         */
        public void exploreVertex(Vertex v) {
            if (v.state != State.VISITED) {
                v.state = State.VISITED;
                Neighbour adj = v.adj;
                while (adj != null) {
                    Vertex neighbour = adj.vertex;
                    if (neighbour.state != State.VISITED) {
                        exploreVertex(adj.vertex);
                    }
                    adj = adj.next;
                }
                stack.push(v);
            }
        }

        public void addVertex(char name) {
            vertices[size++] = new Vertex(name);
            map.put(name, vertices[size - 1]);
        }

        public void addNeighbour(char source, char destination) {
            Vertex sourceV = map.get(source);
            Vertex destinationV = map.get(destination);
            sourceV.adj = new Neighbour(destinationV, sourceV.adj);
        }

        public static class Stack {
            Vertex[] stack;
            int maxSize;
            int top = -1;

            public Stack(int maxSize) {
                this.maxSize = maxSize;
                stack = new Vertex[maxSize];
            }

            public void push(Vertex u) {
                stack[++top] = u;
            }

            public Vertex pop() {
                Vertex v = stack[top];
                stack[top] = null;
                top--;
                return v;
            }

            public boolean isEmpty() {
                return top == -1;
            }
        }

        public static class HashMap {
            int prime = 499;
            MapNode[] map = new MapNode[prime];

            public static class MapNode {
                char key;
                Vertex value;
                MapNode next;

                MapNode(char key, Vertex value, MapNode next) {
                    this.key = key;
                    this.value = value;
                    this.next = next;
                }
            }

            public int index(char key) {
                return hashcode(key) % prime;
            }

            public int hashcode(char key) {
                return 31 * key;
            }

            public boolean put(char key, Vertex value) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return false;
                    }
                    temp = temp.next;
                }
                map[index] = new MapNode(key, value, map[index]);
                return true;
            }

            public Vertex get(char key) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return temp.value;
                    }
                    temp = temp.next;
                }
                return null;
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');
        graph.addVertex('G');
        graph.addVertex('H');
        graph.addNeighbour('A', 'C');
        graph.addNeighbour('B', 'C');
        graph.addNeighbour('B', 'D');
        graph.addNeighbour('C', 'E');
        graph.addNeighbour('D', 'F');
        graph.addNeighbour('E', 'F');
        graph.addNeighbour('E', 'H');
        graph.addNeighbour('F', 'G');
        graph.invokeTopologicalSorting();
    }
}

 

Printing elements of a Binary Tree in Spiral Order Traversal using Java.

Hello Friends,

I am here again with yet another algorithm. Lets say we have a binary tree and we wish to traverse it in a special way.
Lets start traversal of the tree from left starting at the 0th level i.e. the root element. As we move to the next level i.e. level 1 then lets start the traversal from right so all the children of the root are traversed right to left. As we move to next level lets reverse the direction of traversal.






For example for the graph above the traversal should be like 1 2 3 4 6 5 7 8. At each level the traversal direction is changed and we start from root with left direction.

Friends, please have a look at the code below for the implementation of this type of traversal. I have used ArrayDeque to get the implementation of Stack ( java.util.Stack has all its methods synchronized and I do not need synchronization in my current implementation, hence I have used java.util.ArrayDeque). We can eaisly replace the ArrayDeque with our custom stack if we want, but for this example below lets proceed with ArrayDeque.

import java.util.ArrayDeque;

public class SpiralBinaryTreeTraversal {

    public static void main(String[] args) {
        int[] nodes = { 1, 2, 3, 4, 5, 6, 7, 8 };
        int left[] = { -1, 3, -1, -1, 7, -1, -1, -1 };
        int right[] = { 2, 4, 5, 6, 8, - 1, -1, -1 };
        printSpiral(nodes, left, right);
    }

    public static void printSpiral(int nodes[], int left[], int right[]) {
        ArrayDeque<Integer> leftStack = new ArrayDeque<>();
        ArrayDeque<Integer> rightStack = new ArrayDeque<>();
        leftStack.push(nodes[0]);
        boolean isLeft = true;
        int current, currentIndex;
        while(!leftStack.isEmpty() || !rightStack.isEmpty()){
            if(isLeft){
                current = leftStack.pop();
                currentIndex = current-1;
                if(left[currentIndex] != -1){
                    rightStack.push(left[currentIndex]);
                }
                if(right[currentIndex] != -1){
                    rightStack.push(right[currentIndex]);
                }
                System.out.println(current);
                if(leftStack.isEmpty()){
                    isLeft = !isLeft;
                }
            }else{
                current = rightStack.pop();
                currentIndex = current-1;
                if(right[currentIndex] != -1){
                    leftStack.push(right[currentIndex]);
                }
                if(left[currentIndex] != -1){
                    leftStack.push(left[currentIndex]);
                }
                System.out.println(current);
                if(rightStack.isEmpty()){
                    isLeft = !isLeft;
                }
            }
        }
    }
}

 

Solution in Java for th problem : With the data for expected Stock prices for the N days, find the maximum profit that can be earned.

Hello Friends,

I am here again with another famous problem. Finding the best purchasing and selling day in stock market to earn maximum profit.

We are given an Integer Array of size N. This represents expected Stock prices for the N days.

We are required to find the maximum profit that can be earned by purchasing and selling the stock on the ideal day.

I have implemented a solution for this in Java which runs in O(n) time complexity.

For example if we have arrays such as : {250,260,200,300,150,140,135}
here maximum profit that can be earned is 100 if stocks are purchased on day 3 and selling is done on day 4.

public class MaximumStockProfit {
    public void maximumProfit(int stocks[]) {
        int n = stocks.length;
        if (n > 0) {
            int globalMaxDiff = Integer.MIN_VALUE; // to store the maximum
                                                    // profit that can be made.
            int globalLowestDay = -1; // Ideal Purchase Day
            int globalLargestDay = -1;// Ideal Selling Day

            int localMinStock = Integer.MAX_VALUE;
            int localLowestDay = -1;
            for (int i = 0; i < n; i++) {
                if (stocks[i] < localMinStock) {
                    localMinStock = stocks[i];
                    localLowestDay = i + 1; // as days are counted from 1 and
                                            // our array is 0 indexed
                }
                if ((stocks[i] - localMinStock) > globalMaxDiff) {
                    globalMaxDiff = stocks[i] - localMinStock;
                    globalLowestDay = localLowestDay;
                    globalLargestDay = i + 1;
                }
            }
            System.out.println("purchase day: " + globalLowestDay + " with price " + stocks[globalLowestDay - 1]
                    + " units selling day: " + globalLargestDay + " with price " + stocks[globalLargestDay - 1]
                    + " units max profit: " + globalMaxDiff);
        } else {
            System.out.println("Stocks data is empty");
        }
    }

    public static void main(String[] args) {
        MaximumStockProfit msp = new MaximumStockProfit();
        int stocks[] = { 2000,3000,1500,2030,4000,5010,2010,2000 };
        msp.maximumProfit(stocks);
    }
}

Solution for Maximum sum sub sequence or maximum sum sub array or maximum sum slice problem in java in O(n) time complexity.

Dear Friends,

Today I am here with a famous array based problem. The problem statement is as follows

Given an Array 'A' of integers of size 'n' , our objective is to find such a sub array from the original array such that the elements in the sub array are in the same order and sequence as in original array and  among all such sub arrays whose sum is maximum.

For example :
if we have a 0 indexed array, A = {-1,-2,0,4,1,2,3,4,0,9,-2,-3,0} , then here our sub array with the maximum sum is as below

{0,4,1,2,3,4,0,9} with the sum as 23, start index in the original array is 2 and end index is 9



Now lets look at the code for the same.

The idea followed is simple. Traverse the array and and keep on updating the global attributes for start, end and sum as new larger sum is found, and keep on adding elements to the local attributes till the local sum is positive, in an hope to find a positive number ahead which will make the sum greatest.  For the negative numbers our maximum sum will be the element with minimum absolute value, like {-8,-3,-5,-1,-3} here our maximum sum is obtained by just single element i.e. -1 , indexed at 3 as adding any other element from all negative valued array will only decrease the sum.

package com.algorithm.arrays.max_sub_sequence;

public class MaximumSumSubsequence {
 public static void main(String[] args) {
  MaximumSumSubsequence mss = new MaximumSumSubsequence();
  int[] a = { -10, -1, -2, 0, -1, 1, 7, 8, -1, 9};
  int sol = mss.solution(a);
  System.out.println(sol);
 }

 public int solution(int[] A) {
  int globalSum = Integer.MIN_VALUE;
  int localSum = 0;
  int globalStart = 0;
  int localStart = 0;
  int globalEnd = 0;
  int localEnd = 0;
  int n = A.length;
  boolean isAllNegative = true;
  int minIndexIfAllNegative = -1;
  int sumIfAllNegative = Integer.MIN_VALUE;
  for (int i = 0; i < n; i++) {
   if (localSum + A[i] >= 0) {
    localSum = localSum + A[i];
    localEnd = i;
    if (localStart == -1) {
     localStart = i;
    }
   } else {
    localStart = -1;
    localSum = 0;
   }

   if (localSum >= globalSum) {
    globalSum = localSum;
    globalStart = localStart;
    globalEnd = localEnd;
   }
   if (A[i] >= 0) {
    isAllNegative = false;
   } else {
    if (sumIfAllNegative < A[i]) {
     sumIfAllNegative = A[i];
     minIndexIfAllNegative = i; 
    }
   }
  }
  if (isAllNegative) {
   globalSum = sumIfAllNegative;
   globalStart = minIndexIfAllNegative;
   globalEnd = minIndexIfAllNegative;
  }
  System.out.println("start index: " + globalStart + " end index: " + globalEnd + " sum: " + globalSum);
  return globalSum;
 }
}

Implementation in Java for Quicksort

Hello friends,

I am here with implementation of quick sort in Java. It is an divide and conquer algorithm,

Its different with merge sort as it does not require to create two temp arrays separately, instead works in place and does operations on the original array itself. It divides the work in segments and work on each segment.

It is not an stable sorting algorithm as it does not take care of preserving the relative ordering of equal elements.

Please find my implementation for the quick sort below

package com.algorithm.sorting;

public class QuickSort {
 
 public static void main(String[] args) {
  int a[] = {5,33,45454,43254,2,67,8,78,8,8,8,85654,5,4,-1,-1,1,234,24,43,4,-7,45,4,-5,544,9,8,7,6,5,4,3,2,11,2,3,4,5,6,7,8,9};
  quicksort(a);
  for(Integer i : a){
   System.out.println(i);
  }
 }

 public static void quicksort(int[] array) {
  conquerAfterDivide(array, 0, array.length - 1);
 }

 private static void conquerAfterDivide(int[] array, int start, int end) {
  if (start < end) {
   int pivotIndex = divide(array, start, end);
   conquerAfterDivide(array, start, pivotIndex - 1); // keep on dividing the left and then conquer
   conquerAfterDivide(array, pivotIndex + 1, end); // keep on dividing the right and then conquer
  }
 }
 /**Actual division of work, work is done on a segment of the array
  * 
  * @param array
  * @param start
  * @param end
  * @return pivot index
  */
 private static int divide(int[] array, int start, int end) {
  int pIndex = start; // choose start and not 0 :) as this is a common mistake , ( I made initially too )
  
  
  // below 4 line ensure to avoid the worst case (sorted array) time complexity of O(n*N)
  // choose the element at the middle as pivot and swap it with element at last 
  int mid = start + ((end-start)/2);
  int temp = array[mid]; 
  array[mid] = array[end];
  array[end] = temp;
  
  
  int pivot = array[end];
  // the motive of this for loop is to find the index
  // for the pivot element
  // i.e. pIndex = number of elements smaller than pivot element
  for (int i = start; i <= end-1; i++) {
   if (array[i] < pivot) {
    // swap & increment pIndex by 1 as one smaller element has been
    // found and has been put at left of the would be final position
    // of pivot element.
    temp = array[i];
    array[i] = array[pIndex];
    array[pIndex] = temp;
    pIndex++;
   }
  }
  // put the pivot to the correct index calculated in the for loop above
  array[end] = array[pIndex];
  array[pIndex] = pivot;

  return pIndex;
 }

}

Implementation in java for Merge Sort.

Hello Friends,

Today I am here with Implementation of Merge Sort in Java. Its a divide and conquer algorithm as it breaks down the input array and then merge them and finally we have a full sorted merged array.


Before discussing merge sort I would like to induce an idea of how  Recursion can be used for  Stack. (actually stack is used to hold the method state in method calls). For this go through the code below

package com.algorithm.sorting;

public class MergeSort {

    public static void mergeSort(int[] array) {
        divide(array);
    }

    public static void divide(int[] array) {
        int n = array.length;
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] left = new int[mid];
        for (int i = 0; i < mid; i++) {
            left[i] = array[i];
        }
        int[] right = new int[n - mid];

        // this loop is interesting and prone for a mistake, so be careful with
        // this loop.
        // it goes from mid to end but in the right array, input needs to be
        // filled from 0 on wards,
        // hence mid is subtracted from i
        for (int i = mid; i < n; i++) {
            right[i - mid] = array[i];
        }

        divide(left);
        divide(right);
        conquer(left, right, array);
    }

    public static void conquer(int[] left, int[] right, int[] array) {
        int i = 0, j = 0, k = 0;
        int nl = left.length;
        int nr = right.length;
        while (i < nl && j < nr) {

            // <= is needed to keep merge sort a stable sort
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        while (i < nl) {
            array[k++] = left[i++];
        }
        while (j < nr) {
            array[k++] = right[j++];
        }
    }
}