3691. Maximum Total Subarray Value II

HardGreedySegment TreeArrayHeap (Priority Queue)

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n and an integer k.

Your task is to select exactly k distinct non-empty subarrays nums[l..r] from nums. Two important rules apply to the selection:

Subarrays may overlap with each other.
The exact same subarray (identical l and r) cannot be chosen more than once.

Each subarray nums[l..r] has a value, defined as:

max(nums[l..r]) - min(nums[l..r])

In other words, the value of a subarray is the difference between its largest and smallest elements.

The total value of your selection is the sum of the values of all k chosen subarrays.

Return the maximum possible total value you can achieve.

Key points to understand:

A subarray is a contiguous portion of the array, so it is uniquely identified by its left boundary l and right boundary r.
An array of length n has n * (n + 1) / 2 distinct subarrays in total, and you must pick exactly k of them.
Since you want to maximize the sum, the goal is essentially to find the k subarrays with the largest values (max-min differences) and add those values together.
A subarray consisting of a single element always has a value of 0, because its maximum and minimum are the same element.

Example:

Suppose nums = [1, 3, 2] and k = 2.

The subarray [1, 3, 2] has value 3 - 1 = 2.
The subarray [1, 3] has value 3 - 1 = 2.
The subarray [3, 2] has value 3 - 2 = 1.

Choosing the two subarrays with the largest values, [1, 3, 2] and [1, 3], gives a total value of 2 + 2 = 4, which is the maximum achievable.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Heap / Sortings?

This problem maps to Heap / Sortings through a short path in the full flowchart.

Finding the k largest subarray values among monotonic sequences reduces to merging n sorted lists with a max-heap.

Open in Flowchart

Intuition

The brute-force idea would be to compute the value of every possible subarray, sort them all, and take the top k. But there are n * (n + 1) / 2 subarrays, which can be far too many to enumerate and sort when n is large. We need a way to find the k largest values without generating all of them.

The key observation is a monotonicity property. Fix the left boundary l and let the right boundary r grow to the right. As the subarray extends:

The maximum max(nums[l..r]) can only stay the same or increase.
The minimum min(nums[l..r]) can only stay the same or decrease.

Therefore, the value max(nums[l..r]) - min(nums[l..r]) is non-decreasing as r grows. For every fixed l, the largest value is always achieved at r = n - 1.

This restructures the problem nicely: instead of one giant unordered pile of subarray values, we now have n sorted (non-decreasing) sequences — one per left endpoint l. The task becomes a classic one:

Given n sorted sequences, find the sum of the top k elements overall.

This is exactly the pattern of "merge k sorted lists" solved with a max-heap:

Push the largest element of each sequence into the heap — that is, push (value of nums[l..n-1], l, n-1) for every l.
Pop the heap k times. Each pop gives the current global maximum among all remaining candidates. After popping (val, l, r), the next-largest candidate from that same sequence is the subarray nums[l..r-1] (if r > l), so push it in.

This works because of the monotonicity: when we pop (l, r), every longer subarray with the same l has already been considered, and (l, r-1) is guaranteed to be the next candidate from that sequence with a value no greater than the popped one. So the heap always contains the correct frontier of candidates, and each pop is guaranteed to be the true next-largest value.

The last piece is efficiency: each heap operation requires knowing max(nums[l..r]) - min(nums[l..r]) for an arbitrary range. Computing this naively would cost O(n) per query. Since the array never changes, we can precompute a Sparse Table, which answers any range-max and range-min query in O(1) after O(n log n) preprocessing.

Putting it together: the heap holds at most n entries, we perform k pops, and each step does O(1) range queries — giving roughly O((n + k) log n) total time, which avoids ever touching all O(n^2) subarrays.

Pattern Learn more about Greedy, Segment Tree and Heap (Priority Queue) patterns.

Solution Approach

