3730. Maximum Calories Burnt from Jumps 🔒

MediumGreedyArrayTwo PointersSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array heights of size n, where heights[i] represents the height of the ith block in an exercise routine.

You start on the ground (height 0) and must jump onto each block exactly once in any order.

The rules for calculating calories burned are as follows:

The calories burned for a jump from a block of height a to a block of height b is (a - b)².
The calories burned for the first jump from the ground to the chosen first block heights[i] is (0 - heights[i])².

Your task is to return the maximum total calories you can burn by selecting an optimal jumping sequence.

In other words, you need to decide the order in which to visit all the blocks so that the sum of the squared height differences between consecutive jumps (including the initial jump from the ground) is as large as possible. Each block must be visited exactly once.

Note: Once you jump onto the first block, you cannot return to the ground.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Alternating between the highest and lowest remaining blocks with two pointers maximizes squared height differences per jump.

Open in Flowchart

Intuition

The key observation is that the total calories burned is the sum of squared differences between consecutive blocks in our jumping sequence (treating the ground as a starting point with height 0). To maximize this sum, we want each jump to span as large a height difference as possible.

Squared differences grow fastest when the two values are far apart. So intuitively, we should make every jump go from a very high block to a very low block, then back to a high block, and so on. This zigzag pattern between extremes maximizes the gap at each step.

To set this up, we first sort the array. Once sorted, the smallest values sit at the left end and the largest values at the right end. We can then pair up the extremes: take the largest, then the smallest, then the next largest, then the next smallest, repeatedly bouncing between the two ends. This produces the largest possible height differences for each jump.

Concretely, starting from the ground (pre = 0), we first jump to the highest remaining block, which contributes a big (heights[r] - pre)². Then we jump down to the lowest remaining block, contributing (heights[l] - heights[r])². After this, the lowest block becomes the new pre, and we continue the same process inward using two pointers l and r moving toward the center.

This greedy "high-low-high-low" alternation guarantees that we never waste a jump on two blocks of similar height, which would yield a small squared difference. By always pairing the current extremes, we squeeze out the maximum possible contribution from every single jump.

When l and r finally meet (or the loop ends with one block left in the middle for an odd-sized array), we add the final jump from pre to that middle block to complete the sequence.

Pattern Learn more about Greedy, Two Pointers and Sorting patterns.

Solution Approach

Solution 1: Greedy + Sorting

According to the problem statement, the order of jumps affects the total calories burned. To maximize calorie consumption, we use a greedy strategy by prioritizing jumps with the largest height differences. The natural way to create these large gaps is to alternate between the highest and lowest remaining blocks, which we can do efficiently after sorting.

The specific steps are as follows:

Sort the array heights so that the smallest values are on the left and the largest values are on the right.
Initialize the variable pre = 0 to represent the height of the previous block (starting from the ground), and ans = 0 to represent the total calories burned.
Use two pointers: the left pointer l points to the beginning of the array, and the right pointer r points to the end of the array.
While l < r, do the following:
1. Calculate the calories burned from the previous block to the block pointed to by the right pointer, (heights[r] - pre)², and add it to ans.
2. Calculate the calories burned from the block pointed to by the right pointer to the block pointed to by the left pointer, (heights[l] - heights[r])², and add it to ans.
3. Update pre to the height of the block pointed to by the left pointer, i.e. pre = heights[l].
4. Move the left pointer one step to the right (l += 1) and the right pointer one step to the left (r -= 1).
Finally, calculate the calories burned from the previous block to the middle block, (heights[r] - pre)², and add it to ans. This handles the remaining middle block when the array has an odd length, or the meeting point of the two pointers.

This approach realizes the "high-low-high-low" zigzag jumping sequence: each iteration jumps up to a high block and then down to a low block, maximizing the squared difference at every step.

The time complexity is O(n × log n), where n is the length of the array heights, dominated by the sorting step. The space complexity is O(log n), accounting for the space used by sorting.

Example Walkthrough

Let's trace through the solution with a small example: heights = [1, 5, 3].

