3909. Compare Sums of Bitonic Parts

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a bitonic array nums of length n.

A bitonic array is an array that is strictly increasing up to a single peak element and then strictly decreasing. Here:

An array is strictly increasing if each element is strictly greater than its previous one (if it exists).
An array is strictly decreasing if each element is strictly smaller than its previous one (if it exists).

Your task is to split the array into two parts based on the peak element:

Ascending part: from index 0 to the peak element (inclusive).
Descending part: from the peak element to index n - 1 (inclusive).

Note that the peak element belongs to both parts.

After splitting, you need to compare the sums of the two parts and return:

0 if the sum of the ascending part is greater.
1 if the sum of the descending part is greater.
-1 if both sums are equal.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Following the described procedure step by step produces the solution.

Open in Flowchart

Intuition

The key observation is that the peak element is the point where the array stops increasing and starts decreasing. So before computing the two sums, we need to locate this peak.

A natural idea is to walk through the array from left to right. As long as the current element is greater than the previous one, we are still climbing up the ascending part. The moment we find an element that is smaller than its previous one, we have just passed the peak, and the descending part begins.

Now, how do we compute the two sums efficiently? Notice that the peak element belongs to both parts. This means:

The ascending sum covers elements from index 0 to the peak.
The descending sum covers elements from the peak to index n - 1.

Instead of computing both sums separately, we can use a clever trick. We start with two variables:

l set to nums[0], representing the running sum of the ascending part.
r set to sum(nums), representing the sum of all elements.

As we move forward and add each new element b to l (extending the ascending part), we simultaneously subtract the previous element a from r. This way, r always represents the sum of the remaining elements from the current position to the end, which is exactly the descending part once we stop at the peak.

When we reach the peak (where a > b), both l and r correctly include the peak element, since l added it on the last step and r never subtracted it. At that point, we simply compare l and r to decide the result.

Solution Approach

Solution 1: Simulation

We use two variables, l and r, to record the sums of the ascending and descending parts, respectively. Initially, l is set to the first element of the array nums[0], and r is set to the sum of all elements in the array sum(nums).

We iterate through the array using pairwise(nums), which gives us consecutive pairs (a, b) where a is the previous element and b is the current element:

If a > b, it means we have passed the peak element and entered the descending part, so we break out of the loop.
Otherwise, we are still in the ascending part. We add the current element b to l (extending the ascending sum) and subtract the previous element a from r (shrinking the trailing sum so it represents the descending part).

When the loop ends, both l and r correctly include the peak element. We then compare them:

If l == r, the two sums are equal, so we return -1.
If l > r, the ascending sum is greater, so we return 0.
Otherwise, the descending sum is greater, so we return 1.

The time complexity is O(n), where n is the length of the array, since we traverse the array at most once (and sum(nums) is also a single pass). The space complexity is O(1), as we only use a constant number of extra variables.

Example Walkthrough

Let's trace through the solution with a small bitonic array:

nums = [1, 3, 5, 4, 2]

This array increases (1 → 3 → 5) up to the peak 5, then decreases (5 → 4 → 2). The peak element is 5 at index 2.

Expected split:

Ascending part: [1, 3, 5] → sum = 9
Descending part: [5, 4, 2] → sum = 11

Since the descending sum is greater, the answer should be 1. Let's verify this with the algorithm.

Initialization:

l = nums[0] = 1 (running ascending sum)
r = sum(nums) = 1 + 3 + 5 + 4 + 2 = 15 (sum of all elements)

Iterating with pairwise(nums): pairs are (1,3), (3,5), (5,4), (4,2).

Pair `(a, b)`	Check `a > b`?	Action	`l`	`r`
start	—	initialize	`1`	`15`
`(1, 3)`	`1 > 3`? No	`l += 3`, `r -= 1`	`4`	`14`
`(3, 5)`	`3 > 5`? No	`l += 5`, `r -= 3`	`9`	`11`
`(5, 4)`	`5 > 4`? Yes	break	`9`	`11`

Why this works at the break point:

When we process (3, 5), we add the peak 5 into l, so l = 9 now correctly holds 1 + 3 + 5.
At that same step, r only subtracted 3 (the element before the peak), so it never removed the peak. Thus r = 11 correctly holds 5 + 4 + 2.
On the next pair (5, 4), since 5 > 4, we know the peak has passed, so we stop. Both sums already include the peak 5.

Final comparison:

