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++];
        }
    }
}

Implementation in java for Dijkstra's algorithm to find the shortest path

Hello Friends,

Today I am here with you with Dijkstra's algorithm to find the shortest path.
Dijkstra Algorithm uses MinPriorityQueue which usually is implemented using MinHeap.  MinPriorityQueue is a queue which always removes the item with lowest value and not in usual FIFO way.  But as Heap implementation is little complex so first lets use simple Queue and modify its remove() method to implement the MinPriorityQueue. Later in the post I have implemented the algorithm with MinHeap also, which is better in performance.




For the first implementation using simple Queue, I am using above graph to to compute the minimum distances from Node 1 to all other nodes.  Note that Nodes 9,10 and 11 are not reachable from our source node.

/**
 * 
 * @author krishna kumar
 * 
 *         This is a basic implementation of Dijkstra Algorithm using Simple Queue with Graph using Adjacency list.
 *
 */
public class Graph {

    private Node[] vertices; // stores the nodes of the graph
    private int size; // number of nodes in the graph
    private MinPriorityQueue queue;

    public Graph(int size) {
        this.size = size;
        vertices = new Node[size];
        addNodes();
        queue = new MinPriorityQueue(size);
    }

    public class Node {
        int name;
        int cost;
        Neighbour neighbourList;
        State state;

        Node(int name) {
            this.name = name;
            state = State.NEW;
            cost = Integer.MAX_VALUE;
        }
    }

    public class Neighbour {
        int index;
        int weight;
        Neighbour next;

        public Neighbour(int index, Neighbour next, int weight) {
            this.index = index;
            this.next = next;
            this.weight = weight;
        }
    }

    private void addNodes() {
        for (int i = 1; i <= size; i++) {
            addNode(i);
        }
    }

    public void addNode(int name) {
        vertices[name - 1] = new Node(name);
    }

    public void addEdge(int sourceName, int destiName, int weight) {
        int srcIndex = sourceName - 1;
        int destiIndex = destiName - 1;
        Node srcNode = vertices[srcIndex];
        Node destiNode = vertices[destiIndex];
        srcNode.neighbourList = new Neighbour(destiIndex, srcNode.neighbourList, weight);
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        destiNode.neighbourList = new Neighbour(srcIndex, destiNode.neighbourList, weight);
    }

    public void computeSortestPathsFrom(int sourceNodeName) {
        for (int i = 0; i < size; i++) {
            if (vertices[i].name == sourceNodeName) {
                applyDijkstraAlgorithm(vertices[i]);
                break;// in this case we need not traverse the nodes which are
                        // not reachable from the source Node
            }
        }
    }

    /**
     * The algorithm is based upon BFS.
     */
    private void applyDijkstraAlgorithm(Node sourceNode) {
        queue.add(sourceNode);
        sourceNode.state = State.IN_Q;
        sourceNode.cost = 0; // cost of reaching Source from Source Node itself
                                // is 0, for all others we still need to
                                // discover the cost so the cost for them has
                                // been already initialized to Integer.MAX_VALUE
        while (!queue.isEmpty()) {
            Node visitedNode = queue.remove();
            visitedNode.state = State.VISITED;
            Neighbour connectedEdge = visitedNode.neighbourList;
            while (connectedEdge != null) {
                Node neighbour = vertices[connectedEdge.index];
                // adding the not enqued neighbor nodes in the queue
                if (neighbour.state == State.NEW) {
                    queue.add(neighbour);
                    neighbour.state = State.IN_Q;
                }
                // updating [relaxing] the costs of each non visited neighbor
                // node if its
                // have been made lesser.
                if (neighbour.state != State.VISITED && ((connectedEdge.weight + visitedNode.cost) < neighbour.cost)) {
                    neighbour.cost = connectedEdge.weight + visitedNode.cost;
                }
                connectedEdge = connectedEdge.next;
            }
        }
        
        //now printing the shortest distances
        for(int i = 0; i < size; i++){
            if(vertices[i].cost != Integer.MAX_VALUE){
                System.out.println("distance from "+sourceNode.name +" to "+vertices[i].name+" is " +vertices[i].cost);
            }else{
                System.out.println(vertices[i].name +" is not reachable from "+sourceNode.name);
            }
        }
    }

    public enum State {
        NEW, IN_Q, VISITED
    };

    /**
     * 
     * This is a simple queue implemented using array. Ideally MinPriority Queue
     * should be implemented using Heap but for making it easy to understand
     * currently implementation of Normal Queue (its remove() method()) has been
     * modified.
     *
     */
    public class MinPriorityQueue {
        Node[] queue;
        int maxSize;
        int rear = -1, front = -1;

