Problem: Given the prices of a stock for N consecutive days, the task is to find the span for every day. The span of a stock for day i is defined as the number of consecutive days before it with price less than or equal to the price on the i-th day, including the i-th day.
Example:
Input: prices[] = {13, 15, 12, 14, 16, 8, 6, 4, 10, 30} Output: 1, 2, 1, 2, 5, 1, 1, 1, 4, 10
Explanation:
- The span for day 1 is always 1 as it is the first day.
- The span for day 2 is 2 because the price of the day just before it is lesser.
- The span for day 3 is 1 because the price of the day before is greater.
- The span for day 4 is 2 because there is just 1 consecutive day before it with a lesser price. Please note here that the price of day 1 is lesser than the price of day 4, but it is not included in the span.
- The span of day 5 is 5 because there are 4 consecutive days immediately before it.
- So including the 5th day itself, the span is 5.
- So on for the rest of the days.
Solution: If we observe carefully, we can see that the span for a day is given by:
The difference between the index of the current element and the index of the closest greater element on the left, if there exists a greater element on the left. Otherwise, if there doesn't exist any greater element on the left, the span is equal to "index of the current element + 1".
So, the task is to find the position of the closest element on the left of every element that is greater than or equal to it. This can be easily done using a stack. The idea is:
- We use a stack to keep track of the previous greater elements.
- We push the index of the first element onto the stack.
- We then start traversing the array from the second element.
- For every new element, we compare it with the element at the top of the stack (which is the closest previous greater element).
- If the current element is greater than or equal to the element at the top of the stack, we pop elements from the stack until we find an element that is greater than the current element or until the stack becomes empty.
- The span for the current element is then the difference between the current index and the index of the element at the top of the stack, or the current index plus 1 if the stack is empty.
Complexity Analysis:
The time complexity of the above solution is O(N) in the worst case, as each element is pushed and popped from the stack only once. The auxiliary space used will be O(N) in the worst case, as the stack can have at most N elements.
Here's the Java implementation of the algorithm:
import java.util.*;
class StockSpan { static void printSpan(int[] arr) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(0); int[] span = new int[arr.length]; span[0] = 1; for (int i = 1; i < arr.length; i++) { while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) { stack.pop(); } span[i] = stack.isEmpty() ? i + 1 : i - stack.peek(); stack.push(i);
} for (int i = 0; i < span.length; i++) { System.out.print(span[i] + " "); } } }
// Example usage public static void main(String[] args) { int[] prices = {100, 80, 60, 70, 60, 75, 85}; printSpan(prices); // Output: 1 1 1 2 1 4 6 }
In the StockSpan class above, the printSpan method takes an array of stock prices and calculates the span of each stock. The span of a stock is the maximum number of consecutive days in which the stock price was less than or equal to its price on the current day.
For example, if the stock prices on Monday, Tuesday, Wednesday, and Thursday were 100, 80, 60, and 70, respectively, then the span of the stock on Thursday would be 2, because the stock price was less than or equal to its price on Wednesday and Tuesday.
Complete the StockSpan class by implementing the printSpan method. Make sure that the output of the printSpan method matches the expected output for the example usage provided in the main method.