Construct reverse sum hierarchy triangle from an array

Problem

Given an array of integers, generate successive levels where each level contains the sum of consecutive elements from the previous level. The number of elements in each level decreases by one, starting from the original array as the first level. Print the levels in reverse order, i.e., starting from the last level upwards to the first.

Examples

Example 1:

Input: [1, 2, 3, 4]
Output: 
[10]
[5, 7]
[3, 5, 7]
[1, 2, 3, 4]
Explanation:
Level 1: [1, 2, 3, 4] (Original array)
Level 2: [3, 5, 7] (Sum of consecutive pairs: 1+2, 2+3, 3+4)
Level 3: [5, 7] (Sum of consecutive pairs: 3+5, 5+7)
Level 4: [10] (Sum of consecutive pair: 5+7)
Printed in reverse order.

Solution

Method 1 - Iterative

1. Each level is derived from the previous one by summing consecutive elements.
2. This forms a hierarchy, shrinking in size at each level, until reaching one single number.
3. Reversing the levels for printing helps illustrate the progression "backward".

Approach

1. Initialisation: Start with the original array.
2. Iterative Construction: Create new levels by pairing consecutive elements from the current level.
3. Store Levels: Save all levels in a list.
4. Reverse and Print: Print levels in reverse order.

Code

Java

public class Solution {
    public void reverseLevelSumHierarchy(int[] arr) {
        List<List<Integer>> levels = new ArrayList<>();
        List<Integer> currentLevel = new ArrayList<>();
        
        // Initialize first level
        for (int num : arr) {
            currentLevel.add(num);
        }
        
        // Generate levels
        while (!currentLevel.isEmpty()) {
            levels.add(new ArrayList<>(currentLevel));
            List<Integer> nextLevel = new ArrayList<>();
            for (int i = 0; i < currentLevel.size() - 1; i++) {
                nextLevel.add(currentLevel.get(i) + currentLevel.get(i + 1));
            }
            currentLevel = nextLevel;
        }
        
        // Reverse levels and print
        for (int i = levels.size() - 1; i >= 0; i--) {
            System.out.println(levels.get(i));
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        System.out.println("Example 1:");
        sol.reverseLevelSumHierarchy(new int[]{1, 2, 3, 4});
        
        System.out.println("\nExample 2:");
        sol.reverseLevelSumHierarchy(new int[]{5, 6, 7});
    }
}

Python

class Solution:
    def reverseLevelSumHierarchy(self, arr):
        levels = []
        current_level = arr
        
        # Generate levels
        while len(current_level) > 0:
            levels.append(current_level)
            next_level = [current_level[i] + current_level[i + 1] for i in range(len(current_level) - 1)]
            current_level = next_level
        
        # Reverse levels and print
        for level in reversed(levels):
            print(level)

# Example usage
sol = Solution()
print("Example 1:")
sol.reverseLevelSumHierarchy([1, 2, 3, 4])

print("\nExample 2:")
sol.reverseLevelSumHierarchy([5, 6, 7])

Complexity

• ⏰ Time complexity: O(n^2). Summing consecutive elements for each level takes O(n) for the first level, O(n-1) for the second level, and so on. The total is approximately O(n^2).
• 🧺 Space complexity: O(n^2). Storing intermediate levels requires O(n^2) space as levels reduce in size.

Method 2 - Using recursion

In the recursive approach, instead of iteratively generating each level, you define a recursive function that computes the next level and calls itself until reaching the smallest level (a single element). The recursion builds up the hierarchy, which can then be printed in reverse.

Here is the approach:

1. Base Case: The recursion terminates when the current level has only a single element (i.e., size 1).
2. Recursion: The function repeatedly calculates the next level and calls itself, gradually reducing the size of the levels.
3. Appending: After the recursive stack returns, each level is appended to the result list to preserve the reverse order.

Code

Java

class Solution:
    def reverseLevelSumHierarchy(self, arr):
        def generateLevels(level):
            # Base case: if the current level has only one element
            if len(level) == 1:
                return [level]

            # Recursive case: compute next level and append current level to the result
            next_level = [level[i] + level[i + 1] for i in range(len(level) - 1)]
            levels = generateLevels(next_level)
            levels.append(level)
            return levels

        # Generate all levels recursively and reverse to print
        levels = generateLevels(arr)
        for level in levels:
            print(level)

# Example usage
sol = Solution()
print("Example 1:")
sol.reverseLevelSumHierarchy([1, 2, 3, 4])

print("\nExample 2:")
sol.reverseLevelSumHierarchy([5, 6, 7])

Python

public class Solution {
    public void reverseLevelSumHierarchy(int[] arr) {
        List<List<Integer>> levels = generateLevels(arr, arr.length);

        // Print levels directly
        for (List<Integer> level : levels) {
            System.out.println(level);
        }
    }

    private List<List<Integer>> generateLevels(int[] level, int n) {
        // Base case: if the current level has only one element
        List<List<Integer>> levels = new ArrayList<>();
        if (n == 1) {
            levels.add(toList(level));
            return levels;
        }

        // Compute next level: sums of consecutive pairs
        int[] nextLevel = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            nextLevel[i] = level[i] + level[i + 1];
        }

        // Recursive call to compute smaller levels
        levels = generateLevels(nextLevel, nextLevel.length);

        // Add current level in reverse order (at the end)
        levels.add(toList(level));
        return levels;
    }

    // Helper method to convert an array to list
    private List<Integer> toList(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        return list;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        System.out.println("Example 1:");
        sol.reverseLevelSumHierarchy(new int[]{1, 2, 3, 4});
        
        System.out.println("\nExample 2:");
        sol.reverseLevelSumHierarchy(new int[]{5, 6, 7});
    }
}

Complexity

• ⏰ Time complexity: O(n^2). Each level generation takes linear time (O(n) for the first level, O(n-1) for the second, etc.), summing to approximately O(n^2).
• 🧺 Space complexity: O(n^2). The recursive calls stack up in memory, with levels stored in reverse order as part of the recursion stack.