LeetCode 3730 - Maximum Calories Burnt from Jumps

LeetCode Problem 3730

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to determine the maximum total calories that can be burned while visiting every block exactly once in an arbitrary order.

We are given an integer array heights, where heights[i] represents the height of a block. We begin on the ground at height 0, and our first jump must go from the ground to one chosen block. After that, we continue jumping between blocks until every block has been visited exactly once.

The calories burned for any jump from height a to height b is:

$$(a - b)^2$$

The first jump is special only in the sense that it starts from the ground:

$$(0 - heights[i])^2$$

The objective is to find the ordering of blocks that maximizes the total sum of these squared height differences.

A key detail is that every block must be visited exactly once. This means we are effectively searching for the best permutation of the array. Since n can be as large as 10^5, trying all possible orderings is impossible. Any practical solution must scale close to linear or O(n log n) time.

The constraints also tell us that heights can be repeated, since heights[i] ranges from 1 to 10^5. Duplicate values matter because jumping between equal heights contributes 0 calories. We also know that all heights are positive, meaning the initial jump from the ground always contributes a positive amount.

Several edge cases are important to recognize upfront. If there is only one block, the answer is simply the square of its height because there are no subsequent jumps. Duplicate heights can reduce gains because transitions between equal values produce zero calories. Arrays with all identical heights require careful handling because rearranging them provides no benefit. Extremely large values also matter because squared differences may exceed 32-bit integer limits, which is why the Go signature returns int64.

Approaches

Brute Force Approach

The most direct solution is to try every possible ordering of the blocks.

For every permutation, we simulate the jumping process:

1. Compute the first jump from the ground.
2. Compute every consecutive jump between blocks.
3. Sum all calorie costs.
4. Track the maximum total.

This approach is correct because it exhaustively checks every valid sequence and therefore cannot miss the optimal arrangement.

However, it is computationally infeasible. There are n! possible permutations. Even for n = 15, this becomes far too large, and the actual constraint is 10^5. A factorial-time algorithm is completely impractical.

Key Insight for an Optimal Solution

We want to maximize:

$$(0-a_1)^2 + (a_1-a_2)^2 + (a_2-a_3)^2 + \dots$$

Since squaring amplifies large differences, we want consecutive jumps to have the largest possible height gaps.

This becomes a rearrangement problem. To maximize the sum of squared differences between adjacent values, we should place large and small heights alternately so neighboring values differ as much as possible.

The optimal structure emerges after sorting:

• Put the smallest and largest values next to each other.
• Continue alternating extremes.
• Since the starting point is 0, we should start from one of the largest heights to maximize the first jump.

Instead of explicitly constructing permutations, we can derive the optimal arrangement greedily using a deque-like strategy after sorting.

A convenient way is:

1. Sort the heights.
2. Build an alternating arrangement by repeatedly taking the smallest and largest remaining values.
3. Evaluate both possible orientations because reversing the sequence changes the first jump from the ground.
4. Return the maximum result.

This works in O(n log n) time because sorting dominates the complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! · n)	O(n)	Tries every permutation and computes total calories
Optimal	O(n log n)	O(n)	Sorts and greedily builds a high-difference arrangement

Algorithm Walkthrough

Optimal Algorithm

1. Sort the heights array

Sorting gives us direct access to the smallest and largest remaining elements. Since large adjacent differences are desirable, ordering extremes becomes easy after sorting. 2. Construct an alternating sequence

Use two pointers:

• left = 0
• right = n - 1

Repeatedly place elements in the order:

• smallest remaining
• largest remaining

This creates a zigzag arrangement where neighboring heights tend to differ greatly. 3. Check both orientations

Because the first jump starts from height 0, sequence direction matters.

For example:

[1, 9, 2, 8]

and

[8, 2, 9, 1]

have identical internal transitions but different first jumps.

Evaluate both directions and keep the larger total. 4. Compute total calories

For a sequence:

a0, a1, a2, ...

Calculate:

$$a_0^2 + (a_0-a_1)^2 + (a_1-a_2)^2 + \dots$$ 5. Return the maximum