        MinPriorityQueue(int maxSize) {
            this.maxSize = maxSize;
            queue = new Node[maxSize];
        }

        public void add(Node node) {
            queue[++rear] = node;
        }

        public Node remove() {
            Node minValuedNode = null;
            int minValue = Integer.MAX_VALUE;
            int minValueIndex = -1;
            front++;
            for (int i = front; i <= rear; i++) {
                if (queue[i].state == State.IN_Q && queue[i].cost < minValue) {
                    minValue = queue[i].cost;
                    minValuedNode = queue[i];
                    minValueIndex = i;
                }
            }

            swap(front, minValueIndex); // this ensures deletion is still done
                                        // from front;
            queue[front] = null;// lets not hold up unnecessary references in
                                // the queue
            return minValuedNode;
        }

        public void swap(int index1, int index2) {
            Node temp = queue[index1];
            queue[index1] = queue[index2];
            queue[index2] = temp;
        }

        public boolean isEmpty() {
            return front == rear;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(11);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 2, 3);
        graph.addEdge(2, 5, 5);
        graph.addEdge(2, 4, 3);
        graph.addEdge(3, 5, 8);
        graph.addEdge(3, 6, 5);
        graph.addEdge(4, 5, 1);
        graph.addEdge(4, 7, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(5, 8, 8);
        graph.addEdge(5, 7, 2);
        graph.addEdge(6, 8, 15);
        graph.addEdge(7, 8, 5);
        graph.addEdge(9, 11, 2);
        graph.computeSortestPathsFrom(1);
    }
}

Output :
distance from 1 to 1 is 0
distance from 1 to 2 is 3
distance from 1 to 3 is 1
distance from 1 to 4 is 6
distance from 1 to 5 is 7
distance from 1 to 6 is 6
distance from 1 to 7 is 9
distance from 1 to 8 is 14
9 is not reachable from 1
10 is not reachable from 1
11 is not reachable from 1

Now having a look at the Dijkstra's Algorithm using simple Queue to implement the MinPriorityQueue, lets see below the better performance version of the algorithm where we will use MinHeap for the implementation of MinPriorityQueue. Note that we should implement our own MinHeap because PriorityQueue from java.util package does not take care of updating the priority of the items already added in the queue, in case there is some changes in the internal parameters of the items which are already added in the priority queue.

public class DikjstraAlgorithm {
    public static void main(String[] args) {

        Graph graph = new Graph(9);
        for (int i = 0; i < 9; i++) {
            graph.addVertex(i);
        }
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 7, 8);
        graph.addEdge(1, 0, 4);
        graph.addEdge(1, 7, 11);
        graph.addEdge(1, 2, 8);
        graph.addEdge(2, 1, 8);
        graph.addEdge(2, 3, 7);
        graph.addEdge(2, 8, 2);
        graph.addEdge(2, 5, 4);
        graph.addEdge(3, 2, 7);
        graph.addEdge(3, 4, 9);
        graph.addEdge(3, 5, 14);
        graph.addEdge(4, 3, 9);
        graph.addEdge(4, 5, 10);
        graph.addEdge(5, 2, 4);
        graph.addEdge(5, 3, 14);
        graph.addEdge(5, 4, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(6, 5, 2);
        graph.addEdge(6, 7, 1);
        graph.addEdge(6, 8, 6);
        graph.addEdge(7, 0, 8);
        graph.addEdge(7, 1, 11);
        graph.addEdge(7, 6, 1);
        graph.addEdge(7, 8, 7);
        graph.addEdge(8, 2, 2);
        graph.addEdge(8, 6, 6);
        graph.addEdge(8, 7, 7);
        graph.findShortestPaths(0);
    }

    public static class Graph {
        Vertex[] vertices;
        int maxSize;
        int size;

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

        public void addVertex(int name) {
            vertices[size++] = new Vertex(name);
        }

        public void addEdge(int sourceName, int destinationName, int weight) {
            int srcIndex = sourceName;
            int destiIndex = destinationName;
            vertices[srcIndex].adj = new Neighbour(destiIndex, weight, vertices[srcIndex].adj);
            vertices[destiIndex].indegree++;
        }
        
        public void findShortestPaths(int sourceName){
            applyDikjstraAlgorith(vertices[sourceName]);
            for(int i = 0; i < maxSize; i++){
                System.out.println("Distance of "+vertices[i].name+" from Source: "+ vertices[i].cost);
            }
        }
        
        public class Vertex {
            int cost;
            int name;
            Neighbour adj;
            int indegree;
            State state;

