Maximum Height Disc Stack Using Dynamic Programming and Fenwick Tree

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:

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:

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 group
Fenwick 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.

Introduction

Main Concept

Why Simple Sorting + DP Is Not Enough

Key Observation

Step 1: Represent the Discs

Step 2: Sort the Discs by Radius

Step 3: Dynamic Programming State

Fenwick Tree

Query

Update

Fenwick Tree Query

Fenwick Tree Update

Handling Equal Radii

Complete Java Solution

Dry Run

Process (3, 4)

Process (5, 6)

Process (7, 5)

Why Is the Answer 10?

Another Example

Why Use a Fenwick Tree?

Complexity Analysis

Sorting

Fenwick Tree Operations

Auxiliary Space

Key Takeaways

1. Two-Dimensional Increasing Sequence

2. Weighted Dynamic Programming

3. Sorting

4. Fenwick Tree

5. Equal Radius Handling

Final Formula

Process `(3, 4)`

Process `(5, 6)`

Process `(7, 5)`