| 22 Jan 2025 |
 brian_e | cool, goodluck! | 11:47:05 |
 silas | The APLcultivations cover this If you want an array oriented solution | 13:25:39 |
 hd3625 | thank you | 13:26:26 |
| hd3625 | ill lok at this | 13:26:36 |
| hd3625 | * ill look at this | 13:26:46 |
| 23 Jan 2025 |
 loke | I haven't read the entire book. and I suspect it ties into what was discussed earlier. But as a standalone example of how to solve it, it looks a bit overly complicated? | 02:30:32 |
 andover77. | such a great resource | 02:51:57 |
| andover77. | 02:51:57 |
 a.brudz | Announcement: [BAA Vector Webinar](https://aplwiki.com/wiki/BAA#Webinar) in 5 mins. | 15:54:09 |
|  rak1507#1964 changed their profile picture. | 18:30:27 |
 jam3943598 | How to do this in array style? https://leetcode.com/problems/daily-temperatures/description/ I have a solution but it's too complicated. | 20:13:05 |
 ludvikgalois | I'm struggling to even come up with an O(n) solution that doesn't require mutation, let alone being in an array style. Although, I can do O(n log n), which probably meets the timing requirements (still not in an array style though). | 20:53:37 |
 polylokh_39446 | Probably the O(n) solution is to solve it right-to-left. | 20:58:44 |
 dzaima | 30 <= temperatures[i] <= 100 means there's a simple O(70×n) option, but that's largely lame | 21:00:44 |
| jam3943598 | Best I've got: scan from the right into a list of lists of indices of decreasing values, then for each input, binary search the indices. nlogn, I think.
dailytemps_array(xs) = let
dec_seqs = accumulate(reverse(collect(enumerate(xs))); init=Int[]) do acc, (i, x)
j = binary_findlast(j -> xs[j] > x, acc)
push(acc[begin:j], i)
end |> reverse
ixs = map(xs, dec_seqs) do x, seq
get(seq, binary_findlast(j -> xs[j] > x, seq), 0)
end
max.(0, ixs .- eachindex(xs))
end
| 21:02:56 |
 Marshall | Have also done this in the BQN channel, searching the URL should find it? | 21:04:58 |
| polylokh_39446 | yeah that's the only other hit, a 2022 discussion | 21:05:53 |
| dzaima | (matrix / discord) | 21:06:14 |
| jam3943598 | Is Bins the binary-search primitive? | 21:15:55 |
| dzaima | yeah | 21:16:09 |
| jam3943598 | I feel like there's supposed to be a solution involving grade and bins | 21:17:05 |
| dzaima | I for some reason think a single Bins won't be enough | 21:17:37 |
 fiuzeri | I think I've got O(n log n) time and space in a pretty clean array style, but haven't written it down in any language yet.
the basic idea is:
generate the array
a[k][i] = max(input[i+1:i+2^k])
with each row being done in O(n) from two entries of the previous.
use this to generate:
b[k][i] = max(n s.t. max(input[i+1:i+n*2^k] < input[i])
c[k][i] = max(input[i+1:i+b[k][i]]) | 21:18:22 |
| dzaima | yeah, been thinking that you'd need a manual log(n) loop | 21:19:28 |
 discodoug | It’s worth noting that array approaches can often have different big O complexity than traditional approaches but still perform better due to things like more efficient use of memory. “So array idiomatic” and hitting specific big O targets can be at odds. | 21:19:39 |
| fiuzeri | each row of b is computed pointwise from the corresponding of a and the previous of c, each of c is from the corresponding of b. | 21:19:51 |
| fiuzeri | the last of b is the result, plus or minus the zeroing out not-found elements | 21:23:23 |
| Marshall | You mean a row of b comes from the next of c (larger k)? So first you decide whether to add the maximum 2^k to the index, then the next-highest, and so on. | 21:27:24 |
| jam3943598 | Yeah "container with most water" also is linear with pointers and nlogn with arrays, afaik. | 21:29:22 |
| ludvikgalois | The "expected" solution is something like
class Solution:
def dailyTemperatures(self, temperatures):
seen = []
results = [0] * len(temperatures)
for ix, t in enumerate(temperatures):
while len(seen) > 0 and temperatures[seen[-1]] < t:
x = seen.pop()
results[x] = ix - x
seen.append(ix)
return results
which doesn't have much "noise" (if not written in Python), so in this particular case I think you're only likely to have a speed up here if your array solution can make substantial use of parallelism. | 21:29:58 |
