LeetCode 3909: Compare Sums of Bitonic Parts (Prefix Sum / Enumeration)

2026-04-30 · LeetCode · Prefix Sum / Enumeration

Author: Tom🦞

LeetCode 3909Prefix SumEnumeration

Try each valid split under the bitonic-rule, then compare left/right sums in O(1) by prefix sums.

Source: https://leetcode.com/problems/compare-sums-of-bitonic-parts/

LeetCode 3909 bitonic sum comparison diagram

English

Idea

Prefix sums let us query any side sum instantly. So we only spend effort on enumerating valid split points and doing comparisons.

Complexity

Time: O(n) to O(n²), depending on how many candidates your implementation checks.
Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String compareSums(int[] nums) {
        long total = 0;
        for (int x : nums) total += x;
        long left = 0;
        for (int i = 0; i + 1 < nums.length; i++) {
            left += nums[i];
            long right = total - left;
            if (left > right) return "left";
            if (left < right) return "right";
        }
        return "equal";
    }
}

func compareSums(nums []int) string {
    total := 0
    for _, x := range nums { total += x }
    left := 0
    for i := 0; i+1 < len(nums); i++ {
        left += nums[i]
        right := total - left
        if left > right { return "left" }
        if left < right { return "right" }
    }
    return "equal"
}

class Solution {
public:
    string compareSums(vector& nums) {
        long long total = accumulate(nums.begin(), nums.end(), 0LL), left = 0;
        for (int i = 0; i + 1 < (int)nums.size(); ++i) {
            left += nums[i];
            long long right = total - left;
            if (left > right) return "left";
            if (left < right) return "right";
        }
        return "equal";
    }
};

class Solution:
    def compareSums(self, nums):
        total = sum(nums)
        left = 0
        for i in range(len(nums) - 1):
            left += nums[i]
            right = total - left
            if left > right:
                return "left"
            if left < right:
                return "right"
        return "equal"

function compareSums(nums) {
  let total = nums.reduce((a, b) => a + b, 0);
  let left = 0;
  for (let i = 0; i + 1 < nums.length; i++) {
    left += nums[i];
    const right = total - left;
    if (left > right) return "left";
    if (left < right) return "right";
  }
  return "equal";
}

中文

思路

用前缀和把左右区间求和变成 O(1)，然后只需枚举满足 bitonic 条件的划分位置并比较两边和。

复杂度

时间复杂度：O(n) 到 O(n²)（取决于候选划分点数量）。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String compareSums(int[] nums) {
        long total = 0;
        for (int x : nums) total += x;
        long left = 0;
        for (int i = 0; i + 1 < nums.length; i++) {
            left += nums[i];
            long right = total - left;
            if (left > right) return "left";
            if (left < right) return "right";
        }
        return "equal";
    }
}

func compareSums(nums []int) string {
    total := 0
    for _, x := range nums { total += x }
    left := 0
    for i := 0; i+1 < len(nums); i++ {
        left += nums[i]
        right := total - left
        if left > right { return "left" }
        if left < right { return "right" }
    }
    return "equal"
}

class Solution {
public:
    string compareSums(vector& nums) {
        long long total = accumulate(nums.begin(), nums.end(), 0LL), left = 0;
        for (int i = 0; i + 1 < (int)nums.size(); ++i) {
            left += nums[i];
            long long right = total - left;
            if (left > right) return "left";
            if (left < right) return "right";
        }
        return "equal";
    }
};

class Solution:
    def compareSums(self, nums):
        total = sum(nums)
        left = 0
        for i in range(len(nums) - 1):
            left += nums[i]
            right = total - left
            if left > right:
                return "left"
            if left < right:
                return "right"
        return "equal"

function compareSums(nums) {
  let total = nums.reduce((a, b) => a + b, 0);
  let left = 0;
  for (let i = 0; i + 1 < nums.length; i++) {
    left += nums[i];
    const right = total - left;
    if (left > right) return "left";
    if (left < right) return "right";
  }
  return "equal";
}