The solution combines two components: a Sparse Table for O(1) range max/min queries, and a max-heap to greedily extract the top k subarray values.

Step 1: Build the Sparse Table

The SparseTableRMQ class precomputes answers for range maximum and range minimum queries using the doubling technique.

f_max[i][j] stores the maximum of the range starting at index i with length 2^j, i.e., nums[i..i + 2^j - 1].
f_min[i][j] stores the minimum of the same range.

Initialization (base case j = 0): a range of length 1 is just the element itself:

self.f_max[i][0] = data[i]
self.f_min[i][0] = data[i]

Transition: a range of length 2^j is split into two halves of length 2^(j-1):

self.f_max[i][j] = max(self.f_max[i][j - 1], self.f_max[i + (1 << (j - 1))][j - 1])
self.f_min[i][j] = min(self.f_min[i][j - 1], self.f_min[i + (1 << (j - 1))][j - 1])

We also precompute a logarithm table lg, where lg[i] = floor(log2(i)), so queries avoid calling a log function:

self.lg[i] = self.lg[i >> 1] + 1

Querying [l, r]: let k = lg[r - l + 1]. Two ranges of length 2^k — one starting at l and one ending at r — together cover [l, r] (they may overlap, which is harmless for max/min):

def query_max(self, l, r):
    k = self.lg[r - l + 1]
    return max(self.f_max[l][k], self.f_max[r - (1 << k) + 1][k])

Preprocessing takes O(n log n) time and space; each query takes O(1).

Step 2: Initialize the Max-Heap

For each left endpoint l, the largest value among all subarrays starting at l is achieved by the longest one, nums[l..n-1] (due to the monotonicity property). We push all n of these into the heap:

pq = []
for l in range(n):
    val = st.query_max(l, n - 1) - st.query_min(l, n - 1)
    heappush(pq, (-val, l, n - 1))

Python's heapq is a min-heap, so values are negated to simulate a max-heap. Each entry is a tuple (-val, l, r) recording the subarray's value and its boundaries.

Step 3: Greedily Extract the Top `k` Values

We pop from the heap exactly k times. Each pop yields the current global maximum among all remaining candidate subarrays:

ans = 0
for _ in range(k):
    val, l, r = heappop(pq)
    ans += -val
    if r > l:
        val = st.query_max(l, r - 1) - st.query_min(l, r - 1)
        heappush(pq, (-val, l, r - 1))
return ans

After popping (val, l, r):

Add val to the answer.
If r > l, the sequence for left endpoint l still has shorter subarrays left. The next candidate is nums[l..r-1], whose value is no greater than the one just popped. Compute it with the sparse table and push it in.
If r == l, the sequence for this l is exhausted (the single-element subarray with value 0 was the last one).

This is the classic "merge n sorted lists, take top k" pattern: the heap always holds at most one frontier candidate per sequence, and monotonicity guarantees that no skipped subarray can ever exceed a popped one.

Complexity Analysis

Time: O((n + k) log n) — building the sparse table costs O(n log n), the initial heap construction performs n pushes, and the main loop performs k pops/pushes, each costing O(log n) with O(1) range queries.
Space: O(n log n) for the sparse table, plus O(n) for the heap.

Example Walkthrough

Let's trace the algorithm with nums = [1, 3, 2] and k = 3.

All 6 subarrays and their values (for reference):

Subarray	`(l, r)`	max	min	Value
`[1]`	`(0, 0)`	1	1	0
`[3]`	`(1, 1)`	3	3	0
`[2]`	`(2, 2)`	2	2	0
`[1, 3]`	`(0, 1)`	3	1	2
`[3, 2]`	`(1, 2)`	3	2	1
`[1, 3, 2]`	`(0, 2)`	3	1	2

The top 3 values are 2 + 2 + 1 = 5 — this is the answer the algorithm should produce without enumerating all six subarrays.

Step 1: Build the Sparse Table

