Maximum Height Disc Stack

Problem Overview

A disc can sit on another only when both its radius and its height are strictly smaller.

Intuition

A disc can sit on another only when both its radius and its height are strictly smaller. Sorting by radius turns the radius rule into the scan order, and sorting equal radii by descending height keeps those discs from stacking on each other. What remains is a weighted increasing subsequence on height.

Algorithm

1Pair each radius with its height.
2Sort by radius ascending, and by height descending when radii are equal.
3Compress the distinct heights into ranks for a Fenwick tree of maximums.
4For each disc in sorted order, query the best stack among strictly smaller heights.
5The candidate height is that best stack plus the current height.
6Write the candidate back at this height rank and keep the global maximum.

Example Walkthrough

Input: r = [5,7,3], h = [6,5,4]

1. Sorted by radius, the discs are (3,4), then (5,6), then (7,5).
2. (5,6) extends (3,4) because both dimensions grow, for a total of 10.
3. (7,5) cannot extend that stack because its height is not larger than 6.

Output: 10

Common Pitfalls

• Both radius and height must be strictly smaller, not merely one of them.
• Equal radii must be ordered by descending height so they do not chain.
• Query one rank below the current height so equal heights do not stack.
• Compress heights before indexing the tree; raw heights may be far larger than n.

Maximum Height Disc Stack.java

Java

// Approach: A disc stacks only on a strictly larger radius and height. Sort by
// radius ascending, and by height descending when radii match, so equal radii
// never form an increasing height chain. Then this is a weighted LIS on
// height: a Fenwick tree stores the best stack ending at each compressed
// height, and each disc extends the best strictly shorter one.
// Complexity: O(n log n) time, O(n) extra space.
import java.util.*;

class Solution {
    public int maxStackHeight(int[] r, int[] h) {
        int n = r.length;
        int[][] discs = new int[n][2];
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            discs[i][0] = r[i];
            discs[i][1] = h[i];
            heights[i] = h[i];
        }

        Arrays.sort(discs, (a, b) -> a[0] != b[0]
                ? Integer.compare(a[0], b[0])
                : Integer.compare(b[1], a[1]));
        Arrays.sort(heights);

        int m = 0;
        for (int i = 0; i < n; i++) {
            if (m == 0 || heights[i] != heights[m - 1])
                heights[m++] = heights[i];
        }

        int[] bit = new int[m + 1];
        int answer = 0;
        for (int[] disc : discs) {
            int height = disc[1];
            int rank = lowerBound(heights, m, height) + 1;
            int current = query(bit, rank - 1) + height;
            answer = Math.max(answer, current);
            update(bit, rank, current);
        }
        return answer;
    }

    private int lowerBound(int[] a, int n, int target) {
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }

    private int query(int[] bit, int index) {
        int result = 0;
        while (index > 0) {
            result = Math.max(result, bit[index]);
            index -= index & -index;
        }
        return result;
    }

    private void update(int[] bit, int index, int value) {
        while (index < bit.length) {
            bit[index] = Math.max(bit[index], value);
            index += index & -index;
        }
    }
}

Was this solution helpful?