Jobs

Interviews

Discussions

Maximum Sum Circular Subarray

Medium

Amazon

1 view

Topics:

ArraysDynamic Programming

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. A subarray may only include each element of the fixed buffer nums at most once.

For example:

nums = [1,-2,3,-2] should return 3 because the subarray [3] has the maximum sum 3.
nums = [5,-3,5] should return 10 because the subarray [5,5] has the maximum sum 5 + 5 = 10.
nums = [-3,-2,-3] should return -2 because the subarray [-2] has the maximum sum -2.

Can you provide an efficient algorithm to solve this problem?

Maximum Sum Circular Subarray

Medium

Amazon

1 view

Topics:

ArraysDynamic Programming

For example:

nums = [1,-2,3,-2] should return 3 because the subarray [3] has the maximum sum 3.
nums = [5,-3,5] should return 10 because the subarray [5,5] has the maximum sum 5 + 5 = 10.
nums = [-3,-2,-3] should return -2 because the subarray [-2] has the maximum sum -2.

Can you provide an efficient algorithm to solve this problem?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the array contain negative numbers, positive numbers, and/or zeros?
What is the expected behavior if all numbers in the array are negative? Should I return 0 or the largest negative number?
What is the maximum possible length of the input array? This will help me consider potential memory limitations.
Could you clarify what you mean by 'subarray' in the context of a circular array? Does the subarray need to wrap around, or can it also be a regular contiguous subarray?
Is the input array guaranteed to be non-empty, or should I handle the case of an empty input array?

Brute Force Solution

Approach

The problem asks us to find the largest sum from a consecutive section of numbers, where the beginning and end of the list are considered touching. The brute force way means we are going to try every possible section and see which one has the biggest sum.

Here's how the algorithm would work step-by-step:

First, consider all possible regular sections: start at the beginning, take one number, and calculate its sum.
Then, take the first two numbers, then the first three, and so on, each time adding them up and remembering the largest sum we've seen so far.
Next, start at the second number, and do the same: take one, then two, then three numbers following it, calculating sums and updating the largest sum.
Repeat this process, starting at each number in the list, considering all regular sections beginning from that number.
Now, we need to consider the special 'circular' sections that wrap around from the end back to the beginning.
For example, take the last number, and combine it with the first number, then the first two numbers, and so on.
Do this for every possible wrapping section, again calculating sums and comparing to the largest sum we've found.
Finally, after checking every single possible regular and wrapping section, the largest sum we have remembered is the answer.

Code Implementation

def max_sub_array_circular_brute_force(numbers):
    max_sum = float('-inf')
    list_length = len(numbers)

    # Check all possible regular subarrays
    for start_index in range(list_length):
        current_sum = 0
        for end_index in range(start_index, list_length):
            current_sum += numbers[end_index]
            max_sum = max(max_sum, current_sum)

    # Now check all possible circular subarrays
    for start_index in range(list_length):
        current_sum = 0
        # Iterate through circular combinations
        for section_length in range(1, list_length):

            # This handles the wrap-around
            current_index = (start_index + section_length) % list_length
            current_sum += numbers[current_index]
            max_sum = max(max_sum, current_sum)

    # Account for the edge case, all negatives
    if max_sum == float('-inf'):
        max_sum = max(numbers)

    return max_sum

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the array as a potential starting point for a subarray. For each starting element, it considers all possible subarrays beginning from that element, which involves another loop that, on average, checks n/2 elements. Therefore, the total number of operations is proportional to n multiplied by n/2. This simplifies to a quadratic time complexity, O(n²).

Space Complexity

O(1) – The provided explanation describes an iterative approach where we are calculating sums and comparing them against a maximum sum seen so far. The only extra memory used is for variables to keep track of the current sum and the maximum sum, which are a fixed number of variables regardless of the input array's size N. Therefore, the auxiliary space complexity is constant and does not depend on the input size.

Optimal Solution

Approach

The problem asks for the largest possible sum from a continuous part of a list, where the list can 'wrap around'. Instead of checking every possible part, we find both the largest regular sum and the smallest regular sum, then cleverly combine them.

Here's how the algorithm would work step-by-step:

First, find the largest possible sum you can get from any continuous part of the list, treating it as a regular list (no wrapping).
Next, turn all the numbers in the list negative. Then, find the largest possible sum you can get from any continuous part of this negative list.
Turn the negative list's largest sum back into its positive equivalent. This number represents the smallest possible sum from any continuous part of the original list.
Find the total sum of all the numbers in the original list.
Subtract the smallest possible sum (found in step 3) from the total sum. This gives us the largest possible sum if we 'wrap around' the list.
Compare the largest regular sum (found in step 1) with the largest 'wrap around' sum (found in step 5). The bigger of these two is the answer.

Code Implementation

def max_sub_array_circular(numbers):

    def kadane_algorithm(nums):
        current_max = 0
        maximum_so_far = float('-inf')
        for number in nums:
            current_max = max(number, current_max + number)
            maximum_so_far = max(maximum_so_far, current_max)
        return maximum_so_far

    # Find the maximum sum in a regular subarray.
    max_sub_array_sum = kadane_algorithm(numbers)

    inverted_numbers = [-number for number in numbers]

    # Find the max sum of inverted array
    max_sum_inverted_array = kadane_algorithm(inverted_numbers)

    # Convert to smallest sum
    min_sub_array_sum = -max_sum_inverted_array

    total_array_sum = sum(numbers)

    # Calculate the max circular sum
    max_circular_sub_array_sum = total_array_sum - min_sub_array_sum

    # Compare the two maximum sums.
    return max(max_sub_array_sum, max_circular_sub_array_sum)

Big(O) Analysis

Time Complexity

