[Programming Problem] Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

[Problem Link]

If you find a decreasing sequence keep moving forward until you find the number that breaks the sequence. Once you find that, move backward to find temperatures lower than that one. We could use a stack for this.

  1. Keep adding temperatures to a stack.
  2. If current temperature is less than or equal to the last element, add this temperature to the stack.
  3. If you find the current temperature is more than the last element on the stack you’ve found the next highest temperature for it (and possibly some temperatures before that). Keep doing this while the topmost element on the stack is less than the current temperature.

Basically when you find a decreasing sequence, just keep adding it to the stack. When that sequence breaks (meaning you find an element higher than the previous one), keep pop-ing elements from the stack to find temperatures that are lesser than the current temperature. We store indexes (and not actual temperatures) on the stack, so that we can calculate the days elapsed as we go.

Time and space complexity for this would be O(N)

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    if ( T.length === 0 ) return [];
    let ret = [];
    let arr = [ 0 ];
    T.forEach(function(curr, i) {
        if ( i === 0 ) return;
        while ( arr.length > 0 && T[arr[arr.length-1]] < curr ) {
            let lastElement = arr.pop();
            ret[lastElement] = i - lastElement;
        }
        arr.push(i);
    });
    if ( arr.length > 0 ) {
        arr.forEach(function(curr) {
            ret[curr] = 0;
        });
    }
    return ret;
};

softwareeveryday

10,499 thoughts on “[Programming Problem] Daily Temperatures”

  2777. Высшее образование в сфере гуманитарных и естественных наук на 12 факультетах по 35 специальностям первой ступени образования и 22 специальностям второй в Гомельском государственном университете имени Франциска Скорины.
    education высшее образование

    Reply

  7084. slot pg trial is open for service pg slots free 2023 test play PG SLOT We are a slots website open to all players. test playing slots before actually playing without having to apply first

    Reply

  9355. Играю в Казино Кэт уже несколько месяцев, и оно меня не перестает радовать. Ассортимент игровых автоматов широк, поддержка всегда помогает. 10/10!

    Reply
  9495. Pingback: child porn
  9497. Pingback: porn
  9511. Pingback: porn
  9516. Pingback: child porn
  9528. Pingback: porn
  9579. Pingback: porn
  9665. Pingback: https://olanibitenisikenadam.com
  9688. Pingback: dadsf absojpoajcnıjasdoaıjd
  9831. Pingback: https://sway.office.com/bGoHpJ5GIFA7LGs5?ref=Link
  9832. Pingback: https://www.flickr.com/people/199429455@N07/
  9833. Pingback: https://trello.com/u/whiteseotr1/activity
  9834. Pingback: https://padlet.com/whiteseotr1_/anl-padlet-im-xw2i54k1z1w881sm
  9835. Pingback: https://www.beatstars.com/whiteseotr1/about
  9836. Pingback: https://www.bitchute.com/channel/GzD0WCo4Y77n/

  9891. 欢迎来到我们的加密货币博客，这里是探索数字货币世界的绝佳平台。我们致力于提供最新的加密货币新闻、深入的市场分析、投资策略和技术解读。无论您是加密货币的初学者还是经验丰富的投资者，我们的博客都能为您提供有价值的见解。加入我们，一起探索比特币、以太坊、莱特币等多种加密货币的激动人心的旅程，并深入了解区块链技术如何改变世界。
    https://auto-noginsk.ru

    Reply

  9897. 크립토 코리아: 인사이트와 트렌드”는 한국에서 가장 신뢰받는 암호화폐 블로그 중 하나입니다. 최신 암호화폐 뉴스, 시장 분석, 트레이딩 전략을 제공하며, 블록체인 기술과 관련된 혁신적인 아이디어를 탐구합니다. 초보자부터 전문가까지 모든 수준의 투자자와 열정적인 크립토 커뮤니티가 찾는 곳입니다. 이 블로그는 한국의 크립토 트렌드를 이해하는 데 필수적인 자원이며, 암호화폐의 복잡한 세계를 이해하기 위한 명확하고 실용적인 가이드를 제공합니다. 여기서는 최신 ICO 분석, 암호화폐 거래소 리뷰, 블록체인 스타트업의 인터뷰 및 분석 기사를 찾을 수 있습니다.

    https://copyrait.ru/

    Reply

  9934. Welcome to CryptoSphere, your ultimate terminus in spite of all things cryptocurrency. Whether you’re a acclimatized investor or a curious newcomer, our blog offers a fullness of data to keep from you navigate the complex and ever-evolving sphere of digital currencies. From in-depth analyses of the latest market trends to practical guides on blockchain technology and investment strategies, CryptoSphere is your honest source in behalf of punctual, accurate, and insightful content. Verge on our community to interrupt ahead in the energetic and overpowering cosmos of cryptocurrency.

    aple-system.ru

    Reply

  9954. O mundo das criptomoedas tem atraido cada vez mais atencao nos ultimos anos, mas para realmente compreender o potencial desses ativos digitais, e essencial entender a tecnologia que esta por tras deles: o blockchain.

    O blockchain e uma tecnologia de registro distribuido que garante a seguranca e a transparencia das transacoes. Em essencia, e um livro-razao digital, onde as transacoes sao gravadas em ‘blocos’ e cada bloco esta conectado ao anterior, formando uma ‘cadeia’. Esta estrutura unica garante que uma vez que uma transacao e adicionada ao blockchain, ela nao pode ser alterada ou apagada, oferecendo um nivel de seguranca sem precedentes.

    Alem de ser a espinha dorsal das criptomoedas, como o Bitcoin e o Ethereum, o blockchain tem potencial para revolucionar diversos outros setores, como o financeiro, o juridico e ate mesmo o governo, oferecendo maneiras mais eficientes e seguras de realizar e registrar transacoes.

    No entanto, apesar de suas muitas vantagens, o blockchain ainda enfrenta desafios, incluindo questoes de escalabilidade e a necessidade de maior regulamentacao para prevenir usos ilicitos. Mas, a medida que a tecnologia continua a evoluir, ela oferece a promessa de um futuro mais transparente, seguro e eficiente.

    Para os entusiastas de criptomoedas, entender o blockchain nao e apenas uma questao de curiosidade, mas uma necessidade para navegar com seguranca e confianca neste novo e emocionante mundo digital.

    https://korablik-zabeg.ru

    Reply
  10386. Pingback: grandpashabet
  10390. Pingback: child porn
  10433. Pingback: child porn

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More