Log table: lg[1] = 0, lg[2] = 1, lg[3] = 1.
Length-1 ranges (j = 0): f_max[i][0] = f_min[i][0] = nums[i] → [1, 3, 2].
Length-2 ranges (j = 1):
- f_max[0][1] = max(1, 3) = 3, f_min[0][1] = 1
- f_max[1][1] = max(3, 2) = 3, f_min[1][1] = 2

A query on [0, 2] uses k = lg[3] = 1: it combines the two length-2 ranges [0, 1] and [1, 2], giving max(3, 3) = 3 and min(1, 2) = 1 in O(1).

Step 2: Initialize the max-heap

For each left endpoint l, push the longest subarray nums[l..2] (the largest candidate for that l, by monotonicity):

l = 0: query [0, 2] → 3 − 1 = 2 → push (-2, 0, 2)
l = 1: query [1, 2] → 3 − 2 = 1 → push (-1, 1, 2)
l = 2: query [2, 2] → 2 − 2 = 0 → push (0, 2, 2)

Heap (as a max-heap on value): {(2, 0, 2), (1, 1, 2), (0, 2, 2)}.

Step 3: Pop k = 3 times

Pop #	Popped `(val, l, r)`	Running `ans`	Pushed next (shrink `r` by 1)
1	`(2, 0, 2)`	`0 + 2 = 2`	Query `[0, 1]` → `3 − 1 = 2` → push `(2, 0, 1)`
2	`(2, 0, 1)`	`2 + 2 = 4`	Query `[0, 0]` → `0` → push `(0, 0, 0)`
3	`(1, 1, 2)`	`4 + 1 = 5`	Query `[1, 1]` → `0` → push `(0, 1, 1)`

Notice what happened:

After popping [1, 3, 2] (value 2), its shorter sibling [1, 3] immediately entered the heap and was popped next — the monotonicity guarantee at work: shrinking r can never increase the value, so the frontier candidate per l is always sufficient.
The single-element subarrays (value 0) entered the heap but were never popped, since better candidates remained.
The remaining O(n²) subarrays were never even generated.

Result: ans = 5, matching the brute-force answer of selecting [1, 3, 2], [1, 3], and [3, 2].

Solution Implementation

