How to Solve: Maximum Subarray (Kadane’s Algorithm) – Complete Guide for FAANG Interviews

How to Solve: Maximum Subarray (Kadane’s Algorithm) – Complete Guide for FAANG Interviews

? Introduction

"This single algorithm appears in 1 out of every 3 onsite interviews—master Kadane’s, and you instantly prove you can optimize dynamic problems in linear time. Miss it, and you risk failing a question that’s easier than it looks."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Kadane’s Algorithm, ensure you understand: 1. Prefix Sums – How to compute cumulative sums of an array. 2. Dynamic Programming (DP) Basics – The concept of storing intermediate results to avoid recomputation. 3. Sliding Window (Optional but Helpful) – Useful for follow-up problems like "Maximum Subarray of Size K."

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Use this repeatable checklist for every Maximum Subarray problem:

1. Clarify the Problem
2. Ask: "Can the subarray be empty?" (Default: No, unless specified.)
3. Ask: "What if all numbers are negative?" (Return the least negative or 0?)

4. Ask: "Is the array circular?" (If yes, handle wrap-around cases.)

5. Initialize Variables

6. max_current = nums[0] (Tracks max subarray ending at current index).

7. max_global = nums[0] (Tracks overall max subarray found so far).

8. Iterate Through the Array

9. For each num in nums[1:]:

   • max_current = max(num, max_current + num) (Decide: Start new subarray or extend previous?)
   • max_global = max(max_global, max_current) (Update global max if current is better).

10. Handle Edge Cases

11. If all numbers are negative, return max(nums) (unless empty subarrays are allowed).

12. If the array is empty, return 0 or raise an error (clarify with interviewer).

13. Follow-Up Questions (If Time Permits)

14. "What if we need the indices of the subarray?" → Track start/end indices.
15. "What if the array is circular?" → Solve twice (normal + inverted array).

16. "What if we need the maximum product subarray?" → Track min/max products (handles negatives).

17. Optimize for Space (If Needed)

18. Kadane’s is already O(1) space. If asked to reduce further, note that it’s already optimal.

19. Test with Examples

20. Test with:
    • All positive numbers ([1,2,3] → 6).
    • All negative numbers ([-1,-2,-3] → -1).
    • Mixed numbers ([-2,1,-3,4,-1,2,1,-5,4] → 6).
    • Single element ([5] → 5).

? WORKED EXAMPLES

Example 1 – Basic: Maximum Subarray (LeetCode 53)

Problem: Given an integer array nums, find the contiguous subarray with the largest sum.

Thought Process: 1. Clarify: Subarray must be contiguous. Empty subarrays not allowed. 2. Initialize: max_current = max_global = nums[0]. 3. Iterate:
- For i=1, nums[1] = 1 → max_current = max(1, -2 + 1) = 1 → max_global = max(-2, 1) = 1.
- For i=2, nums[2] = -3 → max_current = max(-3, 1 + -3) = -2 → max_global = max(1, -2) = 1.
- For i=3, nums[3] = 4 → max_current = max(4, -2 + 4) = 4 → max_global = max(1, 4) = 4.
- Continue until end. 4. Result: max_global = 6 (subarray [4,-1,2,1]).

Code (Python):

def maxSubArray(nums):

    max_current = max_global = nums[0]

    for num in nums[1:]:

        max_current = max(num, max_current + num)

        max_global = max(max_global, max_current)

    return max_global

Time Complexity: O(n) (single pass). Space Complexity: O(1) (constant extra space).

Why This Works: - At each step, we decide whether to start a new subarray or extend the previous one. - max_current tracks the best subarray ending at the current index. - max_global ensures we never lose the best subarray found so far.

Example 2 – Medium: Maximum Subarray with Indices

Problem: Return the start and end indices of the maximum subarray.

Thought Process: 1. Clarify: Need indices, not just the sum. 2. Initialize:
- max_current = max_global = nums[0]
- start = end = 0
- temp_start = 0 (tracks potential new subarray start) 3. Iterate:
- If max_current + num < num, reset temp_start to current index.
- Update max_current and max_global as before.
- If max_global updates, set start = temp_start and end = current_index.

Code (Python):

def maxSubArrayWithIndices(nums):

    max_current = max_global = nums[0]

    start = end = 0

    temp_start = 0


    for i in range(1, len(nums)):

        if nums[i] > max_current + nums[i]:

            max_current = nums[i]

            temp_start = i

        else:

            max_current += nums[i]


        if max_current > max_global:

            max_global = max_current

            start = temp_start

            end = i


    return (start, end, max_global)

Example: nums = [-2,1,-3,4,-1,2,1,-5,4] → Returns (3, 6, 6) (subarray [4,-1,2,1]).

Why This Works: - We track temp_start to know when a new subarray begins. - When max_global updates, we record the new start and end.

Example 3 – Hard/Follow-Up: Maximum Circular Subarray (LeetCode 918)

Problem: Given a circular array, find the maximum subarray sum.

Thought Process: 1. Clarify: The array is circular (last element connects to first). 2. Key Insight:
- The max subarray is either:
- Normal (non-circular, solved with Kadane’s).
- Circular (wraps around, e.g., [5,-3,5] → 5 + 5 = 10). 3. Approach:
- Compute normal max (Kadane’s).
- Compute total sum of array.
- Compute min subarray (inverted Kadane’s).
- Circular max = total_sum - min_subarray (if min_subarray != total_sum).
- Return max(normal_max, circular_max).

Code (Python):

def maxSubarrayCircular(nums):

    total = sum(nums)


    # Normal Kadane's (max subarray)

    max_normal = current_max = nums[0]

    for num in nums[1:]:

        current_max = max(num, current_max + num)

        max_normal = max(max_normal, current_max)


    # Inverted Kadane's (min subarray)

    min_subarray = current_min = nums[0]

    for num in nums[1:]:

        current_min = min(num, current_min + num)

        min_subarray = min(min_subarray, current_min)


    # Edge case: All numbers are negative

    if max_normal < 0:

        return max_normal


    # Circular max = total - min_subarray

    circular_max = total - min_subarray

    return max(max_normal, circular_max)

Example: nums = [5,-3,5] → - Normal max = 7 ([5,-3,5]). - Min subarray = -3. - Circular max = 10 - (-3) = 13 (but 10 is total sum, so 10 - (-3) = 13 is incorrect; actual circular max is 5 + 5 = 10). - Correction: Circular max = total - min_subarray = 7 - (-3) = 10. - Final answer = max(7, 10) = 10.

Why This Works: - The circular max is the total sum minus the min subarray (since the min subarray is the "gap" we exclude). - If all numbers are negative, the normal max is the answer (no circular benefit).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Kadane’s Algorithm is your go-to for maximum subarray problems in linear time. Here’s the playbook:

1. Clarify: Subarray must be contiguous. Empty subarrays? All negatives?
2. Initialize: max_current and max_global to the first element.
3. Iterate: For each number, decide: start new subarray or extend previous?
4. Update: max_global if max_current is better.
5. Edge Cases: All negatives? Circular array? Track indices if needed.
6. Follow-Ups: Circular? Product? Track min/max for negatives.

Test with [1,2,3], [-1,-2,-3], and [-2,1,-3,4,-1,2,1,-5,4]. If you can code this in 5 minutes, you’re golden. Now go crush that interview!

? Final Notes

• Practice Variations:
• LeetCode 53 (Max Subarray)
• LeetCode 918 (Circular Subarray)
• LeetCode 152 (Max Product Subarray)
• Time Yourself: Aim for <5 minutes for the basic problem.
• Whiteboard First: Sketch the algorithm before coding.

You’ve got this! ?