O(n) – The algorithm computes the maximum subarray sum using Kadane's algorithm, which iterates through the array once. Finding the minimum subarray sum also uses a single pass through the array. Summing all the elements requires another single pass. Finally, comparing the two maximum sums is a constant-time operation. Therefore, the dominant operation is the single iteration through the array in each step, making the time complexity O(n).

Space Complexity

O(1) – The algorithm calculates maximum and minimum subarray sums and a total sum. It uses only a few constant space variables to store intermediate sums and the overall total, regardless of the input list's size (N). No auxiliary data structures like arrays or hash maps are created that scale with the input. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no subarrays to sum.
Array with a single element	Return the single element as it's the only possible subarray.
Array with all negative numbers	Return the largest negative number (least negative) as the maximum subarray sum in this case, which can be found during the min sum calculation.
Array with all zeros	Return 0 as the maximum subarray sum.
Integer overflow when summing large numbers	Use a larger data type like long to store the sum to prevent overflow.
Array with a very large positive number and a few very large negative numbers	Kadane's algorithm correctly finds the maximum sum subarray, even with large positive and negative values.
Array where the maximum subarray is the entire array	Kadane's algorithm and the circular sum logic will handle this case correctly, either with the standard max sum or total - min sum being the full array's sum.
Array where the maximum circular subarray wraps around the end and the beginning	Calculate both the standard max subarray sum and the maximum circular subarray sum (total - min subarray sum) and return the larger of the two.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the array contain negative numbers, positive numbers, and/or zeros?
What is the expected behavior if all numbers in the array are negative? Should I return 0 or the largest negative number?
What is the maximum possible length of the input array? This will help me consider potential memory limitations.
Could you clarify what you mean by 'subarray' in the context of a circular array? Does the subarray need to wrap around, or can it also be a regular contiguous subarray?
Is the input array guaranteed to be non-empty, or should I handle the case of an empty input array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider all possible regular sections: start at the beginning, take one number, and calculate its sum.
Then, take the first two numbers, then the first three, and so on, each time adding them up and remembering the largest sum we've seen so far.
Next, start at the second number, and do the same: take one, then two, then three numbers following it, calculating sums and updating the largest sum.
Repeat this process, starting at each number in the list, considering all regular sections beginning from that number.
Now, we need to consider the special 'circular' sections that wrap around from the end back to the beginning.
For example, take the last number, and combine it with the first number, then the first two numbers, and so on.
Do this for every possible wrapping section, again calculating sums and comparing to the largest sum we've found.
Finally, after checking every single possible regular and wrapping section, the largest sum we have remembered is the answer.

Code Implementation

def max_sub_array_circular_brute_force(numbers):
    max_sum = float('-inf')
    list_length = len(numbers)

    # Check all possible regular subarrays
    for start_index in range(list_length):
        current_sum = 0
        for end_index in range(start_index, list_length):
            current_sum += numbers[end_index]
            max_sum = max(max_sum, current_sum)

    # Now check all possible circular subarrays
    for start_index in range(list_length):
        current_sum = 0
        # Iterate through circular combinations
        for section_length in range(1, list_length):

            # This handles the wrap-around
            current_index = (start_index + section_length) % list_length
            current_sum += numbers[current_index]
            max_sum = max(max_sum, current_sum)

    # Account for the edge case, all negatives
    if max_sum == float('-inf'):
        max_sum = max(numbers)

    return max_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the largest possible sum you can get from any continuous part of the list, treating it as a regular list (no wrapping).
Next, turn all the numbers in the list negative. Then, find the largest possible sum you can get from any continuous part of this negative list.
Turn the negative list's largest sum back into its positive equivalent. This number represents the smallest possible sum from any continuous part of the original list.
Find the total sum of all the numbers in the original list.
Subtract the smallest possible sum (found in step 3) from the total sum. This gives us the largest possible sum if we 'wrap around' the list.
Compare the largest regular sum (found in step 1) with the largest 'wrap around' sum (found in step 5). The bigger of these two is the answer.

Code Implementation

def max_sub_array_circular(numbers):

    def kadane_algorithm(nums):
        current_max = 0
        maximum_so_far = float('-inf')
        for number in nums:
            current_max = max(number, current_max + number)
            maximum_so_far = max(maximum_so_far, current_max)
        return maximum_so_far

    # Find the maximum sum in a regular subarray.
    max_sub_array_sum = kadane_algorithm(numbers)

    inverted_numbers = [-number for number in numbers]

    # Find the max sum of inverted array
    max_sum_inverted_array = kadane_algorithm(inverted_numbers)

    # Convert to smallest sum
    min_sub_array_sum = -max_sum_inverted_array

    total_array_sum = sum(numbers)

    # Calculate the max circular sum
    max_circular_sub_array_sum = total_array_sum - min_sub_array_sum

    # Compare the two maximum sums.
    return max(max_sub_array_sum, max_circular_sub_array_sum)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no subarrays to sum.
Array with a single element	Return the single element as it's the only possible subarray.
Array with all negative numbers	Return the largest negative number (least negative) as the maximum subarray sum in this case, which can be found during the min sum calculation.
Array with all zeros	Return 0 as the maximum subarray sum.
Integer overflow when summing large numbers	Use a larger data type like long to store the sum to prevent overflow.
Array with a very large positive number and a few very large negative numbers	Kadane's algorithm correctly finds the maximum sum subarray, even with large positive and negative values.
Array where the maximum subarray is the entire array	Kadane's algorithm and the circular sum logic will handle this case correctly, either with the standard max sum or total - min sum being the full array's sum.
Array where the maximum circular subarray wraps around the end and the beginning	Calculate both the standard max subarray sum and the maximum circular subarray sum (total - min subarray sum) and return the larger of the two.