1from typing import List
2from heapq import heappush, heappop
3
4
5class SparseTableRMQ:
6    """Sparse Table supporting O(1) range max/min queries after O(n log n) preprocessing."""
7
8    def __init__(self, data: List[int]):
9        self.n = len(data)
10        # Maximum power of two needed to cover any interval length.
11        self.max_log = self.n.bit_length() + 1
12
13        # f_max[i][j]: maximum of the interval starting at i with length 2^j.
14        # f_min[i][j]: minimum of the interval starting at i with length 2^j.
15        self.f_max = [[0] * self.max_log for _ in range(self.n)]
16        self.f_min = [[0] * self.max_log for _ in range(self.n)]
17
18        # Precompute floor(log2(x)) for every interval length 1..n.
19        self.lg = [0] * (self.n + 1)
20        for i in range(2, self.n + 1):
21            self.lg[i] = self.lg[i >> 1] + 1
22
23        # Base case: intervals of length 2^0 = 1 are the elements themselves.
24        for i in range(self.n):
25            self.f_max[i][0] = data[i]
26            self.f_min[i][0] = data[i]
27
28        # Build the table by doubling: an interval of length 2^j is the
29        # combination of two adjacent intervals of length 2^(j-1).
30        for j in range(1, self.max_log):
31            for i in range(self.n - (1 << j) + 1):
32                self.f_max[i][j] = max(
33                    self.f_max[i][j - 1], self.f_max[i + (1 << (j - 1))][j - 1]
34                )
35                self.f_min[i][j] = min(
36                    self.f_min[i][j - 1], self.f_min[i + (1 << (j - 1))][j - 1]
37                )
38
39    def query_max(self, left: int, right: int) -> int:
40        """Return the maximum value in the inclusive range [left, right]."""
41        k = self.lg[right - left + 1]
42        # Cover [left, right] with two (possibly overlapping) blocks of length 2^k.
43        return max(self.f_max[left][k], self.f_max[right - (1 << k) + 1][k])
44
45    def query_min(self, left: int, right: int) -> int:
46        """Return the minimum value in the inclusive range [left, right]."""
47        k = self.lg[right - left + 1]
48        # Cover [left, right] with two (possibly overlapping) blocks of length 2^k.
49        return min(self.f_min[left][k], self.f_min[right - (1 << k) + 1][k])
50
51
52class Solution:
53    def maxTotalValue(self, nums: List[int], k: int) -> int:
54        n = len(nums)
55        sparse_table = SparseTableRMQ(nums)
56
57        # Max-heap (simulated with negated values) of candidate subarrays.
58        # Key observation: for a fixed left endpoint, the value
59        # (max - min) is non-increasing as the right endpoint shrinks.
60        # So for each left endpoint, the widest subarray [left, n-1]
61        # gives the largest value; we push those first.
62        max_heap = []
63        for left in range(n):
64            value = sparse_table.query_max(left, n - 1) - sparse_table.query_min(left, n - 1)
65            heappush(max_heap, (-value, left, n - 1))
66
67        ans = 0
68        # Pop the k largest values; after taking [left, right], the next-best
69        # candidate with the same left endpoint is [left, right - 1].
70        for _ in range(k):
71            neg_value, left, right = heappop(max_heap)
72            ans += -neg_value
73            if right > left:
74                value = sparse_table.query_max(left, right - 1) - sparse_table.query_min(left, right - 1)
75                heappush(max_heap, (-value, left, right - 1))
76        return ans
77