Step 1: Sort the array

After sorting, heights = [1, 3, 5]. Now the smallest value (1) is on the left and the largest (5) is on the right.

Step 2: Initialize variables

pre = 0 (we start on the ground at height 0)
ans = 0 (no calories burned yet)
l = 0 (left pointer at index 0, value 1)
r = 2 (right pointer at index 2, value 5)

Step 3: Main loop (while l < r)

Iteration 1 (l = 0, r = 2):

Jump from the ground to the highest remaining block heights[r] = 5:
- Calories: (5 - 0)² = 25
- ans = 0 + 25 = 25
Jump down to the lowest remaining block heights[l] = 1:
- Calories: (1 - 5)² = 16
- ans = 25 + 16 = 41
Update pre = heights[l] = 1
Move pointers: l = 1, r = 1

Now l < r is 1 < 1, which is false, so the loop ends.

Step 4: Handle the middle block

One block remains in the middle at index 1 (value 3). We jump from pre = 1 to this block:

Calories: (heights[r] - pre)² = (3 - 1)² = 4
ans = 41 + 4 = 45

Result

The maximum total calories burned is 45.

Verifying the jump sequence:

The chosen path is ground(0) → 5 → 1 → 3:

Jump	From	To	Calories
1	`0`	`5`	`(0-5)² = 25`
2	`5`	`1`	`(5-1)² = 16`
3	`1`	`3`	`(1-3)² = 4`
		Total	`45`

This confirms the greedy "high-low-high-low" strategy: by jumping to the extreme high (5) first, then the extreme low (1), we maximize the squared gap at each step rather than wasting jumps on blocks of similar height.

Solution Implementation

1class Solution:
2    def maxCaloriesBurnt(self, heights: list[int]) -> int:
3        # Sort the heights in ascending order so we can pick
4        # smallest and largest values alternately using two pointers.
5        heights.sort()
6
7        # `prev` stores the value placed in the previous step,
8        # used to compute the squared difference with the next pick.
9        prev = 0
10
11        # Two pointers: `left` starts at the smallest value,
12        # `right` starts at the largest value.
13        left, right = 0, len(heights) - 1
14
15        # Accumulator for the total result (sum of squared differences).
16        ans = 0
17
18        # Process values from both ends toward the middle.
19        while left < right:
20            # Add squared difference between current largest and previous pick.
21            ans += (heights[right] - prev) ** 2
22            # Add squared difference between current smallest and current largest.
23            ans += (heights[left] - heights[right]) ** 2
24            # The smallest value just placed becomes the new previous value.
25            prev = heights[left]
26            # Move both pointers inward.
27            left, right = left + 1, right - 1
28
29        # Handle the final remaining element (when length is odd,
30        # or the last `right` position after the loop).
31        ans += (heights[right] - prev) ** 2
32
33        return ans
34

1class Solution {
2    public long maxCaloriesBurnt(int[] heights) {
3        // Sort heights in ascending order so we can pair smallest with largest
4        Arrays.sort(heights);
5
6        long totalCalories = 0;
7        // 'previousLow' tracks the last small element that was consumed
8        int previousLow = 0;
9        // 'right' starts at the largest element
10        int right = heights.length - 1;
11
12        // 'left' moves up from the smallest, 'right' moves down from the largest,
13        // pairing elements from both ends until they meet
14        for (int left = 0; left < right; ++left, --right) {
15            // Add squared difference between current largest and previously consumed low
16            long diffHighToPrev = heights[right] - previousLow;
17            totalCalories += diffHighToPrev * diffHighToPrev;
18
19            // Add squared difference between current low and current high
20            long diffLowToHigh = heights[left] - heights[right];
21            totalCalories += diffLowToHigh * diffLowToHigh;
22
23            // Update the previously consumed low value
24            previousLow = heights[left];
25        }
26
27        // Handle the final remaining element (when pointers meet or the middle element)
28        long diffLast = heights[right] - previousLow;
29        totalCalories += diffLast * diffLast;
30
31        return totalCalories;
32    }
33}
34

