Run your code 2 more times to open the solutions. The idea sticks better after an attempt. Daily Temperatures in Python 2 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
For each day i, walk forward with j until a reading is strictly greater, store j - i and break. The result list starts as all zeros, so a day that never finds a warmer reading keeps its 0 without any extra code.
def daily_temperatures(temperatures: list [int ]) -> list [int ]:
n = len (temperatures)
answer = [0 ] * n
for i in range (n):
for j in range (i + 1 , n):
if temperatures[j] > temperatures[i]:
answer[i] = j - i
break
return answer
A plain list works as the stack: append pushes and pop takes the top, both in constant time. It holds the indices still waiting for a warmer day. Each new reading pops every waiting index it beats and writes the distance into answer, then waits itself. Every index goes on and comes off at most once, so the whole pass is linear.
def daily_temperatures(temperatures: list [int ]) -> list [int ]:
answer = [0 ] * len (temperatures)
waiting: list [int ] = [] # indices with no warmer day yet, readings never rising toward the top
for i, t in enumerate (temperatures):
while waiting and temperatures[waiting[-1 ]] < t:
j = waiting.pop()
answer[j] = i - j
waiting.append(i)
return answer
Daily Temperatures in JavaScript 2 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
new Array(n).fill(0) sets every wait to 0 up front. For each day i, the inner loop walks forward until it meets a strictly greater reading, stores the distance and breaks out of the inner loop only. Days that never find one keep their 0.
function dailyTemperatures (temperatures) {
const n = temperatures.length;
const answer = new Array (n).fill (0 );
for (let i = 0 ; i < n; i++) {
for (let j = i + 1 ; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break ;
}
}
}
return answer;
}
A plain array is the stack: push adds to the end, pop removes from it, and waiting.at(-1) reads the top. It holds the indices still waiting for a warmer day. Each new reading pops every waiting index it beats and records the distance, then pushes its own index. Each index is pushed and popped at most once, so the pass is linear.
function dailyTemperatures (temperatures) {
const answer = new Array (temperatures.length).fill (0 );
const waiting = []; // indices with no warmer day yet
for (let i = 0 ; i < temperatures.length; i++) {
while (waiting.length > 0 && temperatures[waiting.at (-1 )] < temperatures[i]) {
const j = waiting.pop ();
answer[j] = i - j;
}
waiting.push (i);
}
return answer;
}
Daily Temperatures in TypeScript 2 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
For each day i, scan forward with j until a reading is strictly greater and store j - i. The result starts as new Array<number>(n).fill(0), so a day with no warmer reading keeps its 0.
function dailyTemperatures (temperatures: number[]): number[] {
const n = temperatures.length;
const answer = new Array <number>(n).fill (0 );
for (let i = 0 ; i < n; i++) {
for (let j = i + 1 ; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break ;
}
}
}
return answer;
}
A number[] of indices serves as the stack of days still waiting for a warmer one. Each reading pops every waiting index it beats and records the distance, then pushes its own index. Because the loop only pops while the stack is non-empty, pop() never returns undefined there, which the ! tells the compiler.
function dailyTemperatures (temperatures: number[]): number[] {
const answer = new Array <number>(temperatures.length).fill (0 );
const waiting: number[] = []; // indices with no warmer day yet
for (let i = 0 ; i < temperatures.length; i++) {
while (waiting.length > 0 && temperatures[waiting[waiting.length - 1 ]] < temperatures[i]) {
const j = waiting.pop ()!;
answer[j] = i - j;
}
waiting.push (i);
}
return answer;
}
Daily Temperatures in Java 2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
A new int[] in Java is already filled with zeros, which is exactly the answer for a day with no warmer reading. For each day i, the inner loop walks forward until a reading is strictly greater, stores j - i and breaks out of the inner loop.
import java.util.*;
public class Main {
static int [] dailyTemperatures (int [] temperatures) {
int n = temperatures.length;
int [] answer = new int [n];
for (int i = 0 ; i < n; i++) {
for (int j = i + 1 ; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break ;
}
}
}
return answer;
}
}
An ArrayDeque<Integer> holds the indices still waiting for a warmer day; push, peek and pop all work on the head in constant time. Each reading pops every waiting index it beats and records the distance, then pushes its own index. Every index enters and leaves once, so the method is linear.
import java.util.*;
public class Main {
static int [] dailyTemperatures (int [] temperatures) {
int [] answer = new int [temperatures.length];
Deque<Integer> waiting = new ArrayDeque<>(); // indices with no warmer day yet
for (int i = 0 ; i < temperatures.length; i++) {
while (!waiting.isEmpty () && temperatures[waiting.peek ()] < temperatures[i]) {
int j = waiting.pop ();
answer[j] = i - j;
}
waiting.push (i);
}
return answer;
}
}
Daily Temperatures in Go 2 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
make([]int, n) returns a slice of zeros, which is already the answer for a day with no warmer reading. For each day i, the inner loop walks forward until a reading is strictly greater, stores j - i and breaks, which in Go leaves only the innermost loop.
package main
func dailyTemperatures (temperatures []int ) []int {
n := len (temperatures)
answer := make ([]int , n)
for i := range temperatures {
for j := i + 1 ; j < n; j++ {
if temperatures[j] > temperatures[i] {
answer[i] = j - i
break
}
}
}
return answer
}
Go has no stack type; a slice is the idiom. append pushes, waiting[len(waiting)-1] reads the top and waiting = waiting[:len(waiting)-1] pops without freeing memory. Each reading pops every waiting index it beats and records the distance, then pushes its own index; every index enters and leaves once, so the pass is linear.
package main
func dailyTemperatures (temperatures []int ) []int {
answer := make ([]int , len (temperatures))
waiting := make ([]int , 0 , len (temperatures)) // indices with no warmer day yet
for i, t := range temperatures {
for len (waiting) > 0 && temperatures[waiting[len (waiting)-1 ]] < t {
j := waiting[len (waiting)-1 ]
waiting = waiting[:len (waiting)-1 ]
answer[j] = i - j
}
waiting = append (waiting, i)
}
return answer
}
Daily Temperatures in C# 2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
new int[n] starts as all zeros, the answer for a day with no warmer reading. For each day i, the inner loop walks forward until a reading is strictly greater, stores j - i and breaks out of the inner loop.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int [] DailyTemperatures (int [] temperatures)
{
int n = temperatures.Length;
var answer = new int [n];
for (int i = 0 ; i < n; i++)
{
for (int j = i + 1 ; j < n; j++)
{
if (temperatures[j] > temperatures[i])
{
answer[i] = j - i;
break ;
}
}
}
return answer;
}
}
A Stack<int> holds the indices still waiting for a warmer day; Push, Peek and Pop are constant time and, being generic, never box the int. Each reading pops every waiting index it beats and records the distance, then pushes its own index. Every index enters and leaves once, so the pass is linear.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int [] DailyTemperatures (int [] temperatures)
{
var answer = new int [temperatures.Length];
var waiting = new Stack<int >(); // indices with no warmer day yet
for (int i = 0 ; i < temperatures.Length; i++)
{
while (waiting.Count > 0 && temperatures[waiting.Peek ()] < temperatures[i])
{
int j = waiting.Pop ();
answer[j] = i - j;
}
waiting.Push (i);
}
return answer;
}
}
Daily Temperatures in C++ 2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
vector<int> answer(n, 0) starts every wait at 0. For each day i, the inner loop walks forward until a reading is strictly greater, stores j - i and breaks out of the inner loop. Taking temperatures by reference avoids copying the vector.
#include <algorithm>
#include <string >
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public :
vector<int > dailyTemperatures (vector<int >& temperatures) {
int n = (int )temperatures.size ();
vector<int > answer (n, 0 );
for (int i = 0 ; i < n; i++) {
for (int j = i + 1 ; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break ;
}
}
}
return answer;
}
};
A vector<int> is the stack of indices still waiting for a warmer day: push_back, back and pop_back are all constant time, and reserve sizes it once. Each reading pops every waiting index it beats and records the distance, then pushes its own index. Every index enters and leaves once, so the pass is linear.
#include <algorithm>
#include <string >
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public :
vector<int > dailyTemperatures (vector<int >& temperatures) {
int n = (int )temperatures.size ();
vector<int > answer (n, 0 );
vector<int > waiting; // indices with no warmer day yet
waiting.reserve (n);
for (int i = 0 ; i < n; i++) {
while (!waiting.empty () && temperatures[waiting.back ()] < temperatures[i]) {
answer[waiting.back ()] = i - waiting.back ();
waiting.pop_back ();
}
waiting.push_back (i);
}
return answer;
}
};
Daily Temperatures in C 2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
Allocate the result with calloc, so every day starts at 0, the answer for a day with no warmer reading. For each day i, walk forward until a strictly greater reading, store j - i and break. *returnSize is always temperaturesSize.
#include <stdbool.h>
#include <stdlib.h>
#include <string .h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int * dailyTemperatures (int * temperatures, int temperaturesSize, int * returnSize) {
int * answer = calloc (temperaturesSize > 0 ? temperaturesSize : 1 , sizeof *answer);
*returnSize = temperaturesSize;
for (int i = 0 ; i < temperaturesSize; i++) {
for (int j = i + 1 ; j < temperaturesSize; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break ;
}
}
}
return answer;
}
The stack is a second int array of the same length plus a top counter: stack[top++] = i pushes and stack[--top] pops. It holds the indices still waiting for a warmer day. Each reading pops every index it beats and writes the distance, then pushes itself; free the stack before returning the answer.
#include <stdbool.h>
#include <stdlib.h>
#include <string .h>
/**
* Note: the returned array must be malloc'ed; the caller frees it.
*/
int * dailyTemperatures (int * temperatures, int temperaturesSize, int * returnSize) {
int n = temperaturesSize;
int * answer = calloc (n > 0 ? n : 1 , sizeof *answer);
int * stack = malloc ((n > 0 ? n : 1 ) * sizeof *stack); /* indices with no warmer day yet */
int top = 0 ;
for (int i = 0 ; i < n; i++) {
while (top > 0 && temperatures[stack[top - 1 ]] < temperatures[i]) {
int j = stack[--top];
answer[j] = i - j;
}
stack[top++] = i;
}
free (stack);
*returnSize = n;
return answer;
}
Daily Temperatures in Kotlin 2 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
IntArray(n) starts filled with zeros, the answer for a day with no warmer reading. For each day i, the inner loop walks forward until a strictly greater reading, stores j - i and breaks.
class Solution {
fun dailyTemperatures (temperatures: IntArray): IntArray {
val n = temperatures.size
val answer = IntArray (n)
for (i in 0 until n) {
for (j in i + 1 until n) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i
break
}
}
}
return answer
}
}
Kotlin's own ArrayDeque<Int> serves as the stack: addLast pushes, last() peeks and removeLast() pops. It holds the indices still waiting for a warmer day; each reading pops every index it beats, records the distance, then waits itself.
class Solution {
fun dailyTemperatures (temperatures: IntArray): IntArray {
val answer = IntArray (temperatures.size)
val waiting = ArrayDeque<Int>() // indices with no warmer day yet
for ((i, t) in temperatures.withIndex ()) {
while (waiting.isNotEmpty () && temperatures[waiting.last ()] < t) {
val j = waiting.removeLast ()
answer[j] = i - j
}
waiting.addLast (i)
}
return answer
}
}
Daily Temperatures in Rust 2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
Start from vec![0; n], the answer for a day with no warmer reading. For each day i, walk forward with j until a strictly greater reading, store the distance as (j - i) as i32 and break.
impl Solution {
pub fn daily_temperatures (temperatures: Vec<i32>) -> Vec<i32> {
let n = temperatures.len ();
let mut answer = vec![0 ; n];
for i in 0.. n {
for j in i + 1.. n {
if temperatures[j] > temperatures[i] {
answer[i] = (j - i) as i32;
break ;
}
}
}
answer
}
}
A Vec<usize> is the stack: push adds an index and last() peeks without popping. It holds the days still waiting for a warmer reading; each new reading pops every index it beats and writes the distance, then pushes its own index.
impl Solution {
pub fn daily_temperatures (temperatures: Vec<i32>) -> Vec<i32> {
let mut answer = vec![0 ; temperatures.len ()];
let mut waiting: Vec<usize> = Vec::with_capacity (temperatures.len ());
for (i, &t) in temperatures.iter ().enumerate () {
while let Some (&j) = waiting.last () {
if temperatures[j] >= t {
break ;
}
waiting.pop ();
answer[j] = (i - j) as i32;
}
waiting.push (i);
}
answer
}
}
Daily Temperatures in Swift 2 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
Start from [Int](repeating: 0, count: n), the answer for a day with no warmer reading. For each day i, walk forward until a strictly greater reading, store j - i and break. On the last day i + 1..<n is an empty range, so the inner loop simply does not run.
class Solution {
func dailyTemperatures (_ temperatures: [Int]) -> [Int] {
let n = temperatures.count
var answer = [Int](repeating: 0 , count: n)
for i in 0.. <n {
for j in i + 1.. <n {
if temperatures[j] > temperatures[i] {
answer[i] = j - i
break
}
}
}
return answer
}
}
A plain [Int] works as the stack: append pushes, last peeks and removeLast() pops, all in constant time. It holds the indices still waiting for a warmer day; each reading pops every index it beats and writes the distance, then waits itself.
class Solution {
func dailyTemperatures (_ temperatures: [Int]) -> [Int] {
var answer = [Int](repeating: 0 , count: temperatures.count)
var waiting: [Int] = [] // indices with no warmer day yet
waiting.reserveCapacity (temperatures.count)
for (i, t) in temperatures.enumerated () {
while let j = waiting.last, temperatures[j] < t {
waiting.removeLast ()
answer[j] = i - j
}
waiting.append (i)
}
return answer
}
}
Daily Temperatures in PHP 2 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
array_fill(0, $n, 0) starts every day at 0, the answer for a day with no warmer reading. For each day $i, walk forward until a strictly greater reading, store $j - $i and break out of the inner loop.
<?php
class Solution {
/**
* @param int[] $temperatures
* @return int[]
*/
function dailyTemperatures (array $temperatures): array {
$n = count ($temperatures);
$answer = array_fill (0 , $n, 0 );
for ($i = 0 ; $i < $n; $i++) {
$t = $temperatures[$i];
for ($j = $i + 1 ; $j < $n; $j++) {
if ($temperatures[$j] > $t) {
$answer[$i] = $j - $i;
break ;
}
}
}
return $answer;
}
}
A plain array is the stack: $waiting[] = $i pushes and array_pop takes the top. A separate $top counter makes the peek a direct index. Each reading pops every waiting index it beats and writes the distance, then waits itself.
<?php
class Solution {
/**
* @param int[] $temperatures
* @return int[]
*/
function dailyTemperatures (array $temperatures): array {
$n = count ($temperatures);
$answer = array_fill (0 , $n, 0 );
$waiting = []; // indices with no warmer day yet
$top = 0 ;
foreach ($temperatures as $i => $t) {
while ($top > 0 && $temperatures[$waiting[$top - 1 ]] < $t) {
$j = array_pop ($waiting);
$top--;
$answer[$j] = $i - $j;
}
$waiting[] = $i;
$top++;
}
return $answer;
}
}
Daily Temperatures in Ruby 2 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
Array.new(n, 0) starts every day at 0, the answer for a day with no warmer reading. For each day i, a while loop walks forward until a strictly greater reading and stores j - i; plain while loops keep the 2 million comparisons of the largest case quick in an interpreter.
# @param {Integer[]} temperatures
# @return {Integer[]}
def daily_temperatures (temperatures)
n = temperatures.length
answer = Array.new (n, 0 )
i = 0
while i < n
t = temperatures[i]
j = i + 1
while j < n
if temperatures[j] > t
answer[i] = j - i
break
end
j += 1
end
i += 1
end
answer
end
An Array is the stack: push adds an index, last peeks and pop takes the top. It holds the indices still waiting for a warmer day; each reading pops every index it beats and writes the distance, then waits itself.
# @param {Integer[]} temperatures
# @return {Integer[]}
def daily_temperatures (temperatures)
answer = Array.new (temperatures.length, 0 )
waiting = [] # indices with no warmer day yet
temperatures.each_with_index do |t, i|
while !waiting.empty? && temperatures[waiting.last] < t
j = waiting.pop
answer[j] = i - j
end
waiting.push (i)
end
answer
end
Daily Temperatures in Dart 2 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
List.filled(n, 0) starts every day at 0, the answer for a day with no warmer reading. For each day i, walk forward until a strictly greater reading, store j - i and break.
class Solution {
List<int > dailyTemperatures (List<int > temperatures) {
final n = temperatures.length;
final answer = List<int >.filled (n, 0 );
for (var i = 0 ; i < n; i++) {
for (var j = i + 1 ; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
answer[i] = j - i;
break ;
}
}
}
return answer;
}
}
A growable List<int> is the stack: add pushes, last peeks and removeLast() pops, all at the end in constant time. It holds the indices still waiting for a warmer day; each reading pops every index it beats and writes the distance.
class Solution {
List<int > dailyTemperatures (List<int > temperatures) {
final answer = List<int >.filled (temperatures.length, 0 );
final waiting = <int >[]; // indices with no warmer day yet
for (var i = 0 ; i < temperatures.length; i++) {
final t = temperatures[i];
while (waiting.isNotEmpty && temperatures[waiting.last] < t) {
final j = waiting.removeLast ();
answer[j] = i - j;
}
waiting.add (i);
}
return answer;
}
}
Daily Temperatures in Scala 2 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
new Array[Int](n) starts every day at 0, the answer for a day with no warmer reading. For each day i, an inner while walks forward until a strictly greater reading and stores j - i; the loop stops itself, so no return or break is needed.
object Solution {
def dailyTemperatures (temperatures: Array[Int]): Array[Int] = {
val n = temperatures.length
val answer = new Array[Int](n)
for (i <- 0 until n) {
var j = i + 1
while (j < n && temperatures (j) <= temperatures (i)) j += 1
if (j < n) answer (i) = j - i
}
answer
}
}
A mutable.ArrayBuffer[Int] is the stack: += pushes, last peeks and remove(size - 1) pops. It holds the indices still waiting for a warmer day; each reading pops, in a while loop, every index it beats and writes the distance.
import scala.collection.mutable
object Solution {
def dailyTemperatures (temperatures: Array[Int]): Array[Int] = {
val answer = new Array[Int](temperatures.length)
val waiting = mutable.ArrayBuffer.empty[Int] // indices with no warmer day yet
for (i <- temperatures.indices) {
val t = temperatures (i)
while (waiting.nonEmpty && temperatures (waiting.last) < t) {
val j = waiting.remove (waiting.length - 1 )
answer (j) = i - j
}
waiting += i
}
answer
}
}
FAQ for Python Why compare with < and not <= when popping the stack? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so [8, 8, 5, 8, 10] would give 1 for the first 8 instead of 4. With <, equal readings stay on the stack together until something warmer arrives.
Should I use collections.deque for the stack? There is no need. A list already pushes and pops at the end in amortised constant time. A deque pays off when you also remove from the front, which this problem never does.
Why store indices on the stack instead of temperatures? The answer is a distance in days, so you need the position of the waiting day. The temperature is always one lookup away as temperatures[waiting[-1]]. Storing (index, temperature) tuples works too and saves that lookup, at the cost of a tuple per day.
Is the stack version really O(n) with a while loop inside a for loop? Yes. Count the work per index instead of per loop: each index is appended once and popped at most once, so the while body runs at most n times across the whole function, not n times per day.
Can I solve it from right to left instead? Yes. Walk backwards and keep a stack of indices whose readings are warmer than everything between them and the current day. Pop while the top is not warmer than today; the top that remains is the answer, or 0 if the stack is empty; then push today. It is the same O(n) idea seen from the other end.
FAQ for JavaScript Why not use shift and unshift for the stack? shift and unshift work on the front of the array and move every other element, so each call is O(n) and the solution turns quadratic. push and pop work on the end in constant time, which is all a stack needs.
Why fill the result with 0 first? new Array(n) alone is full of empty slots, not zeros. Days left on the stack at the end are never written, so without fill(0) they would print as empty items instead of 0. Filling up front gives every day the "no warmer day" answer by default.
Does waiting.at(-1) work everywhere? Array.prototype.at is in every current browser and Node 16.6 or later. On an older runtime write waiting[waiting.length - 1], which reads the same last element.
What happens with readings typed in as strings? Comparison goes wrong. '9' > '10' is true because strings compare character by character, so ['9', '10'] gives [0, 0] instead of [1, 0]. Convert with map(Number) before calling the function.
Why is the while loop inside the for loop still O(n)? Count per index, not per loop: every index is pushed once and popped at most once, so the while body runs at most n times over the whole call.
FAQ for TypeScript Why the ! after waiting.pop()? Array.prototype.pop is typed as returning number | undefined, because an empty array has nothing to pop. The loop condition already checks waiting.length > 0, so the non-null assertion is safe here; without it, strict mode rejects i - j.
Would an Int32Array be faster for the result? It can be a little faster and starts zeroed, but the signature returns number[]. Convert with Array.from(result) at the end if you use one, or keep the plain array, which is fast enough for this size.
Why strictly less than when popping? An equal reading is not warmer. With <=, the second 8 in [8, 8, 5, 8, 10] would pop the first and give it a wait of 1 instead of 4.
Is this the same as next greater element? Yes, with a twist in the output: next greater element returns the warmer value itself, this problem returns the distance to it. The stack loop is identical; only answer[j] = i - j changes to answer[j] = temperatures[i].
Why is a loop inside a loop still linear here? Each index is pushed once and popped at most once, so the inner while runs at most n times over the entire call, not per day.
FAQ for Java Why ArrayDeque instead of java.util.Stack? Stack extends Vector, so every call is synchronized, which costs time for nothing in single-threaded code. The Javadoc itself points to Deque for stack use. ArrayDeque has push, pop and peek with the same meaning and no locking.
Can I avoid boxing the indices? Yes. Use an int[] stack = new int[n] and an int top = 0: push with stack[top++] = i, peek with stack[top - 1] and pop with stack[--top]. The stack never holds more than n indices, so the array never overflows, and no Integer objects are created.
Why is the answer array not filled with zeros explicitly? Java zeroes every new int[], so new int[n] already says "no warmer day" for every position. Only the days that get popped are written; whatever is left on the stack at the end keeps its 0.
Why compare with < and not <= in the while loop? The wait ends at a strictly warmer day. With <=, an equal reading would pop the earlier day, so {8, 8, 5, 8, 10} would report 1 for the first 8 instead of 4.
Is the nested while loop O(n²) in the worst case? No. One reading can pop many indices, but each index is pushed once and popped at most once, so all the while iterations together are at most n.
FAQ for Go How do I write a stack in Go? Use a slice. Push with s = append(s, v), read the top with s[len(s)-1] and pop with s = s[:len(s)-1]. Popping only shortens the slice header; the backing array stays, so the next append reuses it without allocating.
Why give the stack a capacity in make? The stack can hold every index at once, for example on readings that only fall. make([]int, 0, len(temperatures)) allocates that room once, so append never has to grow and copy the backing array during the loop.
Does the function return nil for an empty input? No. make([]int, 0) is an empty, non-nil slice, so the result prints as [] and encoding/json marshals it as [] rather than null.
Why strictly less than when popping? An equal reading is not warmer. With <=, the second 8 in []int{8, 8, 5, 8, 10} would pop the first 8 and give it a wait of 1 instead of 4.
Is a loop inside a range loop still O(n)? Yes. Each index is appended once and popped at most once, so the inner for runs at most n times in total across the whole call.
FAQ for C# Stack<int> or the old non-generic Stack? System.Collections.Stack stores object, so every int is boxed on Push and needs a cast on Pop. Stack<int> from System.Collections.Generic stores the values directly and is type-safe; there is no reason to use the old one.
Why check Count before Peek? Peek and Pop throw InvalidOperationException on an empty stack. The waiting.Count > 0 && part short-circuits first, so Peek is never called on an empty stack. TryPeek(out int top) is the alternative that does both in one call.
Why strictly less than when popping? An equal reading is not warmer. With <=, the second 8 in { 8, 8, 5, 8, 10 } would pop the first and give it a wait of 1 instead of 4.
Can I skip the Stack class altogether? Yes: an int[] stack = new int[n] with an int top counter does the same job, pushing with stack[top++] = i and popping with stack[--top]. It avoids the occasional resize of Stack<int>, though at this size the difference is small.
Why is the nested while loop still O(n)? Each index is pushed once and popped at most once, so the while body runs at most n times across the whole method, however the readings are arranged.
FAQ for C++ Should I use std::stack instead of a vector? Either works. std::stack<int> from <stack> is an adapter over std::deque by default and gives you only push, top and pop, which documents the intent. A vector<int> with push_back, back and pop_back does the same, can reserve its memory once and keeps the indices contiguous.
Why does pop_back not return the value? In the standard library, removing and reading are separate on purpose: pop_back returns void, so read waiting.back() first and then pop. std::stack::pop works the same way with top.
Why check empty() before back()? Calling back() on an empty vector is undefined behaviour, not an exception. The !waiting.empty() && part short-circuits first, so back() is only reached when there is a top to read.
Why strictly less than when popping? An equal reading is not warmer. With <=, the second 8 in {8, 8, 5, 8, 10} would pop the first and give it a wait of 1 instead of 4.
Is the inner while loop O(n) per day? Only in a single step. Over the whole call each index is pushed once and popped at most once, so all the while iterations together are at most n, and the method is O(n).
FAQ for C Why calloc instead of malloc for the answer? calloc zeroes the memory, and 0 is exactly the answer for a day that never sees a warmer reading. With malloc you would need a memset(answer, 0, n * sizeof *answer) or a loop first, or the days left on the stack would return garbage.
Why allocate at least one element when the input is empty? malloc(0) and calloc(0, ...) may return NULL or a unique pointer, depending on the C library. Asking for one element always gives a real pointer, and *returnSize = 0 tells the caller not to read it.
How big does the stack array need to be? At most n. Every index is pushed once, so the stack can never hold more indices than there are days. That is why a fixed int array with a top counter is enough and never needs realloc.
Why compare with < and not <= when popping? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so {8, 8, 5, 8, 10} would give 1 for the first 8 instead of 4.
Who frees the returned array? The caller does, as the Note: comment says. The function frees only its own scratch stack before returning; freeing answer there would hand the caller a dangling pointer.
FAQ for Kotlin Which ArrayDeque is this, Kotlin or java.util? Without an import it is kotlin.collections.ArrayDeque, part of the standard library on every platform. Its stack calls are addLast, last() and removeLast(). java.util.ArrayDeque would use push, peek and pop on the head instead; both work, just do not mix the two sets of calls.
Why not use a MutableList as the stack? A mutableListOf<Int>() works the same way with add and removeAt(lastIndex), since removing at the end is constant time. ArrayDeque states the intent and its removeLast() reads clearly.
Can I avoid boxing the indices? Yes. Use val stack = IntArray(n) and var top = 0: push with stack[top++] = i, peek with stack[top - 1] and pop with stack[--top]. It never holds more than n indices, and no Int objects are boxed.
Why compare with < and not <= in the while loop? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so intArrayOf(8, 8, 5, 8, 10) would give 1 for the first 8 instead of 4.
Is the while inside the for loop O(n²)? No. Each index is added once and removed at most once, so all the while iterations together are at most n across the whole method.
FAQ for Rust Why does the stack hold usize and not i32? The stack holds positions, and Rust indexes slices only with usize. Keeping the indices as usize means temperatures[j] needs no cast; the one as i32 happens when the distance is written into the answer.
Why while let Some(&j) = waiting.last() with a break inside? last() returns an Option<&usize>, so while let keeps looping while the stack is not empty and binds the top by value. The break stops at the first waiting day that is not cooler. Writing while !waiting.is_empty() && temperatures[*waiting.last().unwrap()] < t works too, but needs an unwrap.
Can j - i underflow? No. Every index on the stack was pushed on an earlier iteration, so j < i whenever i - j is computed. In the brute force j starts at i + 1. In this debug build an underflow would panic rather than wrap, so the code would tell you.
Why compare with >= to break instead of < to pop? It is the same rule: pop while the top is strictly cooler, stop at an equal or warmer one. An equal reading must not end the wait, so vec![8, 8, 5, 8, 10] gives 4 for the first 8, not 1.
Why Vec::with_capacity? The stack never holds more than n indices, so reserving n up front means push never reallocates. It is an optimisation only; Vec::new() gives the same answer.
FAQ for Swift Is i + 1..<n safe on the last day? Yes. A half-open range a..<b traps only when a > b. Since i < n, i + 1 is at most n, and n..<n is just an empty range, so the inner loop does nothing on the last day.
How does while let j = waiting.last, temperatures[j] < t work? The condition list runs left to right: waiting.last is nil on an empty stack, which ends the loop; otherwise j is bound and the second clause checks that the waiting day is cooler. It reads as "while there is a top and it is cooler".
Does Swift have a built-in Stack type? No, and it does not need one. Array already has append, last and removeLast() at the end in amortised constant time, which is everything a stack does.
Why compare with < and not <=? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so [8, 8, 5, 8, 10] would give 1 for the first 8 instead of 4.
Do I need import Foundation here? No. Arrays, ranges, enumerated() and reserveCapacity are all in the standard library. Leaving Foundation out also keeps each Run faster.
FAQ for PHP Is array_fill(0, 0, 0) safe for an empty input? Yes. Since PHP 5.6 a count of 0 returns an empty array instead of a warning, so the empty case needs no special branch and the method returns [].
Why keep a $top counter instead of using end() or count()? count() on an array is constant time, so $waiting[count($waiting) - 1] works. end() also returns the last value but moves the internal pointer and returns false on an empty array. A $top counter is the plainest peek and makes the empty check a simple $top > 0.
Does array_pop keep the array a list? Yes. array_pop removes the last element and resets the next append key, so the following $waiting[] = $i lands at the freed position and the stack stays a 0-based list.
Why compare with < and not <=? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so [8, 8, 5, 8, 10] would give 1 for the first 8 instead of 4.
Could SplStack replace the array? SplStack has push, pop, top and isEmpty, and works here. A plain array is faster in practice for a stack of integers, and it is what most PHP solutions use.
FAQ for Ruby Is Array.new(n, 0) safe here? Yes. The second argument is shared by every slot, which bites with a mutable default like Array.new(n, []). Integers are immutable, so each answer[i] = ... simply replaces one slot.
Why while loops in the brute force instead of each and break? (i + 1...n).each with break gives the same answer, but each step calls a block. The largest case runs about 2 million comparisons, and plain while loops avoid that per-step overhead in the interpreter.
Does Ruby have a Stack class? No. Array already has push, pop and last at the end in amortised constant time, which is everything a stack needs.
Why compare with < and not <=? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so [8, 8, 5, 8, 10] would give 1 for the first 8 instead of 4.
Can I write the loop condition as until waiting.empty? || ...? Yes, until waiting.empty? || temperatures[waiting.last] >= t is the same loop. waiting.last returns nil on an empty array, so the emptiness check must come first, or temperatures[nil] raises a TypeError.
FAQ for Dart Why List.filled for the answer but a list literal for the stack? List.filled(n, 0) is fixed-length by default, which suits the answer: it never grows and every slot already holds 0. The stack grows and shrinks, so it needs a growable list such as <int>[]; calling add on a fixed-length list throws an UnsupportedError.
Do I need dart:collection for a stack? No. A plain List already has add, last and removeLast() at the end. Queue from dart:collection also works with addLast and removeLast, but adds nothing here.
What happens if I read waiting.last on an empty list? It throws a StateError ("No element"). That is why the while condition checks waiting.isNotEmpty first; && short-circuits, so last is never read on an empty stack.
Why compare with < and not <=? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so [8, 8, 5, 8, 10] would give 1 for the first 8 instead of 4.
Is the while inside the for loop O(n²)? No. Each index is added once and removed at most once, so all the while iterations together are at most n across the whole method.
FAQ for Scala Why ArrayBuffer instead of mutable.Stack? mutable.Stack works too, with push, top and pop; since Scala 2.13 it is backed by an ArrayDeque. ArrayBuffer keeps the stack at the end of a plain resizable array, and remove(length - 1) there is constant time.
Why a while loop in the brute force instead of a for with break? Scala has no break keyword for loops. The while condition carries the stop rule, "keep going while not warmer", so the loop ends at the first warmer day without boundary or a non-local return.
Is new Array[Int](n) really all zeros? Yes. Array[Int] is a JVM int[], which the runtime zeroes, so every day starts with the answer 0 and only the days that find a warmer reading are written.
Why compare with < and not <=? The wait ends only at a strictly warmer reading. With <=, an equal reading would pop the earlier day, so Array(8, 8, 5, 8, 10) would give 1 for the first 8 instead of 4.
Is there a functional way to write the stack pass? You can fold over temperatures.indices with an immutable List[Int] as the stack, consing on push and taking the tail on pop. It is the same O(n) idea, but the answer array still has to be written, so the mutable buffer version is the clearer one.
Keep going Jump Game 31 / 40 · Greedy · Medium Try Daily Temperatures in Python (Daily Temperatures in Python) , JavaScript (Daily Temperatures in JavaScript) , TypeScript (Daily Temperatures in TypeScript) , Java (Daily Temperatures in Java) , Go (Daily Temperatures in Go) , C# (Daily Temperatures in C#) , C++ (Daily Temperatures in C++) , C (Daily Temperatures in C) , Rust (Daily Temperatures in Rust) , Swift (Daily Temperatures in Swift) , PHP (Daily Temperatures in PHP) , Ruby (Daily Temperatures in Ruby) , Dart (Daily Temperatures in Dart) or Scala (Daily Temperatures in Scala)