1import java.util.PriorityQueue;
2
3/**
4 * Sparse Table for Range Minimum/Maximum Queries (RMQ).
5 * Preprocessing: O(n log n) time and space.
6 * Query: O(1) per range max/min query.
7 */
8class SparseTableRMQ {
9    /** Number of elements in the underlying array. */
10    private final int n;
11    /** Number of levels in the sparse table (log2(n) + 1). */
12    private final int maxLog;
13    /** sparseMax[i][j] = maximum of the range [i, i + 2^j - 1]. */
14    private final int[][] sparseMax;
15    /** sparseMin[i][j] = minimum of the range [i, i + 2^j - 1]. */
16    private final int[][] sparseMin;
17    /** log2Floor[len] = floor(log2(len)), precomputed for O(1) queries. */
18    private final int[] log2Floor;
19
20    public SparseTableRMQ(int[] data) {
21        this.n = data.length;
22        this.maxLog = 32 - Integer.numberOfLeadingZeros(n) + 1;
23        this.sparseMax = new int[n][maxLog];
24        this.sparseMin = new int[n][maxLog];
25        this.log2Floor = new int[n + 1];
26
27        // Precompute floor(log2(i)) for every length from 2 to n.
28        for (int i = 2; i <= n; i++) {
29            log2Floor[i] = log2Floor[i >> 1] + 1;
30        }
31
32        // Base level: ranges of length 1 are just the elements themselves.
33        for (int i = 0; i < n; i++) {
34            sparseMax[i][0] = data[i];
35            sparseMin[i][0] = data[i];
36        }
37
38        // Build higher levels: a range of length 2^j is the combination
39        // of two overlapping (here, adjacent) ranges of length 2^(j-1).
40        for (int j = 1; j < maxLog; j++) {
41            for (int i = 0; i + (1 << j) <= n; i++) {
42                int rightStart = i + (1 << (j - 1));
43                sparseMax[i][j] = Math.max(sparseMax[i][j - 1], sparseMax[rightStart][j - 1]);
44                sparseMin[i][j] = Math.min(sparseMin[i][j - 1], sparseMin[rightStart][j - 1]);
45            }
46        }
47    }
48
49    /**
50     * Returns the maximum value in the inclusive range [left, right].
51     * Uses two overlapping power-of-two ranges that cover [left, right].
52     */
53    public int queryMax(int left, int right) {
54        int k = log2Floor[right - left + 1];
55        return Math.max(sparseMax[left][k], sparseMax[right - (1 << k) + 1][k]);
56    }
57
58    /**
59     * Returns the minimum value in the inclusive range [left, right].
60     * Uses two overlapping power-of-two ranges that cover [left, right].
61     */
62    public int queryMin(int left, int right) {
63        int k = log2Floor[right - left + 1];
64        return Math.min(sparseMin[left][k], sparseMin[right - (1 << k) + 1][k]);
65    }
66}
67
68class Solution {
69    /**
70     * Computes the maximum total value obtainable by selecting the k subarrays
71     * with the largest values, where the value of a subarray [l, r] is defined
72     * as max(nums[l..r]) - min(nums[l..r]).
73     *
74     * Key observation: for a fixed left endpoint l, the value of [l, r] is
75     * non-increasing as r decreases (shrinking a range can only reduce the
76     * max-min spread). Therefore, a max-heap seeded with the widest range for
77     * each left endpoint can lazily enumerate subarray values in descending
78     * order, similar to a k-way merge of sorted sequences.
79     *
80     * Time complexity: O((n + k) log n).
81     */
82    public long maxTotalValue(int[] nums, int k) {
83        int n = nums.length;
84        SparseTableRMQ rmq = new SparseTableRMQ(nums);
85
86        // Max-heap ordered by subarray value; entries are {value, left, right}.
87        PriorityQueue<long[]> maxHeap = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
88
89        // Seed the heap with the widest subarray [l, n - 1] for each left endpoint,
90        // which holds the largest value among all subarrays starting at l.
91        for (int left = 0; left < n; left++) {
92            long value = (long) rmq.queryMax(left, n - 1) - rmq.queryMin(left, n - 1);
93            maxHeap.offer(new long[] {value, left, n - 1});
94        }
95
96        long answer = 0;
97        // Extract the top k values; after taking [l, r], push its successor [l, r - 1],
98        // the next-largest candidate sharing the same left endpoint.
99        for (int i = 0; i < k; i++) {
100            long[] top = maxHeap.poll();
101            long value = top[0];
102            int left = (int) top[1];
103            int right = (int) top[2];
104            answer += value;
105
106            // Push the shrunken range if it is still non-empty.
107            if (right > left) {
108                long nextValue = (long) rmq.queryMax(left, right - 1) - rmq.queryMin(left, right - 1);
109                maxHeap.offer(new long[] {nextValue, left, right - 1});
110            }
111        }
112        return answer;
113    }
114}
115

