Skip to content

3909. Compare Sums of Bitonic Parts

Description

You are given a bitonic array nums of length n.

Split the array into two parts:

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

The peak element belongs to both parts.

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.

Notes:

  • A bitonic array is an array that is strictly increasing up to a single peak element and then strictly decreasing.
  • An array is said to be strictly increasing if each element is strictly greater than its previous one (if exists).
  • An array is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

 

Example 1:

Input: nums = [1,3,2,1]

Output: 1

Explanation:

  • Peak element is nums[1] = 3
  • Ascending part = [1, 3], sum is 1 + 3 = 4
  • Descending part = [3, 2, 1], sum is 3 + 2 + 1 = 6
  • Since the descending part has a larger sum, return 1.

Example 2:

Input: nums = [2,4,5,2]

Output: 0

Explanation:

  • Peak element is nums[2] = 5
  • Ascending part = [2, 4, 5], sum is 2 + 4 + 5 = 11
  • Descending part = [5, 2], sum is 5 + 2 = 7
  • Since the ascending part has a larger sum, return 0.

Example 3:

Input: nums = [1,2,4,3]

Output: -1

Explanation:

  • Peak element is nums[2] = 4
  • Ascending part = [1, 2, 4], sum is 1 + 2 + 4 = 7
  • Descending part = [4, 3], sum is 4 + 3 = 7
  • Since both parts have equal sums, return -1.

 

Constraints:

  • 3 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums is a bitonic array.

Solutions

Solution 1: Simulation

Thinking

The array is already bitonic, so the peak is unique and we need not re-check the rise/fall shape. Finding the peak and summing both sides separately takes two scans; one scan can split the sums at the same time.

Let \(\textit{l}\) be the rising-part sum and \(\textit{r}\) start as the total sum. While adjacent pairs still increase, fold the new value into \(\textit{l}\) and drop the previous value from \(\textit{r}\) (the peak stays on the right). Stop at the first descent.

Comparing \(\textit{l}\) and \(\textit{r}\) then tells which side is larger.

We use two variables, \(\textit{l}\) and \(\textit{r}\), to record the sums of the ascending and descending parts, respectively. Initially, \(\textit{l}\) is set to the first element of the array, and \(\textit{r}\) is set to the sum of all elements in the array.

We iterate from the second element of the array until we find the peak element. During the iteration, we add the current element to \(\textit{l}\) and subtract the previous element from \(\textit{r}\).

Finally, we compare the values of \(\textit{l}\) and \(\textit{r}\) and return the corresponding result.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def compareBitonicSums(self, nums: list[int]) -> int:
        l, r = nums[0], sum(nums)
        for a, b in pairwise(nums):
            if a > b:
                break
            l += b
            r -= a
        if l == r:
            return -1
        return 0 if l > r else 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int compareBitonicSums(int[] nums) {
        long l = nums[0], r = 0;
        for (int x : nums) {
            r += x;
        }
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i - 1] > nums[i]) {
                break;
            }
            l += nums[i];
            r -= nums[i - 1];
        }
        if (l == r) {
            return -1;
        }
        return l > r ? 0 : 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int compareBitonicSums(vector<int>& nums) {
        long long l = nums[0], r = 0;
        for (int x : nums) {
            r += x;
        }
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i - 1] > nums[i]) {
                break;
            }
            l += nums[i];
            r -= nums[i - 1];
        }
        if (l == r) {
            return -1;
        }
        return l > r ? 0 : 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func compareBitonicSums(nums []int) int {
    var l, r int64
    l = int64(nums[0])
    r = 0
    for _, x := range nums {
        r += int64(x)
    }
    for i := 1; i < len(nums); i++ {
        if nums[i-1] > nums[i] {
            break
        }
        l += int64(nums[i])
        r -= int64(nums[i-1])
    }
    if l == r {
        return -1
    }
    if l > r {
        return 0
    }
    return 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function compareBitonicSums(nums: number[]): number {
    let l: number = nums[0];
    let r: number = nums.reduce((acc, curr) => acc + curr, 0);

    for (let i = 1; i < nums.length; i++) {
        if (nums[i - 1] > nums[i]) {
            break;
        }
        l += nums[i];
        r -= nums[i - 1];
    }

    if (l === r) {
        return -1;
    }
    return l > r ? 0 : 1;
}

Comments