Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE coding round, got a subarray problem that looked deceptively clean but the O(n) constraint is where it gets interesting. Not sure how it went.

Questions Asked (1)

Given an integer array, compute the total sum of all 'good' subarrays, where a subarray is good if every pair of adjacent elements differs by exactly 1. The solution must run in O(n) time.

Algorithms & Data Structures

Author's notes

My first instinct was just enumerate all valid subarrays and sum them up, which is obviously not O(n).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the definition of a 'good' subarray and confirm that the sum is over all elements in all such subarrays. Then, propose an O(n) solution by identifying maximal contiguous segments where adjacent elements differ by exactly 1, and for each segment, compute the sum of all subarrays within it using a formula based on prefix sums and contributions.

Pro tip: Mention that the sum of all subarray sums can be computed by summing each element's contribution (value multiplied by the number of subarrays containing it), which simplifies the calculation and avoids explicit enumeration.

1. Clarify the problem

Ask if 'good' subarray means every adjacent pair differs by exactly 1 (absolute difference). Confirm that the total sum is the sum of all elements in all good subarrays.

2. Identify maximal good segments

Scan the array once to find maximal contiguous segments where each adjacent pair satisfies |a[i] - a[i+1]| == 1. These segments are the only places where good subarrays can exist.

3. Compute sum of all subarrays in a segment

For a segment of length L, the sum of all subarray sums can be computed in O(L) using prefix sums or by summing each element's contribution: element at index i (0-based) appears in (i+1)*(L-i) subarrays.

4. Aggregate and return

Sum the contributions from all maximal segments to get the total sum. Ensure the algorithm runs in O(n) by processing each element a constant number of times.

Key Points to Mention

Definition of 'good' subarray: adjacent elements differ by exactly 1 (absolute difference).
Maximal good segments: contiguous regions where the condition holds; any good subarray lies entirely within one such segment.
Efficient computation of sum of all subarray sums using prefix sums or element contribution formula.
Time complexity: O(n) because each element is visited once during segmentation and once during sum computation.
Space complexity: O(1) extra space if using contribution formula, or O(n) if using prefix sums (but can be optimized).
Edge cases: empty array, single element, segments of length 1 (only single-element subarrays).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.