The larger of the two evaluated totals is the answer.

Why it works

The essential property is that squared differences reward large gaps disproportionately. Pairing very large values with very small values maximizes local gains, and alternating extremes globally maximizes adjacent distance. Since the only asymmetry comes from starting at ground height 0, evaluating both directions guarantees we choose the orientation with the best initial jump.

Python Solution

from typing import List

class Solution:
    def maxCaloriesBurnt(self, heights: List[int]) -> int:
        heights.sort()

        arrangement = []
        left, right = 0, len(heights) - 1

        while left <= right:
            if left == right:
                arrangement.append(heights[left])
            else:
                arrangement.append(heights[left])
                arrangement.append(heights[right])

            left += 1
            right -= 1

        def calculate(sequence: List[int]) -> int:
            total = sequence[0] * sequence[0]

            for i in range(1, len(sequence)):
                diff = sequence[i - 1] - sequence[i]
                total += diff * diff

            return total

        return max(
            calculate(arrangement),
            calculate(arrangement[::-1])
        )

The implementation begins by sorting the array so that we can efficiently access the smallest and largest remaining values. Using two pointers, we greedily build an arrangement that alternates between extremes, which tends to maximize adjacent differences.

Once the candidate arrangement is constructed, we define a helper function calculate to evaluate total calories for any sequence. The function starts with the square of the first element because the jump begins from ground level 0. Then it iterates through adjacent pairs and accumulates squared differences.

Finally, we evaluate both the arrangement and its reverse. Since the first jump depends on sequence direction, testing both guarantees we do not miss the better orientation.

Go Solution

package main

import "sort"

func maxCaloriesBurnt(heights []int) int64 {
	sort.Ints(heights)

	arrangement := make([]int, 0, len(heights))
	left, right := 0, len(heights)-1

	for left <= right {
		if left == right {
			arrangement = append(arrangement, heights[left])
		} else {
			arrangement = append(arrangement, heights[left])
			arrangement = append(arrangement, heights[right])
		}

		left++
		right--
	}

	calculate := func(sequence []int) int64 {
		first := int64(sequence[0])
		total := first * first

		for i := 1; i < len(sequence); i++ {
			diff := int64(sequence[i-1] - sequence[i])
			total += diff * diff
		}

		return total
	}

	reversed := make([]int, len(arrangement))
	for i := range arrangement {
		reversed[i] = arrangement[len(arrangement)-1-i]
	}

	ans1 := calculate(arrangement)
	ans2 := calculate(reversed)

	if ans1 > ans2 {
		return ans1
	}

	return ans2
}

The Go implementation mirrors the Python logic closely. The primary difference is integer handling. Since squared values can become large, int64 is used for all calorie calculations to avoid overflow. Slice allocation is explicit, and reversing the arrangement requires constructing a separate slice because Go does not provide built-in reverse slicing like Python's [::-1].

Worked Examples

Example 1

Input:

heights = [1,7,9]

After sorting:

[1,7,9]

Construct arrangement:

Step	Left	Right	Arrangement
Start	0	2	[]
Add min/max	1	1	[1, 9]
Add middle	2	0	[1, 9, 7]

Evaluate forward:

Jump	Calculation	Calories
Ground → 1	1²	1
1 → 9	(1 - 9)²	64
9 → 7	(9 - 7)²	4
Total		69

Evaluate reverse:

Sequence:

[7,9,1]

Jump	Calculation	Calories
Ground → 7	7²	49
7 → 9	(7 - 9)²	4
9 → 1	(9 - 1)²	64
Total		117

However, the true optimal ordering is:

[9,1,7]

Calories:

81 + 64 + 36 = 181

This reveals an important issue: a simple alternating construction alone is insufficient. We need a stronger greedy formulation.

Correct Insight

We can reformulate:

$$(a-b)^2 = a^2 + b^2 - 2ab$$

The sum of all squared terms becomes fixed except for adjacency interactions. Therefore, maximizing calories becomes equivalent to minimizing adjacent products.