l = 9, r = 11
l == r? No
l > r? No (9 < 11)
Otherwise → return 1

Result: 1 ✅ — matching our expected answer that the descending part has the greater sum.

This confirms the clever trick: by growing l forward and shrinking r from the front simultaneously, the peak element naturally ends up counted in both sums exactly once, all in a single O(n) pass with O(1) extra space.

Solution Implementation

1from itertools import pairwise
2
3
4class Solution:
5    def compareBitonicSums(self, nums: list[int]) -> int:
6        # left_sum begins with the first element;
7        # right_sum begins as the total of all elements.
8        left_sum = nums[0]
9        right_sum = sum(nums)
10
11        # Iterate over each adjacent pair (current, next_val).
12        for current, next_val in pairwise(nums):
13            # Stop once the sequence starts decreasing (peak reached).
14            if current > next_val:
15                break
16            # Still ascending: shift the boundary by moving
17            # next_val into the left side and removing current from the right side.
18            left_sum += next_val
19            right_sum -= current
20
21        # Both sides are equal -> return -1.
22        if left_sum == right_sum:
23            return -1
24
25        # Return 0 if the left side is larger, otherwise 1.
26        return 0 if left_sum > right_sum else 1
27

1class Solution {
2    public int compareBitonicSums(int[] nums) {
3        // ascendingSum: accumulates the non-decreasing prefix sum,
4        // initialized with the first element.
5        long ascendingSum = nums[0];
6
7        // descendingSum: starts as the total sum of all elements;
8        // elements moved into the ascending part are subtracted out,
9        // leaving the suffix (peak onward) as the descending part.
10        long descendingSum = 0;
11        for (int value : nums) {
12            descendingSum += value;
13        }
14
15        // Walk the array until the first strictly descending step.
16        // At that point nums[i - 1] is the peak; the loop has included
17        // the peak in ascendingSum and removed everything before the peak
18        // from descendingSum.
19        for (int i = 1; i < nums.length; ++i) {
20            // Stop when the sequence starts to decrease.
21            if (nums[i - 1] > nums[i]) {
22                break;
23            }
24            // Extend the ascending side with the current element.
25            ascendingSum += nums[i];
26            // Remove the previous element from the descending side.
27            descendingSum -= nums[i - 1];
28        }
29
30        // Compare the ascending and descending portion sums.
31        if (ascendingSum == descendingSum) {
32            return -1; // Both sides are equal.
33        }
34        return ascendingSum > descendingSum ? 0 : 1;
35    }
36}
37

1class Solution {
2public:
3    int compareBitonicSums(vector<int>& nums) {
4        // leftSum starts with the first element.
5        // rightSum starts as the total sum of all elements.
6        long long leftSum = nums[0];
7        long long rightSum = 0;
8
9        // Compute the total sum into rightSum.
10        for (int value : nums) {
11            rightSum += value;
12        }
13
14        // Walk through the ascending (non-decreasing) prefix of the sequence.
15        // Stop as soon as the order breaks (current element is smaller than the previous one).
16        for (int i = 1; i < static_cast<int>(nums.size()); ++i) {
17            if (nums[i - 1] > nums[i]) {
18                break;
19            }
20            // Extend the left accumulation with the current element.
21            leftSum += nums[i];
22            // Shrink the right accumulation by removing the previous element.
23            rightSum -= nums[i - 1];
24        }
25
26        // Compare the two accumulated sums.
27        if (leftSum == rightSum) {
28            return -1;          // Both sides are equal.
29        }
30        return leftSum > rightSum ? 0 : 1;  // 0 if left is larger, 1 if right is larger.
31    }
32};
33

