Start practising

Kadane's Algo - Circular Array - No Extra Space

Hard Arrays & Hashing Kadane's Algorithm Original on GeeksforGeeks

Kadane's Algo - Circular Array - No Extra Space is a hard arrays & hashing problem solved with the kadane's algorithm pattern. The best approach, optimal (max kadane vs total minus min kadane), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

The array is circular: after the last element comes the first one again. Find the largest sum of a non-empty contiguous subarray, where a subarray may wrap around the end. Each element can be used at most once.

Solve it without building a doubled copy of the array.

Examples

Example 1

Input
arr = [8, -8, 9, -9, 10, -11, 12]
Output
22
Why
Wrapping around: [12, 8, -8, 9, -9, 10] sums to 22.

Example 2

Input
arr = [-2, -5, -1]
Output
-1
Why
All negative: the answer is the largest element, not the wrap case.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i] <= 10^4

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute forceO(n²)O(1)
Optimal (max Kadane vs total minus min Kadane)O(n)O(1)

1Brute force

TimeO(n²)
SpaceO(1)

For every start index, extend up to n elements using modulo indexing, keeping the best sum.

  1. For each start i, sum arr[(i + len) % n] for len = 0..n - 1.
  2. Track the maximum.
Java
class Solution {
    public int circularSubarraySum(int[] arr) {
        int n = arr.length, best = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int len = 0; len < n; len++) {
                sum += arr[(i + len) % n];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

2Optimal (max Kadane vs total minus min Kadane)

TimeO(n)One pass tracking both Kadane runs.
SpaceO(1)

The answer either does not wrap (plain Kadane max) or wraps. A wrapping subarray is everything except a contiguous middle block, so its best sum is total - minSubarraySum. Take the larger, unless every number is negative: then the wrap case would pick an empty array, so return the plain max.

  1. In one pass compute total, the max subarray sum and the min subarray sum.
  2. If maxSum < 0, return maxSum (all negative).
  3. Return max(maxSum, total - minSum).
Java
class Solution {
    public int circularSubarraySum(int[] arr) {
        int total = 0;
        int curMax = 0, maxSum = Integer.MIN_VALUE;
        int curMin = 0, minSum = Integer.MAX_VALUE;
        for (int x : arr) {
            total += x;
            curMax = Math.max(x, curMax + x);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(x, curMin + x);
            minSum = Math.min(minSum, curMin);
        }
        if (maxSum < 0) return maxSum;
        return Math.max(maxSum, total - minSum);
    }
}

Edge cases to test

  • All negative numbers (total - minSum would be 0, which is an empty subarray)
  • The best subarray does not wrap

Hints

Hint 1

A wrapping subarray leaves out one contiguous middle part. Which middle part should you leave out?

Hint 2

Answer = max(normal Kadane max, total - minimum subarray sum).

FAQ

What is the best time complexity for Kadane's Algo - Circular Array - No Extra Space?

Optimal (max Kadane vs total minus min Kadane) runs in O(n) time and O(1) extra space. One pass tracking both Kadane runs.

Which pattern does Kadane's Algo - Circular Array - No Extra Space use?

It is a arrays & hashing problem that uses the kadane's algorithm pattern. Other problems with the same pattern: Kadane's Algorithm - Simple, Find minimum subarray sum.

Is there a brute force solution for Kadane's Algo - Circular Array - No Extra Space?

Yes. Brute force takes O(n²) time and O(1) space. For every start index, extend up to n elements using modulo indexing, keeping the best sum.

Which edge cases should I test for Kadane's Algo - Circular Array - No Extra Space?

All negative numbers (total - minSum would be 0, which is an empty subarray); The best subarray does not wrap.