This is exactly the classic arrangement problem solved by placing numbers in a pendulum order after sorting.

Revised Optimal Algorithm

1. Sort the heights.
2. Build a deque-like arrangement:

• Alternate placing values at front and back.

3. Evaluate both orientations.
4. Compute total calories.
5. Return the maximum.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maxCaloriesBurnt(self, heights: List[int]) -> int:
        heights.sort()

        arrangement = deque()

        for i, value in enumerate(heights):
            if i % 2 == 0:
                arrangement.appendleft(value)
            else:
                arrangement.append(value)

        arrangement = list(arrangement)

        def calculate(sequence: List[int]) -> int:
            total = sequence[0] * sequence[0]

            for i in range(1, len(sequence)):
                diff = sequence[i - 1] - sequence[i]
                total += diff * diff

            return total

        return max(
            calculate(arrangement),
            calculate(arrangement[::-1])
        )

Go Solution

package main

import "sort"

func maxCaloriesBurnt(heights []int) int64 {
	sort.Ints(heights)

	arrangement := make([]int, 0, len(heights))

	for i, value := range heights {
		if i%2 == 0 {
			arrangement = append([]int{value}, arrangement...)
		} else {
			arrangement = append(arrangement, value)
		}
	}

	calculate := func(sequence []int) int64 {
		first := int64(sequence[0])
		total := first * first

		for i := 1; i < len(sequence); i++ {
			diff := int64(sequence[i-1] - sequence[i])
			total += diff * diff
		}

		return total
	}

	reversed := make([]int, len(arrangement))
	for i := range arrangement {
		reversed[i] = arrangement[len(arrangement)-1-i]
	}

	ans1 := calculate(arrangement)
	ans2 := calculate(reversed)

	if ans1 > ans2 {
		return ans1
	}

	return ans2
}

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates runtime
Space	O(n)	Extra arrangement storage

The dominant operation is sorting, which requires O(n log n) time. Building the arrangement and computing calories both take linear time. Additional space is used to store the reordered sequence.

Test Cases

solution = Solution()

assert solution.maxCaloriesBurnt([1, 7, 9]) == 181  # provided example
assert solution.maxCaloriesBurnt([5, 2, 4]) == 38  # provided example
assert solution.maxCaloriesBurnt([3, 3]) == 9  # duplicate heights
assert solution.maxCaloriesBurnt([5]) == 25  # single element
assert solution.maxCaloriesBurnt([1, 2]) == 5  # simple pair
assert solution.maxCaloriesBurnt([10, 1, 10]) == 262  # repeated extremes
assert solution.maxCaloriesBurnt([4, 4, 4, 4]) == 16  # all equal
assert solution.maxCaloriesBurnt([1, 2, 3, 4, 5]) > 0  # increasing order
assert solution.maxCaloriesBurnt([100000]) == 10000000000  # max value

Test	Why
[1,7,9]	Validates provided example
[5,2,4]	Tests small unsorted input
[3,3]	Confirms duplicate handling
[5]	Minimum size edge case
[1,2]	Smallest multi-element input
[10,1,10]	Repeated extreme values
[4,4,4,4]	All identical values
[1,2,3,4,5]	General increasing input
[100000]	Maximum value boundary

Edge Cases

Single Element Array

If n = 1, there are no jumps between blocks. The answer is simply the square of the block height from the initial ground jump. A naive implementation may accidentally assume at least one transition exists and index out of bounds. The implementation handles this naturally because the calculation loop starts at index 1.

Duplicate Heights

Repeated values can produce zero calorie jumps. For example:

[3,3]

The transition contributes:

$$(3-3)^2 = 0$$

Some greedy approaches may assume distinct values and fail to handle duplicates correctly. Since the algorithm only relies on ordering after sorting, repeated values work naturally.

Very Large Heights

With values up to 10^5, squaring differences can produce values up to:

$$(10^5)^2 = 10^{10}$$

Summing many such terms can exceed 32-bit integer range. The Go implementation explicitly uses int64 to avoid overflow, while Python integers automatically expand as needed.