1/**
2 * Walks along the non-decreasing (ascending) prefix of the array and compares
3 * the accumulated left sum against the remaining right sum at the stopping point.
4 *
5 * - leftSum:  sum of elements from the start up to (and including) the current index.
6 * - rightSum: sum of elements from the previous index to the end of the array.
7 *
8 * The scan stops as soon as a descent is found (nums[i - 1] > nums[i]).
9 *
10 * @param nums - The input array of numbers.
11 * @returns -1 if the two sums are equal, 0 if the left sum is greater, 1 otherwise.
12 */
13function compareBitonicSums(nums: number[]): number {
14    // leftSum begins with the first element (the start of the ascending run).
15    let leftSum: number = nums[0];
16
17    // rightSum begins as the total sum of all elements.
18    let rightSum: number = nums.reduce(
19        (accumulator, current) => accumulator + current,
20        0,
21    );
22
23    // Advance through the ascending portion of the array.
24    for (let i = 1; i < nums.length; i++) {
25        // Stop at the first descent: the ascending run has ended.
26        if (nums[i - 1] > nums[i]) {
27            break;
28        }
29
30        // Extend the left sum to include the current element.
31        leftSum += nums[i];
32
33        // Shrink the right sum by removing the previous element.
34        rightSum -= nums[i - 1];
35    }
36
37    // Equal sums are reported with -1.
38    if (leftSum === rightSum) {
39        return -1;
40    }
41
42    // 0 means the left sum dominates; 1 means the right sum dominates.
43    return leftSum > rightSum ? 0 : 1;
44}
45

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The initial computation sum(nums) requires a single pass over all elements, taking O(n) time. The subsequent for loop iterates over the pairs generated by pairwise(nums), which produces n - 1 pairs, and each iteration performs only constant-time operations (comparison, addition, subtraction). In the worst case, the loop runs through all pairs without an early break, contributing another O(n). Therefore, the overall time complexity is O(n) + O(n) = O(n).
Space Complexity: O(1). The algorithm uses only a constant number of extra variables (l, r, a, b), regardless of the input size. The pairwise(nums) call returns an iterator that yields pairs lazily rather than materializing a new list, so it does not consume additional space proportional to n. Hence, the auxiliary space usage remains constant at O(1).

Common Pitfalls

Pitfall 1: Double-counting or omitting the peak element

The most common mistake is mishandling the peak element, which belongs to both parts by definition. Many implementations split the array at the peak index and forget to include the peak in both the ascending and descending sums.

A typical buggy approach looks like this:

# WRONG: peak counted only once
peak = nums.index(max(nums))
left_sum = sum(nums[:peak + 1])   # includes peak
right_sum = sum(nums[peak + 1:])  # excludes peak!

Here the descending part wrongly starts after the peak, so the peak is missing from right_sum. The correct split must include the peak on both sides:

peak = nums.index(max(nums))
left_sum = sum(nums[:peak + 1])   # indices 0..peak
right_sum = sum(nums[peak:])      # indices peak..n-1

The reference solution avoids this elegantly: it initializes right_sum = sum(nums) and only subtracts current (never the peak) as it advances, so the peak naturally remains in both left_sum and right_sum.

Pitfall 2: Breaking on the wrong condition (`>=` instead of `>`)

Because the array is strictly increasing/decreasing, no two adjacent elements are equal. If you defensively write if current >= next_val: break, it works here, but the same habit fails on arrays that legitimately contain plateaus. More importantly, using < vs <= incorrectly can stop the loop one step too early or too late, leaving the peak excluded from left_sum. Stick with the strict comparison current > next_val that matches the problem's guarantee.

Pitfall 3: Assuming a strictly bitonic shape when the peak is at an endpoint

If the array is entirely increasing (peak at the last index) or entirely decreasing (peak at index 0), the loop boundary logic must still hold:

Entirely increasing: the break never triggers, the loop processes every pair, and left_sum ends up equal to sum(nums) while right_sum reduces to just the final (peak) element. This is correct.
Entirely decreasing: current > next_val triggers on the very first pair, so left_sum stays as nums[0] (the peak) and right_sum stays as the full sum. This is also correct.

The pitfall is "fixing" the loop with an off-by-one guard that breaks these edge cases. The given code handles both endpoints correctly without special-casing.

Pitfall 4: Integer overflow in other languages

In Python this is a non-issue thanks to arbitrary-precision integers. However, when porting to Java/C++, summing a large array can overflow a 32-bit int. Use a 64-bit type (long) for left_sum and right_sum to stay safe.

Solution / Best Practice

Initialize one running sum to the full total and shift the boundary incrementally, ensuring the peak stays in both halves automatically:

from itertools import pairwise


class Solution:
    def compareBitonicSums(self, nums: list[int]) -> int:
        left_sum = nums[0]
        right_sum = sum(nums)
        for current, next_val in pairwise(nums):
            if current > next_val:   # strict comparison matches the problem
                break
            left_sum += next_val
            right_sum -= current
        if left_sum == right_sum:
            return -1
        return 0 if left_sum > right_sum else 1

This keeps the peak shared between both parts, handles endpoint peaks gracefully, and runs in O(n) time with O(1) extra space.

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:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know