Getting everything ready for you…

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

0s

Practice › Stack & Queue

Daily Temperatures

Medium · Stack & Queue · Asked at Amazon, Google, Meta, Microsoft

For each day, print how many days you have to wait for a warmer temperature. If no warmer day comes, print 0 for that day.

Input

First line: n. Second line: n space-separated integers.

Output

n space-separated waits.

Constraints

A stack of indices whose answer is still unknown, with decreasing temperatures. A warmer day pops (and answers) all colder days on top.

Example 1

Input

8
73 74 75 71 69 72 76 73

Output

1 1 4 2 1 1 0 0

Example 2

Input

4
30 40 50 60

Output

1 1 1 0

Hints

  1. Keep a stack of indices of days still waiting for a warmer day.
  2. When a warmer day i arrives, pop every colder day j from the stack and set answer[j] = i − j.

Approach

The stack holds indices with non-increasing temperatures. For day i, while the top day is colder than t[i], it has found its answer: ans[top] = i − top; pop it. Then push i. Days left on the stack at the end never get warmer, so their answer stays 0.

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

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<int> t(n), ans(n, 0), st;
    for (auto &x : t) cin >> x;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && t[st.back()] < t[i]) {
            ans[st.back()] = i - st.back();
            st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
t = data[1:]
ans, st = [0] * len(t), []
for i, x in enumerate(t):
    while st and t[st[-1]] < x:
        j = st.pop()
        ans[j] = i - j
    st.append(i)
print(*ans)

Java solution

import java.util.*;

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

Solve Daily Temperatures online · All practice problems