Prompt and setting
Given an integer array of length n whose end connects to its beginning, a contiguous subarray may wrap around but cannot use a position twice. Return the maximum sum of a non-empty subarray. Interviewers often ask candidates to derive the circular variant from Kadane's algorithm and explain why an all-negative array cannot blindly use total - minSum.
What the interviewer tests
- Splitting the answer into non-wrapping and wrapping ranges.
- Using the complement between maximum and minimum subarray sums instead of duplicating the array.
- Preserving the non-empty constraint for all-negative, one-element, and bounded-integer inputs.
Clarifying questions before answering
- Must the subarray be non-empty? Yes, so an all-negative input returns its largest negative value.
- May a position be used twice? No; a wrapping range is the complement of one non-empty middle range.
- Do we return only the sum or also boundaries? This prompt asks for the sum; boundaries need extra index bookkeeping and a circular representation.
30-second answer framework
I split the answer into two cases. A non-wrapping range is the ordinary maximum subarray sum. A wrapping range equals the total sum minus a non-empty minimum subarray sum. One pass maintains the maximum, minimum, and total sums. If the minimum range is the entire array, the complement is empty, so I return the ordinary maximum instead. The algorithm is O(n) time and O(1) extra space.
Step-by-step deep dive
1. Derive the two cases
Kadane's algorithm finds the best non-wrapping range. A wrapping range consists of a suffix and prefix; its complement is one non-empty contiguous middle range, so its sum is total - minSubarray. Taking the larger of these candidates covers every legal range.
2. Maintain Kadane invariants
At value x, the ordinary state stores the best sum ending at the current position; the minimum state stores the smallest sum ending there. Update each from the previous current state, then update the global extrema. Initialize global maximum to negative infinity and minimum to positive infinity so a one-element negative array is not treated as empty.
3. Handle all-negative input
When every value is negative, the minimum subarray is the entire array and total - minSubarray is zero, which represents an empty range and violates the prompt. Return the ordinary maximum whenever the best sum is negative. Tracking whether the minimum range covers the whole array is another valid implementation, but the sign check is simpler.
4. Code and complexity
from typing import List
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = 0
current_max = current_min = 0
best_max = float("-inf")
best_min = float("inf")
for value in nums:
total += value
current_max = max(value, current_max + value)
best_max = max(best_max, current_max)
current_min = min(value, current_min + value)
best_min = min(best_min, current_min)
if best_max < 0:
return int(best_max)
return int(max(best_max, total - best_min))Every element is visited once: O(n) time and O(1) extra space. Use a wider integer type when the language's machine integer may overflow for the total or intermediate sums.
5. Counterexamples and verification
[5,-3,5] has a wrapping answer of 5 + 5 = 10. [-3,-2,-3] must return -2, not zero. For [1,-2,3,-2], the ordinary answer is 3 and the wrapping candidate cannot exceed it. Tests should also cover one element, all-positive input, a range equivalent to the whole circular array, and sums near the integer limit.
High-quality sample answer
“I first separate ranges that cross the boundary from those that do not. The non-wrapping case is Kadane's maximum. A wrapping range is the total array sum minus a non-empty minimum middle range, so I maintain maximum and minimum Kadane states in one pass. If every value is negative, the minimum range is the whole array and its complement is empty, so I return the ordinary maximum. This is O(n) time and O(1) space, with tests for one value, all negatives, wrapping positives, and integer limits.”
Common mistakes
- Run ordinary Kadane on a duplicated array → a position may be used twice → bound the window or derive the complement case.
- Always return
total - minSum→ all-negative input produces the empty range zero → handle the negative-best branch first. - Allow an empty minimum range → the complement formula loses the non-empty constraint → start minimum Kadane from a real element.
- State O(n) without invariants → coverage of boundary cases is unproven → define both range cases and every state.
Follow-up questions and responses
How would you return the start and end positions?
Record boundaries for both maximum and minimum states. A wrapping answer is the minimum range's complement, represented as [minEnd+1,n-1] and [0,minStart-1]; define whether the API returns two linear pieces or a circular start and length.
How would the code change if empty subarrays were allowed?
The answer is at least zero, so the current sum may reset to zero. That changes the all-negative semantics; confirm the prompt before using an empty-allowed Kadane variant.
Can you update the answer in O(1) for a dynamic stream?
Appending at one end can maintain prefix, suffix, and summary values, but deleting an arbitrary old element invalidates extrema. A segment tree or block summaries may be needed. Clarify update direction, query rate, and whether approximation is allowed.
What if the subarray must have exactly length k?
The complement formula no longer applies because the complement length is constrained. Treat the array as a length-2n sequence, maintain length-k windows with prefix sums or a deque, and cap the window at n; complexity depends on the query pattern.