Introduction
Given two arrays r[] and h[] of size n, where r[i] represents the radius and h[i] represents the height of the i-th disc, the goal is to build a stack with the maximum possible total height.
A disc can be placed above another disc only when both its radius and height are strictly smaller than the disc below it:
A.radius < B.radius
AND
A.height < B.height
Each disc can be used at most once.
For example:
r = [5, 7, 3]
h = [6, 5, 4]
The discs are:
(5, 6)
(7, 5)
(3, 4)
We can stack (3, 4) below (5, 6) because:
3 < 5
4 < 6
The total height is:
4 + 6 = 10
Therefore, the maximum possible stack height is 10.
Main Concept
This problem can be viewed as a two-dimensional Longest Increasing Subsequence (LIS) problem.
Every disc has two properties:
(radius, height)
For a smaller disc to be placed above a larger disc, both dimensions must satisfy the strict ordering.
Since every disc also contributes its height to the answer, this is not an ordinary LIS problem. It is a:
Maximum-weight 2D increasing subsequence
The weight of each disc is its height.
Why Simple Sorting + DP Is Not Enough
A straightforward approach would be:
Sort the discs by radius.
Use dynamic programming to find the maximum stack height ending at each disc.
For every disc, check all previous discs.
For every disc i:
if r[j] < r[i] && h[j] < h[i]
we could calculate:
dp[i] = max(dp[i], dp[j] + h[i])
However, this requires checking every pair of discs.
For n discs, the time complexity is:
O(n²)
When:
n <= 100000
an O(n²) solution is too slow.
The DP transition needs to be optimized.
Key Observation
After sorting the discs by radius, for the current disc we need to find:
Among previously processed discs with smaller radius, what is the maximum stack height whose height is smaller than the current disc's height?
Suppose the current disc has height h.
We need:
maximum DP value for height < h
This is a prefix maximum query.
A Fenwick Tree (Binary Indexed Tree) can efficiently perform both operations:
Query the maximum DP value for a range of heights.
Update a height with a new maximum DP value.
Each operation takes:
O(log n)
Therefore, the overall solution can be reduced to:
O(n log n)
Step 1: Represent the Discs
We combine the radius and height into a single object.
static class Disc {
int radius;
int height;
Disc(int radius, int height) {
this.radius = radius;
this.height = height;
}
}
For example:
r = [5, 7, 3]
h = [6, 5, 4]
becomes:
(5, 6)
(7, 5)
(3, 4)
Step 2: Sort the Discs by Radius
We sort the discs according to their radius.
Arrays.sort(discs, (a, b) -> {
if (a.radius != b.radius) {
return Integer.compare(a.radius, b.radius);
}
return Integer.compare(a.height, b.height);
});
After sorting:
(3, 4)
(5, 6)
(7, 5)
Processing the discs in this order allows previously processed discs to represent candidates with smaller radius.
The remaining condition is:
previous height < current height
which is handled by the Fenwick Tree.
Step 3: Dynamic Programming State
Let:
dp[i]
represent the maximum total stack height for a valid sequence ending with the current disc.
For a current disc with height h:
dp = bestPreviousStack + h
where bestPreviousStack is the maximum stack height among previously processed discs whose height is strictly smaller than h.
Therefore:
dp = query(h - 1) + h
The h - 1 is important because the height comparison must be strict.
Fenwick Tree
A conventional Fenwick Tree is often used for prefix sums. Here, instead of storing sums, we store maximum values.
For each height, the Fenwick Tree maintains the maximum DP value available for the corresponding prefix.
We need two operations.
Query
Find the maximum DP value for all heights less than or equal to a given height.
Update
Store the maximum DP value associated with a particular height.
Fenwick Tree Query
private int query(int[] bit, int index) {
int max = 0;
while (index > 0) {
max = Math.max(max, bit[index]);
index -= index & -index;
}
return max;
}
Suppose the current disc has:
height = 6
We need a previous disc whose height is:
< 6
Therefore, we query:
query(bit, 5)
This returns the maximum stack height that can be formed using a previous disc with height at most 5.
Fenwick Tree Update
After calculating the DP value for a disc, we update the tree.
private void update(int[] bit, int index, int value) {
while (index < bit.length) {
bit[index] = Math.max(bit[index], value);
index += index & -index;
}
}
For example, if:
height = 6
dp = 10
we perform:
update(bit, 6, 10);
This allows future discs with larger heights to use this stack.
Handling Equal Radii
There is an important edge case involving equal radii.
Consider:
(5, 4)
(5, 6)
Although:
4 < 6
the radius condition is invalid:
5 < 5
Therefore, these two discs cannot be stacked.
If we immediately update the Fenwick Tree after processing (5, 4), (5, 6) could incorrectly use it.
To prevent this, discs with the same radius are processed as a group:
Calculate all DP values for the group.
Update the Fenwick Tree only after all DP values have been calculated.
This guarantees that discs with equal radius cannot use one another.
Complete Java Solution
class Solution {
static class Disc {
int radius;
int height;
Disc(int radius, int height) {
this.radius = radius;
this.height = height;
}
}
public int maxStackHeight(int[] r, int[] h) {
int n = r.length;
Disc[] discs = new Disc[n];
// Create disc objects
for (int i = 0; i < n; i++) {
discs[i] = new Disc(r[i], h[i]);
}
// Sort by radius
// For equal radius, sort by height
java.util.Arrays.sort(discs, (a, b) -> {
if (a.radius != b.radius) {
return Integer.compare(a.radius, b.radius);
}
return Integer.compare(a.height, b.height);
});
/*
* h[i] <= 1000 according to the constraints.
* Therefore, Fenwick Tree size can be 1001.
*/
int maxHeight = 1000;
int[] bit = new int[maxHeight + 1];
int answer = 0;
int i = 0;
while (i < n) {
int j = i;
// Find all discs having the same radius
while (j < n && discs[j].radius == discs[i].radius) {
j++;
}
/*
* First calculate DP values.
* Do not update the Fenwick Tree yet.
*/
int[] dp = new int[j - i];
for (int k = i; k < j; k++) {
int height = discs[k].height;
// Only heights strictly smaller than current height
int best = query(bit, height - 1);
dp[k - i] = best + height;
answer = Math.max(answer, dp[k - i]);
}
/*
* Update the Fenwick Tree only after processing
* all discs having the same radius.
*/
for (int k = i; k < j; k++) {
update(
bit,
discs[k].height,
dp[k - i]
);
}
i = j;
}
return answer;
}
// Maximum value for all indices <= index
private int query(int[] bit, int index) {
int max = 0;
while (index > 0) {
max = Math.max(max, bit[index]);
index -= index & -index;
}
return max;
}
// Update maximum value at the given index
private void update(int[] bit, int index, int value) {
while (index < bit.length) {
bit[index] = Math.max(bit[index], value);
index += index & -index;
}
}
}
Dry Run
Consider:
r = [5, 7, 3]
h = [6, 5, 4]
The discs are:
(5, 6)
(7, 5)
(3, 4)
After sorting by radius:
(3, 4)
(5, 6)
(7, 5)
Process (3, 4)
There is no previous disc.
Therefore:
query(3) = 0
So:
dp = 0 + 4
= 4
Update height 4 with value 4.
BIT:
height 4 → 4
Process (5, 6)
We need a previous disc with height:
< 6
So:
query(5)
The previous stack has height 4, therefore:
best = 4
Current DP value:
dp = 4 + 6
= 10
Update height 6 with 10.
The current answer is:
10
Process (7, 5)
We need a previous disc with height:
< 5
The disc (3, 4) qualifies.
Therefore:
query(4) = 4
Current DP value:
dp = 4 + 5
= 9
The maximum remains:
10
Therefore:
Answer = 10
Why Is the Answer 10?
The optimal stack is:
(5, 6)
-------
(3, 4)
-------
The total height is:
6 + 4 = 10
The disc (7, 5) cannot be placed below (5, 6) because:
7 > 5
Although:
5 < 6
the radius condition is not satisfied.
Another Example
Consider:
r = [3, 7]
h = [7, 4]
The discs are:
(3, 7)
(7, 4)
To stack (3, 7) above (7, 4):
3 < 7 ✓
7 < 4 ✗
The height condition fails.
To stack (7, 4) above (3, 7):
7 < 3 ✗
The radius condition fails.
Therefore, no two discs can be stacked.
The maximum answer is simply:
max(7, 4) = 7
Why Use a Fenwick Tree?
Without a Fenwick Tree, for every disc we would need to examine all previous discs:
for every i:
for every j < i:
check height[j] < height[i]
This produces:
O(n²)
time complexity.
For:
n = 100000
this approach is too expensive.
The Fenwick Tree allows us to perform:
Prefix Maximum Query → O(log H)
Update → O(log H)
where H is the maximum height.
This reduces the overall complexity to:
O(n log n)
Complexity Analysis
Sorting
Sorting n discs takes:
O(n log n)
Fenwick Tree Operations
Each disc performs:
One query →
O(log H)One update →
O(log H)
where H is the maximum possible height.
Since:
H <= 1000
these operations are efficient.
The overall time complexity is:
O(n log n)
Auxiliary Space
The algorithm uses:
Disc[]→O(n)dp[]→O(n)in the largest equal-radius groupFenwick Tree →
O(H)
Therefore, the auxiliary space is:
O(n)
Key Takeaways
1. Two-Dimensional Increasing Sequence
A disc can be placed above another disc only when both its radius and height are strictly smaller.
When the discs are processed from smaller to larger radius, the DP sequence follows increasing radius and increasing height.
2. Weighted Dynamic Programming
Each disc contributes its height to the result, so the objective is to maximize total height rather than simply maximize the number of discs.
3. Sorting
Sorting by radius handles one dimension of the problem. The Fenwick Tree is then used to efficiently handle the height condition.
4. Fenwick Tree
The Fenwick Tree maintains the maximum DP value for different height prefixes.
It supports:
Prefix Maximum Query → O(log H)
Update → O(log H)
5. Equal Radius Handling
Discs with equal radius cannot be stacked.
Therefore, all discs with the same radius must have their DP values calculated before any of them are inserted into the Fenwick Tree.
Final Formula
For every disc:
dp[i] =
height[i]
+ maximum dp[j]
where radius[j] < radius[i]
and height[j] < height[i]
The Fenwick Tree efficiently calculates the maximum previous dp[j].
Finally:
Answer = maximum dp[i]
This transforms the straightforward O(n²) dynamic programming solution into an efficient O(n log n) solution.
Join the conversation! Your thoughts help the community grow.