Where it runs
1. The problem
The last two lessons built segment trees. They answer a range question and take changes, both in O(log n). Now the data stops changing. A log file is closed at midnight, a reference table ships with the app, a puzzle grid is fixed in advance. There will be no more writes. And you still have to answer thousands of questions like "what is the smallest value between index l and r?"
A segment tree would work here, but O(log n) per query is more than you need to pay. If the array never changes, you can work out enough in advance that each range-minimum query costs O(1). This structure is called a sparse table.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems on an array that never changes, with many minimum, maximum or GCD questions over ranges. After O(n log n) building, two overlapping blocks answer each range in O(1). LeetCode never names the sparse table, and a monotonic deque or a segment tree also passes most of these.
Every window is a range, so build a max table once and answer each window in O(1). The deque from lesson 56 does it in O(n).
- 1438.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (opens in a new tab)Medium
Grow the window with two pointers and read its max and min from two tables, moving the left end while their gap is above limit.
Put a before b. If a equals b or b is taller, the answer is b. Otherwise binary search for the first index after b where the range max beats the taller of the two.