1class Solution {
2public:
3    long long maxCaloriesBurnt(vector<int>& heights) {
4        // Sort heights in ascending order so we can pick from both ends.
5        ranges::sort(heights);
6
7        long long totalCalories = 0;          // Accumulated result (sum of squared differences).
8        int previousValue = 0;                // Tracks the last "small" value placed in the sequence.
9        int right = static_cast<int>(heights.size()) - 1;  // Right pointer at the largest element.
10
11        // Move two pointers toward each other, building a zig-zag arrangement:
12        // previousValue -> largest -> smallest -> largest -> ...
13        for (int left = 0; left < right; ++left, --right) {
14            // Difference between the current largest value and the previous small value.
15            long long diffUp = static_cast<long long>(heights[right] - previousValue);
16            totalCalories += diffUp * diffUp;
17
18            // Difference between the current smallest value and the current largest value.
19            long long diffDown = static_cast<long long>(heights[left] - heights[right]);
20            totalCalories += diffDown * diffDown;
21
22            // Update the previous small value for the next iteration.
23            previousValue = heights[left];
24        }
25
26        // Handle the remaining middle element (when pointers meet or cross).
27        long long finalDiff = static_cast<long long>(heights[right] - previousValue);
28        totalCalories += finalDiff * finalDiff;
29
30        return totalCalories;
31    }
32};
33

1/**
2 * Calculates the maximum calories burnt based on the given heights.
3 *
4 * Strategy:
5 * 1. Sort the heights in ascending order.
6 * 2. Use two pointers (left and right) starting from both ends.
7 * 3. On each step, pair the current largest remaining height with the
8 *    previous "base" value and with the current smallest remaining height,
9 *    accumulating the squared differences.
10 * 4. The previous base is then advanced to the current smallest height.
11 *
12 * @param heights - An array of height values.
13 * @returns The accumulated maximum calories burnt.
14 */
15function maxCaloriesBurnt(heights: number[]): number {
16    // Sort heights in ascending order so that we can pair extremes.
17    heights.sort((a, b) => a - b);
18
19    // Accumulated result (total calories burnt).
20    let answer: number = 0;
21
22    // The previous "base" height used as a reference for the next step.
23    let previous: number = 0;
24
25    // Two pointers: left starts at the smallest, right at the largest.
26    let left: number = 0;
27    let right: number = heights.length - 1;
28
29    // Process pairs from both ends moving toward the center.
30    while (left < right) {
31        // Square of the gap between the current largest and the previous base.
32        answer += (heights[right] - previous) ** 2;
33
34        // Square of the gap between the current smallest and largest.
35        answer += (heights[left] - heights[right]) ** 2;
36
37        // Advance the base to the current smallest height.
38        previous = heights[left];
39
40        // Move both pointers inward.
41        left++;
42        right--;
43    }
44
45    // Handle the remaining middle element (when left === right) by adding
46    // the squared gap between it and the last recorded base.
47    answer += (heights[right] - previous) ** 2;
48
49    return answer;
50}
51

Time and Space Complexity