1class SparseTableRMQ {
2public:
3    int n;                          // Number of elements in the input array
4    int maxLog;                     // Maximum power of two needed for the table
5    vector<vector<int>> maxTable;   // maxTable[i][j] = max of range [i, i + 2^j - 1]
6    vector<vector<int>> minTable;   // minTable[i][j] = min of range [i, i + 2^j - 1]
7    vector<int> logTable;           // Precomputed floor(log2(x)) for fast queries
8
9    // Build the sparse table in O(n log n) time
10    SparseTableRMQ(const vector<int>& data) {
11        n = static_cast<int>(data.size());
12        maxLog = 32 - __builtin_clz(n) + 1;
13        maxTable.assign(n, vector<int>(maxLog, 0));
14        minTable.assign(n, vector<int>(maxLog, 0));
15        logTable.assign(n + 1, 0);
16
17        // Precompute logarithms: logTable[i] = floor(log2(i))
18        for (int i = 2; i <= n; i++) {
19            logTable[i] = logTable[i >> 1] + 1;
20        }
21
22        // Base case: ranges of length 1 are the elements themselves
23        for (int i = 0; i < n; i++) {
24            maxTable[i][0] = data[i];
25            minTable[i][0] = data[i];
26        }
27
28        // Combine two halves of length 2^(j-1) to cover length 2^j
29        for (int j = 1; j < maxLog; j++) {
30            for (int i = 0; i + (1 << j) <= n; i++) {
31                maxTable[i][j] = max(maxTable[i][j - 1], maxTable[i + (1 << (j - 1))][j - 1]);
32                minTable[i][j] = min(minTable[i][j - 1], minTable[i + (1 << (j - 1))][j - 1]);
33            }
34        }
35    }
36
37    // Query the maximum value in range [left, right] in O(1)
38    int queryMax(int left, int right) {
39        int k = logTable[right - left + 1];
40        return max(maxTable[left][k], maxTable[right - (1 << k) + 1][k]);
41    }
42
43    // Query the minimum value in range [left, right] in O(1)
44    int queryMin(int left, int right) {
45        int k = logTable[right - left + 1];
46        return min(minTable[left][k], minTable[right - (1 << k) + 1][k]);
47    }
48};
49
50class Solution {
51public:
52    long long maxTotalValue(vector<int>& nums, int k) {
53        int n = static_cast<int>(nums.size());
54        SparseTableRMQ rmq(nums);
55
56        // Max-heap ordered by the range value (max - min) of subarray [left, right]
57        auto compare = [](const tuple<long long, int, int>& a, const tuple<long long, int, int>& b) {
58            return get<0>(a) < get<0>(b);
59        };
60        priority_queue<tuple<long long, int, int>,
61                       vector<tuple<long long, int, int>>,
62                       decltype(compare)> maxHeap(compare);
63
64        // For each left endpoint, the widest subarray [left, n - 1]
65        // yields the largest possible value, so seed the heap with these
66        for (int left = 0; left < n; left++) {
67            long long value = rmq.queryMax(left, n - 1) - rmq.queryMin(left, n - 1);
68            maxHeap.push({value, left, n - 1});
69        }
70
71        long long answer = 0;
72
73        // Extract the k largest values; after taking [left, right],
74        // the next candidate for the same left endpoint is [left, right - 1]
75        for (int i = 0; i < k; i++) {
76            auto [value, left, right] = maxHeap.top();
77            maxHeap.pop();
78            answer += value;
79
80            // Push the shrunken range as the next best candidate for this left endpoint
81            if (right > left) {
82                long long nextValue = rmq.queryMax(left, right - 1) - rmq.queryMin(left, right - 1);
83                maxHeap.push({nextValue, left, right - 1});
84            }
85        }
86
87        return answer;
88    }
89};
90

