BudiBadu Logo

Chronicle Walkway Binding

Tree Easy 6 views
Like21

The Chronicle Walkway in the city of Merislav is an enchanted promenade lined with glyph tiles. Each tile glows when paired tiles at mirrored positions emit simultaneously. Given a set of synchronized notes that describe which tiles glow together, sages want to compute the farthest distance between simultaneously glowing tiles so that visitors know how wide the reflections reach.

Each entry in notes is either:

  • a plain integer index (meaning a single tile), or
  • a pair [left, right] where left and right are themselves notes describing groups that glow at the same time.

When a plain integer appears, its glowing range is just that index. When a pair appears, its range stretches from the smallest index covered by its left part to the largest index covered by its right part. The distance contributed by a pair is therefore max_right(left) - min_left(left), max_right(right) - min_left(right), and the distance between the furthest tile on the left subtree and the furthest tile on the right subtree. The maximum distance in the entire structure is the answer.

Formally, define:

  • If node is an integer k, then min(node) = max(node) = k and diameter(node) = 0.
  • If node is [left, right], then recursively compute min, max, and diameter for left and right. Then
    min(node) = min(min(left), min(right))
    max(node) = max(max(left), max(right))
    diameter(node) = max(diameter(left), diameter(right), max(right) - min(left)).

Return diameter(notes) as an integer. The input structure may be deeply nested. Your solution must operate recursively, propagating the necessary bounds and diameter upward.

Example 1:

Input: notes = 5
Output: 0

Example 2:

Input: notes = [1, 4]
Output: 3

Example 3:

Input: notes = [[1, 3], [6, [7, 10]]]
Output: 9

Explanation: The left structure spans tiles 1..3, the right spans 6..10 (because of the nested pair). The farthest simultaneous tiles are 1 and 10 (distance 9).

Algorithm Flow

Recommendation Algorithm Flow for Chronicle Walkway Binding - Budibadu
Recommendation Algorithm Flow for Chronicle Walkway Binding - Budibadu

Best Answers

java
class Solution {
    private static class Result {
        int min, max, diameter;
        Result(int min, int max, int diameter) {
            this.min = min;
            this.max = max;
            this.diameter = diameter;
        }
    }
    
    public int chronicle_walkway_binding(Object notes) {
        return helper(notes).diameter;
    }
    
    private Result helper(Object node) {
        if (node instanceof Integer) {
            int val = (Integer) node;
            return new Result(val, val, 0);
        }
        Object[] pair = (Object[]) node;
        Result left = helper(pair[0]);
        Result right = helper(pair[1]);
        int nodeMin = Math.min(left.min, right.min);
        int nodeMax = Math.max(left.max, right.max);
        int nodeDiam = Math.max(Math.max(left.diameter, right.diameter), right.max - left.min);
        return new Result(nodeMin, nodeMax, nodeDiam);
    }
}