Skip to main content

# Daily Temperatures

Given an array of integers `temperatures` represents the daily temperatures, return an array answer such that `answer[i]` is the number of days you have to wait after the `ith` day to get a warmer temperature. If there is no future day for which this is possible, keep `answer[i] == 0` instead.

``package questionsimport _utils.UseCommentAsDocumentationimport utils.shouldBeimport java.util.*/** * Given an array of integers `temperatures` represents the daily temperatures, return an array answer * such that `answer[i]` is the number of days you have to wait after the `ith` day to get a warmer temperature. * If there is no future day for which this is possible, keep `answer[i] == 0` instead. * * [Source](https://leetcode.com/problems/daily-temperatures/) */@UseCommentAsDocumentationprivate fun dailyTemperatures(temperatures: IntArray): IntArray {    val ans = IntArray(temperatures.size) { 0 }    // Maintain an actual index that points the next higher temperature than current    // indices          = 0, 1, 2, 3, 4    // temp             = 4, 9, 6, 5, 7    // successorPointer = 1, 0, 4, 4, null    val successorPointer = Array<Int?>(temperatures.size) { null }    // no further higher temperature for last element    successorPointer[successorPointer.lastIndex] = null    for (i in temperatures.lastIndex - 1 downTo 0) {        val currentTemp = temperatures[i]        val nextTemp = temperatures[i + 1]        if (nextTemp > currentTemp) {            ans[i] = 1            successorPointer[i] = i + 1        } else {            val nextIndex = findImmediateSuccessorIndex(temperatures, successorPointer, i + 1, temperatures[i])            if (nextIndex == null) {                ans[i] = 0 // no higher temp            } else {                ans[i] = nextIndex - i                successorPointer[i] = nextIndex            }        }    }    return ans}private fun findImmediateSuccessorIndex(    temperatures: IntArray,    successorPointers: Array<Int?>,    index: Int?,    target: Int): Int? {    if (index == null) {        return null    }    val nextIndex = successorPointers[index] ?: return null    return if (temperatures[nextIndex] > target) { // found next higher temp        nextIndex    } else {        // not found so go to whatever its successor is        findImmediateSuccessorIndex(temperatures, successorPointers, nextIndex, target)    }}fun main() {    dailyTemperatures(intArrayOf(80, 34, 80, 80, 80, 34, 34, 34, 34, 34)) shouldBe            intArrayOf(0, 1, 0, 0, 0, 0, 0, 0, 0, 0)    dailyTemperatures(intArrayOf(34, 80, 80, 34, 34, 80, 80, 80, 80, 34)) shouldBe            intArrayOf(1, 0, 0, 2, 1, 0, 0, 0, 0, 0)    dailyTemperatures(intArrayOf(89, 62, 70, 58, 47, 47, 46, 76, 100, 70)) shouldBe            intArrayOf(8, 1, 5, 4, 3, 2, 1, 1, 0, 0)    dailyTemperatures(intArrayOf(30, 60, 90)) shouldBe intArrayOf(1, 1, 0)    dailyTemperatures(intArrayOf(73, 74, 75, 71, 69, 72, 76, 73)) shouldBe intArrayOf(1, 1, 4, 2, 1, 1, 0, 0)    dailyTemperatures(intArrayOf(30, 40, 50, 60)) shouldBe intArrayOf(1, 1, 1, 0)}``

Updated on 2021-11-13