1// Number of elements in the source array
2let n: number;
3// Maximum power of two needed for the sparse table
4let maxLog: number;
5// Sparse table for range maximum queries: fMax[i][j] = max of nums[i .. i + 2^j - 1]
6let fMax: number[][];
7// Sparse table for range minimum queries: fMin[i][j] = min of nums[i .. i + 2^j - 1]
8let fMin: number[][];
9// Precomputed floor(log2(x)) values for fast lookup
10let lg: number[];
11
12/**
13 * Builds the sparse tables and the log lookup table for the given data.
14 * Preprocessing time: O(n log n), enabling O(1) range max/min queries.
15 */
16function buildSparseTable(data: number[]): void {
17    n = data.length;
18    maxLog = Math.floor(Math.log2(n)) + 2;
19    fMax = Array.from({ length: n }, () => Array(maxLog).fill(0));
20    fMin = Array.from({ length: n }, () => Array(maxLog).fill(0));
21    lg = Array(n + 1).fill(0);
22
23    // Precompute floor(log2(i)) for every length 2..n
24    for (let i = 2; i <= n; i++) {
25        lg[i] = lg[i >> 1] + 1;
26    }
27
28    // Base case: intervals of length 1 (2^0)
29    for (let i = 0; i < n; i++) {
30        fMax[i][0] = data[i];
31        fMin[i][0] = data[i];
32    }
33
34    // Build longer intervals by merging two halves of length 2^(j-1)
35    for (let j = 1; j < maxLog; j++) {
36        for (let i = 0; i <= n - (1 << j); i++) {
37            fMax[i][j] = Math.max(
38                fMax[i][j - 1],
39                fMax[i + (1 << (j - 1))][j - 1],
40            );
41            fMin[i][j] = Math.min(
42                fMin[i][j - 1],
43                fMin[i + (1 << (j - 1))][j - 1],
44            );
45        }
46    }
47}
48
49/**
50 * Returns the maximum value in nums[l..r] in O(1)
51 * by combining two overlapping power-of-two intervals.
52 */
53function queryMax(l: number, r: number): number {
54    const k = lg[r - l + 1];
55    return Math.max(fMax[l][k], fMax[r - (1 << k) + 1][k]);
56}
57
58/**
59 * Returns the minimum value in nums[l..r] in O(1)
60 * by combining two overlapping power-of-two intervals.
61 */
62function queryMin(l: number, r: number): number {
63    const k = lg[r - l + 1];
64    return Math.min(fMin[l][k], fMin[r - (1 << k) + 1][k]);
65}
66
67/**
68 * Computes the maximum total value of the top k subarrays,
69 * where the value of a subarray is (max element - min element).
70 *
71 * Strategy:
72 * 1. For each left endpoint l, the widest interval [l, n-1] has the
73 *    largest possible value (shrinking the right end never increases it).
74 * 2. Push all such widest intervals into a max-heap keyed by value.
75 * 3. Pop k times; after popping [l, r], push its successor [l, r-1],
76 *    which is the next-best interval sharing the same left endpoint.
77 */
78function maxTotalValue(nums: number[], k: number): number {
79    const len = nums.length;
80    buildSparseTable(nums);
81
82    // Max-heap of tuples [value, leftIndex, rightIndex], ordered by value descending
83    const pq = new PriorityQueue<[number, number, number]>((a, b) => b[0] - a[0]);
84
85    // Seed the heap with the best (widest) interval for each left endpoint
86    for (let l = 0; l < len; l++) {
87        const val = queryMax(l, len - 1) - queryMin(l, len - 1);
88        pq.enqueue([val, l, len - 1]);
89    }
90
91    let ans = 0;
92    // Extract the k largest interval values
93    for (let i = 0; i < k; i++) {
94        if (pq.isEmpty()) break;
95        const [val, l, r] = pq.dequeue()!;
96        ans += val;
97        // Push the next candidate with the same left endpoint and a shorter range
98        if (r > l) {
99            const nextVal = queryMax(l, r - 1) - queryMin(l, r - 1);
100            pq.enqueue([nextVal, l, r - 1]);
101        }
102    }
103    return ans;
104}
105

Time and Space Complexity