Time complexity: O(n log n), where n is the length of the array heights. The dominant operation is heights.sort(), which takes O(n log n) time. The subsequent while loop uses two pointers (l and r) converging from both ends, performing constant-time arithmetic operations at each step, which totals O(n). Therefore, the overall time complexity is O(n log n).
Space complexity: O(log n), where n is the length of the array heights. The algorithm uses only a constant number of extra variables (pre, l, r, ans), so no additional O(n) space is allocated. However, the sorting algorithm (Timsort in Python) requires O(log n) auxiliary stack space for its recursive operations. Hence, the overall space complexity is O(log n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Mishandling the final middle element (off-by-one and odd/even length errors)

The most frequent mistake in this solution is incorrectly processing the last remaining block after the two-pointer loop terminates. The loop condition is while left < right, which means:

Odd-length arrays: When the loop ends, left == right, and there is exactly one unprocessed block in the middle. The final line ans += (heights[right] - prev) ** 2 correctly handles it.
Even-length arrays: When the loop ends, left > right (specifically left == right + 1). At this point all blocks have already been processed, but the final line ans += (heights[right] - prev) ** 2 still executes, adding a spurious extra term using a stale right index.

This silently corrupts the answer for even-length inputs.

Example trace (even length): heights = [1, 2]

After sort: [1, 2], prev = 0, left = 0, right = 1.
Loop iteration: ans += (2 - 0)² = 4, then ans += (1 - 2)² = 1, so ans = 5. Update prev = 1, left = 1, right = 0.
Loop ends (left > right).
Final line runs: ans += (heights[0] - 1)² = (1 - 1)² = 0. Here ans stays 5 only by luck because heights[0] == prev.

For heights = [3, 10]:

After sort: [3, 10], prev = 0.
Loop: ans += (10 - 0)² = 100, ans += (3 - 10)² = 49, ans = 149. prev = 3, left = 1, right = 0.
Final line: ans += (heights[0] - 3)² = (3 - 3)² = 0. Correct only because heights[right] == prev again.

The reason it appears to "work" is subtle: when the loop exits with left = right + 1, heights[right] points at the element prev was just assigned from, so the extra term is (prev - prev)² = 0. This is a fragile coincidence, not robust logic.

Solution: Make the boundary handling explicit so the intent is unambiguous and the code does not rely on a zero-valued accident.

class Solution:
    def maxCaloriesBurnt(self, heights: list[int]) -> int:
        heights.sort()
        prev = 0
        left, right = 0, len(heights) - 1
        ans = 0

        while left < right:
            ans += (heights[right] - prev) ** 2
            ans += (heights[left] - heights[right]) ** 2
            prev = heights[left]
            left, right = left + 1, right - 1

        # Only add the middle element if one truly remains (odd length).
        if left == right:
            ans += (heights[right] - prev) ** 2

        return ans

The added if left == right: guard ensures the final term is included only for odd-length arrays, eliminating reliance on the coincidental zero term.

Pitfall 2: Treating the greedy "zigzag" as provably optimal without verification

The approach assumes that the "high-low-high-low" alternation always yields the global maximum. While sorting and alternating extremes is a strong heuristic that works for many inputs, the greedy zigzag is not guaranteed to be optimal in every case for this specific objective (sum of squared consecutive differences with a fixed start at 0).

Why this is risky: The squared cost is nonlinear and the starting constraint (always begin from height 0) interacts with the ordering in non-obvious ways. The greedy choice of jumping to the largest remaining block first maximizes the initial term (heights[right] - 0)², but committing to that may not maximize the sum of all subsequent terms.

Solution: For small n, validate the greedy result against a brute-force permutation search to build confidence (or catch counterexamples):

from itertools import permutations

def brute_force(heights):
    best = 0
    for perm in permutations(heights):
        total = 0
        prev = 0
        for h in perm:
            total += (h - prev) ** 2
            prev = h
        best = max(best, total)
    return best

# Compare greedy vs brute force on random small arrays before trusting greedy.

If discrepancies appear, the problem likely requires a DP or exact search formulation for guaranteed optimality. Running this check on a range of random inputs is the safest way to confirm whether the greedy assumption holds under the problem's constraints.

Pitfall 3: Integer overflow concerns when porting to other languages

In Python, integers have arbitrary precision, so (heights[right] - prev) ** 2 never overflows. However, if this logic is translated to Java or C++, the squared differences and their accumulated sum can easily exceed the range of a 32-bit int.

Example: With n = 10^5 blocks each near 10^4, a single term reaches ~10^8, and the total sum can reach ~10^13, far beyond 2^31 - 1 ≈ 2.1 × 10^9.

Solution: Use a 64-bit type (long in Java, long long in C++) for both the per-term computation and the accumulator. In Python no action is needed, but it's worth noting explicitly to avoid bugs when sharing or migrating the algorithm.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering