The Stock Span Problem Solution in Java

The Stock Span Problem

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.

The span of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

For example, 
if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}

Solution:

Traverse the input price array. For every element being visited, traverse elements on left of it and increment the span value of it while elements on the left side are smaller.

Code:

import java.util.Stack;

/**
 * @author Abhinaw.Tripathi
 *
 */
public class TheStockSpanProblem {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int price[] = {10, 4, 5, 90, 120, 80};
stockSpanProblem(price);

}
@SuppressWarnings({ "unchecked", "rawtypes" })
private static int[] stockSpanProblem(int[] arr)
{
Stack<Integer> s = new Stack();
Stack<Integer> s2 = new Stack();
int[] returned_arr = new int[arr.length];
int temp;
int count;
for(int i = 0;i < arr.length; i++)
{
 count = 1;
//to push elements inside it until larger element comes
if (s.empty())

s.push(arr[i]);

if (s.peek() > arr[i])
{
 s.push(arr[i]);
}
else
{
 while (!s.empty() && s.peek() < arr[i])
 {
temp = s.pop();
s2.push(temp);
count ++;
 }
s.push(arr[i]);//push this element
while (!s2.empty())
{
 s.push(s2.pop());
}//so s2 empty at last
}
returned_arr[i] = count;
System.out.println(returned_arr[i]);
  }
   return returned_arr;
}
}

Output:

1 1 2 4 5 1

But this solution is inefficient.Can be a better solution than this.

Time Complexity: O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of array is added and removed from stack at most once. So there are total 2n operations at most. Assuming that a stack operation takes O(1) time, we can say that the time complexity is O(n).

Auxiliary Space: O(n) in worst case when all elements are sorted in decreasing order.

LinkedHashSet Class and Stack Class example java

LinkedHashSet Class

This is a subclass of HashSet class and does not contain any additional members on its own.It is a generic class that has declaration:

class LinkedHashSet<T>

Here.T represents generic type parameter.

LinkedHashSet internally uses a linked list to store the elements.

Stack Class

A stack represents a group of elements stored in LIFO.This means that the element which is stored as a last element into the stack will be the first element to be removed from the stack.

There are three operation can be performed on stack:

1. Push() ----Inserting an element in stack.
2. Pop()------Deleting an element from stack.
3. Peek()-----Searching an element from stack.

Stack Class Methods

• boolean empty();
• element peek();
• element pop();
• element push(element obj);
• int search(Object obj);

What is Auto Boxing?

Ans: Converting a primitive data type into an object form automatically is called Auto-Boxing.Auto Boxing is done in generic types.

Program:

/**

 * 

 */

package com.collectionpack;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Stack;

/**

 * @author Abhinaw.Tripathi

 *

 */

public class StackApp

{

/**

* @param args

* @throws IOException 

* @throws NumberFormatException 

*/

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

{

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

int choice = 0;

int position,element;

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

while(choice < 4)

{

System.out.println("Stack Operation");

System.out.println("1 Push an element");

System.out.println("2 Pop an element");

System.out.println("3 Search an element?");

System.out.println("4 Exist");

choice=Integer.parseInt(br.readLine());

switch (choice) 

{

case 1:

System.out.println("Enter element: ");

   element=Integer.parseInt(br.readLine());

   st.push(element);

break;

case 2:

Integer obj=st.pop();

System.out.println("Popped= "+ obj);

break;

case 3:

System.out.println("Which element?");

element=Integer.parseInt(br.readLine());

position=st.search(element);

if(position == -1)

System.out.println("Element not found");

else

System.out.println("Position:" +position);

break;

default:

return;

}

System.out.println("stack contents: "+st);

}

}

}

Output:

Stack Operation

1 Push an element

2 Pop an element

3 Search an element?

4 Exist

1

Enter element: 

52

stack contents: [52]

Stack Operation

1 Push an element

2 Pop an element

3 Search an element?

4 Exist

Stack Implemented by a Linked List in core-java example

Stack implementation by a Linked List:


/**
 * @author Abhinaw.Tripathi
 *
 */
class Link
{

 public long dData;
 public Link next;

 public Link(long dd)
 {
dData=dd;
 }

 public void displayLink()
 {
 System.out.println(dData+ " ");
 }

}

class LinkList
{
private Link first;

public LinkList()
{
first=null;
}

public boolean isEmpty()
{
return (first==null);
}

public void insertFirst(long dd)
{
Link newLink=new Link(dd);
newLink.next=first;
first=newLink;
}

public Link deleteFirst()
{
Link temp=first;
first=first.next;
return temp;
}

public void displayList()
{
Link current=first;
while(current!=null)
{
current.displayLink();
current=current.next;
}
System.out.println(" ");
}

}

class LinkStack
{
 private LinkList theList;

 public LinkStack()
 {
theList=new LinkList();
 }

 public void push(long j)
 {
theList.insertFirst(j);
 }

 public Link pop()
 {
return (theList.deleteFirst());
 }

 public boolean isEmpty()
 {
return (theList.isEmpty());
 }

 public void displayStack()
 {
System.out.println("Stack  (top---->bottom:)");
theList.displayList();
 }

}



public class LinkStackApp
{
public static void main(String[] args)
{
LinkStack theStack=new LinkStack();
theStack.push(20);
theStack.push(40);

theStack.displayStack();

theStack.push(60);
theStack.push(80);
        theStack.displayStack();
     
        theStack.pop();
        theStack.pop();
     
        theStack.displayStack();
}


}

The desire output will be 

Stack  (top---->bottom:)

40 

20 

Stack  (top---->bottom:)

80 

60 

40 

20 

Stack  (top---->bottom:)

40 

20