Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Stock Span

Medium · Stack & Queue · Asked at Amazon, Microsoft, Samsung

The span of day i is the number of consecutive days ending at day i (including it) whose price is ≤ today's price. Print the span of every day.

Input

First line: n. Second line: n prices.

Output

n spans, space-separated.

Constraints

Example 1

Input

7
100 80 60 70 60 75 85

Output

1 1 1 2 1 4 6

Example 2

Input

3
10 20 30

Output

1 2 3

Hints

  1. The span of day i reaches back to the previous day with a strictly greater price.
  2. Keep a stack of indices with decreasing prices. Pop while price[top] ≤ price[i]; span = i − (new top), or i + 1 if the stack is empty.

Approach

This is "previous greater element". Days with price ≤ today's can never stop a future span earlier than today does, so pop them. The index left on top is the previous strictly greater day, and the span is the distance to it. Push i afterwards. Each index is pushed and popped once.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> p(n);
    for (auto &x : p) cin >> x;
    vector<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && p[st.back()] <= p[i]) st.pop_back();
        int span = st.empty() ? i + 1 : i - st.back();
        cout << span << (i + 1 < n ? " " : "\n");
        st.push_back(i);
    }
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, p = data[0], data[1 : data[0] + 1]
stack, spans = [], []
for i in range(n):
    while stack and p[stack[-1]] <= p[i]:
        stack.pop()
    spans.append(i - stack[-1] if stack else i + 1)
    stack.append(i)
print(*spans)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] p = new long[n];
        for (int i = 0; i < n; i++) p[i] = sc.nextLong();
        int[] st = new int[n];
        int top = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            while (top > 0 && p[st[top - 1]] <= p[i]) top--;
            int span = top == 0 ? i + 1 : i - st[top - 1];
            sb.append(i > 0 ? " " : "").append(span);
            st[top++] = i;
        }
        System.out.println(sb);
    }
}

Solve Stock Span online · All practice problems