CareerCup

One solution can be we get the span of ith day by checking if any j<i exists such that a[j]<a[i].
If so, in that case span[i]=span[j]+1 else it will be 0.

void getspan(int a[],int n)
{
     int span[100];
     int i=0,j;
     span[0]=0;
     for(i=1;i<n;i++)
     {
        j=i-1;      
        while(j>=0 && a[j]>=a[i])
           j--;
        if(j==-1)
           span[i]=0;
        else
           span[i]=span[j]+1;
     }
     for(i=0;i<n;i++)
        printf("%d\t",span[i]);
     printf("\n");
}

This is basically the computation of smaller element count on the right. We can do it more efficiently using balanced BST such as AVL tree. We will consider each number in an array as a BST node and insert them in a AVL tree one by one from right to left. During each insert we will keep updating the size of left subtree at the node being inserted. This will give us our desired smaller element count. We also need to handle balancing the tree while insert.

A balance tree got imbalanced on an insert when the insert on a subtree rooted at a node x makes difference between left subtree and right subtree height more than 1. We will have to consider 4 cases:

1) Insert-in-left-of-left-subtree of x: we can balance by rotating x right
2) Insert-in-right-of-right-subtree of x: we can balance by rotating x left
3) Insert-in-right-of-left-subtree of x: we need two rotations: balance left of x by rotating left. And then a right rotation of x.
4) Insert-in-left-of-right-subtree of x: we need two rotations: balance right of x by rotating right. And then a left rotation of x.

Time complexity will be O(nlgn) and space is O(n).

This can be solved simply by maintaining a Min and max stock price.

Globals
int Size = 100; //Some large value
int StockStack[size];
int Min = 32767; //Some large sentinel value
int Max = -1;
int spanOfStack( int StockPriceForTheDay)
{
int count = 0;

if(StockPriceForTheDay <= Min)
{
Min = StockPriceForTheDay;
StockStack.push(Min);
return -1;
}
else if(StockPriceOfTheDay >= Max)
{
Max = StockPriceOfTheDay;
StockStack.push(Max);
return StockStack.NumberOfElements();
}
else
{
StockStack.push(StockPriceForTheDay);
for(int i=0;i<StockStack.NumberOfElements();i++)
{
if(StockStack[i]<StockPriceForTheDay)
count++;
}

return count;
}

}

insert the values to the Linked List in sorted order.
Increment the span to index while inserting.

could sort them by the stock prices preserving the original index, the number of the span will be the new index minus the number of pairs which the previous element's original index is higher than the current one.e.g:
input:{2,4,6,9,5,7,1};
internal sorted result {1,2,4,5,6,7,9} with index{6,0,1,4,2,5,3}
output:{-1,1,2,3,2,3,-1}
expected time complexity o(nlogn) + o(n)
space complexity o(n)

#include <algorithm>
#include <utility>
#include <iostream>

vector<int>& calculateSpan(const vector<int>& stock_prices) {
  // result of the span calculation
  vector<int> *span = new vector<int>(stock_prices.size(), -1);
  if (span->size() > 1) {
    // sorted the stock prices, preserving the original index
    vector<pair<int, int> > sorted_prices;
    for (int i = 0; i < stock_prices.size(); ++i) {
      sorted_prices.push_back(make_pair(stock_prices[i], i));
    }
    sort(sorted_prices.begin(), sorted_prices.end());
    
    // whenever we find a value with its index lower than the previous one, we
    // increase the count
    int higher_index_count = 0;
    for (int i = 1; i < sorted_prices.size(); ++i) {
      if (sorted_prices[i].second < sorted_prices[i - 1].second) {
        ++higher_index_count;
      }
      // the span is calcuated by the index minus the higher index count
      const int number_of_span = i - higher_index_count;
      (*span)[sorted_prices[i].second] = number_of_span == 0? -1: number_of_span;
    }
  }
  return *span;
}

The solution can be found in O(n) using a stack and is present in many algorithm text books.

int[] span(int[] stockValues) {
		int[] out = new int[stockValues.length];
		SortedMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		
		for (int i = 0; i<stockValues.length;i++) {
			int stockValue = stockValues[i];
			int frequency = 0;
			if (map.containsKey(stockValue))
				frequency = map.get(stockValue);
			map.put(stockValue, ++frequency);
			
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				if (entry.getKey() < stockValue) out[i] = out[i]+entry.getValue();
				else break;
			}
		}
		
		return out;
	}

For each entry have another count variable which keeps track of how many entries are less than that in the list. Have a bst constructed for each entry. That way for finding number of entries less than n we can go to the inorder predecessor of n, get its count and do a +1.

this can be done using avl tree,

every time we insert a stock value we check how many values are less than that of the present stock value being inserted.

I was trying to find solution faster than O(N*N), but I could not.
Here is a solution in python

def find_max_span(data):
  output = []
  for i in range(0, len(data)):
    current = data[i]
    count = -1
    for j in range(0, i):
      if (data[j] < current): 
        if (count==-1):
          count =1
        else:
          count+=1
    output.append(count)
  return output

This can be solved in nlogn time using a same approach as calculating number of inversion pairs. Just change the definition of inversion to be A[i] < A[j].

not clear question please explain more

This was just having fun and answering quickly. Linked list sure is a nice soln though.

public class MaxStockPriceSpan {

	/**
	 Max span is number of days before this day that the price was lower than todays.
	 I/P is an array of prices ordered by days.
	 */
	public static void main(String[] args) {
		PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
		int[] in = {2, 4 ,6 ,9, 5, 1};
		List<Integer> out = new ArrayList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();
		for (int n : in) {
			while (!minHeap.isEmpty() && minHeap.peek() < n) {
				int temp = minHeap.poll();
				stack.push(temp);
			}
			minHeap.offer(n);
			if (stack.isEmpty()) {
				out.add(-1);
			}
			else {
				out.add(stack.size());
				while (!stack.isEmpty()) {
					int temp = stack.pop();
					minHeap.offer(temp);
				}
			}
		}
		System.out.println("The min span array for " + Arrays.toString(in) + " is " + Arrays.toString(out.toArray()) + ".");
	}
}

I also think the balanced search tree idea deserves a look. Seems like it would make sense since what we're looking for is a data struct that's always sorted and which gives you the index of a member on request -- like the linked list solution does "manually."

void getspan(int a[],int n)
{
int span[50];
int i,j;
span[0]=0;
for(i=1;i<n;i++)
{

for(j=0;j<i;j++){
if(a[i]>a[j])
span[i]=span[j]+1;
}
}
for(i=0;i<n;i++){
printf("%d\t",span[i]);
printf("\n");
}
}

Just came up with a simple idea of maintaining a sorted list.
So my algorithm would look like this.

(1) Initialize Sorted List
(2) Using binary search check the lower bound of the key to be inserted in the sorted list, if it is at x then put x in the span[i], (exception: if x == 0, then span[i] = -1)

So the sorted list would keep on growing, but the advantage is that it is simpler than maintaining a tree or a balanced BST. Moreover, it is always sorted and we can calculate the lower bound of an element to be inserted (also called lower bound insertion point) in logarithmic time.

If we maintain a dynamic array-like structure for the sorted list then insertion would be constant time.

Overall runtime should be under **nlogn** which is fairly satisfactory for this problem.
Please put your comments below.

The solution could be achieved in nlogn complexity

Deatils:
construct BST and keep adding +1 when moving to right tree and dont increment anything when moving in left part of the tee.

for root-> -1(output)
for node having 0 as incremnet count(output -1)
and >0 output whatever is the count.