Time Complexity: O(n log n + k log n), where n is the length of the array nums.
- Sparse Table Construction: Building f_max and f_min requires filling a table of size n × O(log n), where each entry is computed in O(1) time, costing O(n log n) in total. The lg array is precomputed in O(n).
- Heap Initialization: For each left endpoint l (there are n of them), one RMQ query is performed in O(1) and one heappush is performed in O(log n), costing O(n log n) in total.
- Extracting the Top-k Values: The loop runs k times; each iteration performs one heappop and at most one heappush on a heap of size at most n (each in O(log n)), plus O(1) RMQ queries, costing O(k log n) in total.
- Summing these parts gives O(n log n) + O(n log n) + O(k log n) = O(n log n + k log n).
Space Complexity: O(n log n), where n is the length of the array nums.
- The sparse tables f_max and f_min each occupy O(n log n) space, which dominates.
- The lg array takes O(n) space, and the heap pq holds at most n entries, i.e., O(n) space.
- Therefore, the overall space usage is O(n log n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Assuming subarray values are independent per left endpoint without the monotonicity guarantee

The heap-based "merge n sorted lists" approach is only correct because of a key property: for a fixed left endpoint l, the value max(nums[l..r]) - min(nums[l..r]) is non-decreasing as r grows (extending a range can only raise the max or lower the min, never the opposite). A common mistake is to apply this pattern to a different value function (e.g., subarray sum, which is not monotonic in r) or to enumerate candidates in an order that breaks monotonicity (e.g., shrinking from the left while the heap entries are keyed by left endpoint). If the per-sequence values are not sorted, the heap no longer guarantees that the k popped values are the global top k.

Solution: Verify the monotonicity argument before reusing this pattern. Here, each "sorted list" is the family of subarrays [l, n-1], [l, n-2], ..., [l, l] for a fixed l, whose values are non-increasing. After popping (l, r), push only its direct successor (l, r-1) — never skip ahead or push multiple successors, or you risk duplicates.

Pitfall 2: Pushing duplicate subarrays into the heap

If, after popping (l, r), you push both (l, r-1) and (l+1, r) (a tempting "expand in both directions" idea borrowed from other problems), the same subarray can enter the heap via multiple paths — e.g., (l+1, r-1) is reachable from both (l, r-1) and (l+1, r). Since the problem forbids choosing the identical subarray twice, duplicates inflate the answer.

Solution: Either stick to the one-dimensional successor scheme used in this code (each l owns its own chain, and only (l, r-1) is pushed), or, if expanding in two directions, maintain a visited set of (l, r) pairs and skip already-seen entries before pushing.

Pitfall 3: Computing values eagerly for all `O(n²)` subarrays

A naive approach precomputes the value of every subarray, sorts them, and takes the top k. With n up to typical constraint sizes (e.g., 10^5), this requires O(n²) time and memory and will TLE/MLE.

Solution: Use the lazy heap approach shown: keep at most one frontier candidate per left endpoint, so the heap never exceeds n entries and total work is O((n + k) log n).

Pitfall 4: Sparse table indexing and sizing errors

Two frequent off-by-one mistakes when hand-rolling the sparse table:

Inner loop bound: the start index i must satisfy i + 2^j - 1 <= n - 1, i.e., iterate for i in range(n - (1 << j) + 1). Writing range(n - (1 << j)) silently drops the last valid interval, producing wrong query results near the array's right edge.
Query block placement: the second block must end at right, so it starts at right - (1 << k) + 1. Forgetting the + 1 shifts the block and may read out of the covered range.

Note that overlapping blocks are harmless only for idempotent operations like max/min/gcd. Reusing this exact two-block query for sums would double-count the overlap.

Solution: Carefully derive both bounds from the invariant "block of length 2^j starting at i covers [i, i + 2^j - 1]", and test queries at the boundaries (l = 0, r = n - 1, and l == r).

Pitfall 5: Forgetting that Python's `heapq` is a min-heap

Pushing (value, l, r) instead of (-value, l, r) extracts the k smallest values, yielding a drastically wrong (often zero-heavy) answer. Conversely, after negating, forgetting to negate back when accumulating (ans += -neg_value) produces a negative total.

Solution: Negate consistently on both push and pop, or wrap values in a comparator-flipping class. A quick sanity check: the answer must be non-negative, and with k = 1 it must equal max(nums) - min(nums).

Pitfall 6: Not terminating the chain at single-element subarrays

After popping (l, r) with r == l, pushing (l, r - 1) creates an invalid subarray with r < l, which either crashes the sparse table query or silently adds garbage values.

Solution: Guard the push with if right > left: as the code does. Single-element subarrays (value 0) are valid selections — they are still counted toward k when popped — but they have no successor.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: