What is the time complexity of Maximum Sum Circular Subarray?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Maximum Sum Circular Subarray?

This problem uses Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Maximum Sum Circular Subarray?

Insight 1: The maximum sum subarray can either be a regular subarray (not wrapping around) or a circular subarray (wrapping around). Insight 2: Kadane's Algorithm can efficiently find the maximum sum of a regular subarray. A modified Kadane's can find the minimum sum subarray.

Which companies ask LeetCode 918. Maximum Sum Circular Subarray in interviews?

This problem is frequently asked at Flipkart, Two Sigma.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Maximum Sum Circular Subarray - LeetCode 918 Solution

Q: How to solve Maximum Sum Circular Subarray?

The solution uses Kadane's Algorithm twice: once to find the maximum subarray sum (without wrapping), and once to find the minimum subarray sum. Then, it calculates the maximum circular subarray sum by subtracting the minimum subarray sum from the total array sum. Finally, it returns the larger of the two sums, handling the edge case where all numbers are negative.

Maximum Sum Circular Subarray - Complete Solution Guide

Maximum Sum Circular Subarray is LeetCode problem 918, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a circular integer array nums of length n , return the maximum possible sum of a non-empty subarray of nums . A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n] . A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j] , there does not exist i <= k1 , k2 <=

Detailed Explanation

The problem asks us to find the maximum sum of a non-empty subarray within a circular integer array. A circular array is like a regular array, but the end connects to the beginning. The crucial constraint is that each element in the original array can be included in the subarray only once. The goal is to return the largest possible sum from any valid subarray.

Solution Approach

The solution uses Kadane's Algorithm twice: once to find the maximum subarray sum (without wrapping), and once to find the minimum subarray sum. Then, it calculates the maximum circular subarray sum by subtracting the minimum subarray sum from the total array sum. Finally, it returns the larger of the two sums, handling the edge case where all numbers are negative.

Step-by-Step Algorithm

Step 1: Calculate the total sum of the array elements.
Step 2: Use Kadane's Algorithm to find the maximum subarray sum (`max_so_far`). This handles the case where the maximum subarray is a regular subarray (not wrapped).
Step 3: Use a modified Kadane's Algorithm to find the minimum subarray sum (`min_so_far`).
Step 4: Calculate the maximum circular subarray sum by subtracting the minimum subarray sum from the total array sum: `total_sum - min_so_far`.
Step 5: Compare `max_so_far` and `total_sum - min_so_far`. The larger value is potentially the answer. However we need to check the edge case.
Step 6: Handle the edge case: If `max_so_far` is negative (which often indicates all numbers in the array are non-positive), return `max_so_far`. Otherwise, return the maximum of `max_so_far` and `total_sum - min_so_far`.

Key Insights

Insight 1: The maximum sum subarray can either be a regular subarray (not wrapping around) or a circular subarray (wrapping around).
Insight 2: Kadane's Algorithm can efficiently find the maximum sum of a regular subarray. A modified Kadane's can find the minimum sum subarray.
Insight 3: The sum of a circular subarray can be expressed as the total sum of the array minus the minimum sum subarray. This provides a way to calculate the maximum sum of wrapping subarrays.
Insight 4: It is crucial to handle the edge case where all numbers in the array are negative. In this case, the maximum subarray sum is the largest (least negative) number in the array.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Divide and Conquer, Dynamic Programming, Queue, Monotonic Queue.

Companies

Asked at: Flipkart, Two Sigma.

Maximum Sum Circular Subarray | LeetCode 918

Medium

Array Divide and Conquer Dynamic Programming Queue Monotonic Queue

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total_sum = 0;
        int max_so_far = -30001;
        int current_max = -30001;
        int min_so_far = 30001;
        int current_min = 30001;

        boolean has_positive = false;

        // Using a single loop to find total_sum, max_so_far (Kadane's), and min_so_far
        for (int num : nums) {
            total_sum += num;

            // Standard Kadane's for maximum subarray sum
            current_max = Math.max(num, current_max + num);
            max_so_far = Math.max(max_so_far, current_max);

            // Kadane's for minimum subarray sum
            current_min = Math.min(num, current_min + num);
            min_so_far = Math.min(min_so_far, current_min);
        }

        // There are two cases for the maximum sum:
        // 1. The subarray is not "wrapped" around the circular array.
        //    This is the standard maximum subarray sum, which is `max_so_far`.
        // 2. The subarray is "wrapped" around.
        //    This sum is equivalent to `total_sum - min_so_far`.

        // Edge case: If all numbers are negative, `max_so_far` will be the
        // largest (least negative) number. `min_so_far` will be `total_sum`.
        // In this case, `total_sum - min_so_far` would be 0, which corresponds
        // to an empty subarray. The problem requires a non-empty subarray,
        // so the answer must be `max_so_far`.
        // This is correctly handled by checking if `max_so_far` is positive.
        // If `max_so_far` is not positive, it means either all numbers are non-positive
        // and the max is the largest element (or 0), or the structure is such
        // that the wrapped case is not better.
        // A simpler way to check this edge case is if `min_so_far == total_sum`.
        // This indicates that the minimum subarray is the entire array.
        // Thus, the wrapping subarray would be empty.

        if (max_so_far > 0) {
            return Math.max(max_so_far, total_sum - min_so_far);
        } else {
            // This handles the case where all numbers are non-positive.
            // The maximum subarray sum will be the largest number (or 0).
            return max_so_far;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 918: Maximum Sum Circular Subarray - Detailed explanation and solution approaches.

Topics

Array Divide and Conquer Dynamic Programming Queue Monotonic Queue

Companies

FlipkartTwo Sigma

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:918

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Calculate the total sum of the array elements.
2
Step 2: Use Kadane's Algorithm to find the maximum subarray sum (`max_so_far`). This handles the case where the maximum subarray is a regular subarray (not wrapped).
3
Step 3: Use a modified Kadane's Algorithm to find the minimum subarray sum (`min_so_far`).
4
Step 4: Calculate the maximum circular subarray sum by subtracting the minimum subarray sum from the total array sum: `total_sum - min_so_far`.
5
Step 5: Compare `max_so_far` and `total_sum - min_so_far`. The larger value is potentially the answer. However we need to check the edge case.
6
Step 6: Handle the edge case: If `max_so_far` is negative (which often indicates all numbers in the array are non-positive), return `max_so_far`. Otherwise, return the maximum of `max_so_far` and `total_sum - min_so_far`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the array once to calculate the total sum and then iterates again twice for Kadane's algorithm (maximum and minimum subarrays). Since the number of iterations is directly proportional to the size of the input array 'n', the time complexity is O(n). The algorithm uses a constant amount of extra space to store variables like `total_sum`, `max_so_far`, `current_max`, `min_so_far`, and `current_min`, hence the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Prefix Sum and Monotonic Queue

Calculate the prefix sum array. Use a monotonic queue to find the minimum prefix sum within a sliding window of size n-1.

Time: O(n)Space: O(n)

Trade-offs: This approach also has O(n) time complexity, but it uses O(n) extra space for the prefix sum array and monotonic queue. The Kadane's algorithm approach is preferred due to its lower space complexity.

✨

Key Insights

1Insight 1: The maximum sum subarray can either be a regular subarray (not wrapping around) or a circular subarray (wrapping around).
2Insight 2: Kadane's Algorithm can efficiently find the maximum sum of a regular subarray. A modified Kadane's can find the minimum sum subarray.
3Insight 3: The sum of a circular subarray can be expressed as the total sum of the array minus the minimum sum subarray. This provides a way to calculate the maximum sum of wrapping subarrays.
4Insight 4: It is crucial to handle the edge case where all numbers in the array are negative. In this case, the maximum subarray sum is the largest (least negative) number in the array.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Queue

FIFO structure - First In, First Out. Like a line at a store!

Edge Cases

Edge case 1: All numbers are negative or zero. In this case, the maximum subarray sum is the largest (least negative) number. Kadane's algorithm for max_so_far correctly identifies this, and the conditional `if (max_so_far > 0)` ensures that the correct value is returned. If max_so_far is not > 0 (meaning it is negative or zero), max_so_far is returned.
Edge case 2: The maximum subarray wraps around the circular array. This is handled by calculating the minimum subarray sum and subtracting it from the total sum to find the sum of the wrapping subarray.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the edge case where all numbers are negative. This results in incorrectly returning 0, corresponding to an empty subarray which isn't allowed.

✗Common mistake 2: Incorrectly applying Kadane's Algorithm for the minimum subarray sum. Need to track the minimum sum ending at the current position, not the maximum.

✗Common mistake 3: Forgetting that the wrapping subarray sum is the `total_sum - min_so_far`, and confusing it with `total_sum + min_so_far`

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Financial analysis - Identifying the period of maximum profit in a cyclical market.

🏦Real-world scenario 2: Signal processing - Finding the strongest signal within a repeating pattern.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 19, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Maximum Sum Circular Subarray"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether divide and conquer techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?