FastPrepSum of Unit-Step Subarrays

Sum of Unit-Step Subarrays

Google logoGoogle● MediumFULLTIMENEW GRADONSITE INTERVIEW
Learn

Problem statement

A nonempty contiguous subarray is good when it is a singleton, or when every adjacent difference is the same signed value: all +1 or all -1. A change of direction makes the subarray invalid.

Return the sum of the elements of every good subarray, counting each subarray once. Equal values at different indices remain different occurrences. Return 0 for an empty array. Use O(n) time, where n = nums.length.

Function

sumGoodSubarrays(nums: int[]) → long

Examples

Example 1

nums = [3,5,6,7,6]return = 82

The source-listed subarrays are [3], [5], [6], [7], [6], [5,6], [6,7], [5,6,7] and [7,6]. Their element sums total82.

Example 2

nums = [1,2,1]return = 10

The singletons total4 and the two length-2 subarrays each sum to3. The direction-changing length-3 subarray is invalid.

Example 3

nums = [-1,0,1]return = 0

Every subarray is good, and its signed element sum contributions cancel.

Constraints

  • 0 <= nums.length <= 10^4.
  • -10^4 <= nums[i] <= 10^4.
  • Return the exact signed 64-bit sum, without a modulus.

More Google problems

See Google hiring insights
public long sumGoodSubarrays(int[] nums) {
    // Write your code here.
}
nums[3,5,6,7,6]
expected82
Checking account…