            public Vertex(int name) {
                this.name = name;
                cost = Integer.MAX_VALUE;
                state = State.NEW;
            }

            public int compareTo(Vertex v) {
                if (this.cost == v.cost) {
                    return 0;
                }
                if (this.cost < v.cost) {
                    return -1;
                }
                return 1;
            }
        }

        public enum State {
            NEW, IN_Q, VISITED
        }

        public class Neighbour {
            int index;
            Neighbour next;
            int weight;

            Neighbour(int index, int weight, Neighbour next) {
                this.index = index;
                this.next = next;
                this.weight = weight;
            }
        }

        public void applyDikjstraAlgorith(Vertex src) {
            Heap heap = new Heap(maxSize);
            heap.add(src);
            src.state = State.IN_Q;
            src.cost = 0;
            while (!heap.isEmpty()) {
                Vertex u = heap.remove();
                u.state = State.VISITED;
                Neighbour temp = u.adj;
                while (temp != null) {
                    if (vertices[temp.index].state == State.NEW) {
                        heap.add(vertices[temp.index]);
                        vertices[temp.index].state = State.IN_Q;
                    }
                    if (vertices[temp.index].cost > u.cost + temp.weight) {
                        vertices[temp.index].cost = u.cost + temp.weight;
                        heap.heapifyUP(vertices[temp.index]);
                    }
                    temp = temp.next;
                }
            }
        }

        public static class Heap {
            private Vertex[] heap;
            private int maxSize;
            private int size;

            public Heap(int maxSize) {
                this.maxSize = maxSize;
                heap = new Vertex[maxSize];
            }

            public void add(Vertex u) {
                heap[size++] = u;
                heapifyUP(size - 1);
            }

            public void heapifyUP(Vertex u) {
                for (int i = 0; i < maxSize; i++) {
                    if (u == heap[i]) {
                        heapifyUP(i);
                        break;
                    }
                }
            }

            public void heapifyUP(int position) {
                int currentIndex = position;
                Vertex currentItem = heap[currentIndex];
                int parentIndex = (currentIndex - 1) / 2;
                Vertex parentItem = heap[parentIndex];
                while (currentItem.compareTo(parentItem) == -1) {
                    swap(currentIndex, parentIndex);
                    currentIndex = parentIndex;
                    if (currentIndex == 0) {
                        break;
                    }
                    currentItem = heap[currentIndex];
                    parentIndex = (currentIndex - 1) / 2;
                    parentItem = heap[parentIndex];
                }
            }

            public Vertex remove() {
                Vertex v = heap[0];
                swap(0, size - 1);
                heap[size - 1] = null;
                size--;
                heapifyDown(0);
                return v;
            }

            public void heapifyDown(int postion) {
                if (size == 1) {
                    return;
                }

                int currentIndex = postion;
                Vertex currentItem = heap[currentIndex];
                int leftChildIndex = 2 * currentIndex + 1;
                int rightChildIndex = 2 * currentIndex + 2;
                int childIndex;
                if (heap[leftChildIndex] == null) {
                    return;
                }
                if (heap[rightChildIndex] == null) {
                    childIndex = leftChildIndex;
                } else if (heap[rightChildIndex].compareTo(heap[leftChildIndex]) == -1) {
                    childIndex = rightChildIndex;
                } else {
                    childIndex = leftChildIndex;
                }
                Vertex childItem = heap[childIndex];
                while (currentItem.compareTo(childItem) == 1) {
                    swap(currentIndex, childIndex);
                    currentIndex = childIndex;
                    currentItem = heap[currentIndex];
                    leftChildIndex = 2 * currentIndex + 1;
                    rightChildIndex = 2 * currentIndex + 2;
                    if (heap[leftChildIndex] == null) {
                        return;
                    }
                    if (heap[rightChildIndex] == null) {
                        childIndex = leftChildIndex;
                    } else if (heap[rightChildIndex].compareTo(heap[leftChildIndex]) == -1) {
                        childIndex = rightChildIndex;
                    } else {
                        childIndex = leftChildIndex;
                    }
                }
            }

            public void swap(int index1, int index2) {
                Vertex temp = heap[index1];
                heap[index1] = heap[index2];
                heap[index2] = temp;
            }

            public boolean isEmpty() {

                return size == 0;
            }
        }
    }
}

Output :
Distance of 0 from Source: 0
Distance of 1 from Source: 4
Distance of 2 from Source: 12
Distance of 3 from Source: 19
Distance of 4 from Source: 21
Distance of 5 from Source: 11
Distance of 6 from Source: 9
Distance of 7 from Source: 8
Distance of 8 from Source: 14