Skip to content
Coding Patterns - Guide to 30 Core Algorithm Patterns
Kadane's Algorithm: Complete Guide with Examples
Kadane's Algorithm: Practice Problems with Solutions

Kadane's Algorithm: Practice Problems with Solutions

Welcome to the practice problems for Kadane’s algorithm. If you need a refresher on the code, the code templates have the pattern in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems build on one idea, so the order matters.

  1. Best Time to Buy and Sell Stock shows the disguise. The problem is not a subarray problem on the surface, but converting prices to daily differences reveals Kadane’s algorithm underneath.
  2. Maximum Subarray is the pure form. Master the extend-or-restart decision here because every later problem is a variation of it.
  3. Maximum Product Subarray adds the sign flip. Products behave differently from sums, and the extra minimum tracker is the whole lesson.
  4. Maximum Sum Circular Subarray adds wrap-around. It pairs standard Kadane with a minimum-subarray pass.
  5. Maximum Subarray Sum with One Deletion adds a second state. The delete option changes the recurrence but not the one-pass structure.
  6. Max Sum of Rectangle No Larger Than K is the Hard capstone. It compresses a 2D matrix into 1D column sums and runs Kadane with an upper bound.
The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Best Time to Buy and Sell Stock

LeetCode 121 | Difficulty: Easy

Brief: Given daily prices, return the maximum profit from one buy and one sell, with the buy before the sell.

Why this pattern: The profit from buying on day i and selling on day j is the sum of the daily differences between i and j. The best profit is therefore the maximum subarray sum of the difference array. The problem is Kadane’s algorithm wearing a disguise.

Key Insight: Build the difference array on the fly. Each step adds one new diff to the running total, and the running total is exactly the profit of holding from the restart day to the current day.

Visual:

    graph LR
    A["prices: 7,1,5,3,6,4"] --> B["diffs: -6,4,-2,3,-2"]
    B --> C["max subarray of diffs"]
    C --> D["sum: 5"]
    D --> E["buy at 1, sell at 6"]

Code:

var maxProfit = function(prices) {
    let maxEndingHere = 0;
    let maxSoFar = 0;

    for (let i = 1; i < prices.length; i++) {
        const diff = prices[i] - prices[i - 1];
        // A day with negative diff is a losing day. Holding
        // through it only makes sense if it sits between gains.
        maxEndingHere = Math.max(diff, maxEndingHere + diff);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
};

Both accumulators start at 0 here, which is the one place that differs from standard Kadane. A profit of 0 means never buying, and that is always a legal answer in this problem. If the prices only fall, the answer is 0, not the least negative diff.

Medium Problems

2. Maximum Subarray

LeetCode 53 | Difficulty: Medium

Brief: Find the contiguous subarray with the largest sum and return that sum.

Why this pattern: This is the problem Kadane’s algorithm was invented for. Every other problem on this page is a variation of this one decision: extend the current subarray or start fresh.

Key Insight: A subarray either starts at the current element or continues the best subarray ending at the previous element. There is no third option, so the recurrence has exactly two candidates per position.

Visual:

    graph LR
    A["-2"] -->|"restart at 1"| B["1"]
    B -->|"ending -2, best 1"| C["-3"]
    C -->|"ending -2, best 1"| D["4"]
    D -->|"ending 4, best 4"| E["-1"]
    E -->|"ending 3, best 4"| F["2"]
    F -->|"ending 5, best 5"| G["1"]
    G -->|"ending 6, best 6"| H["-5"]
    H -->|"ending 1, best 6"| I["4"]
    I -->|"ending 5, best 6"| J["answer 6"]

Code:

var maxSubArray = function(nums) {
    let maxEndingHere = nums[0];
    let maxSoFar = nums[0];

    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
};

Seeding both accumulators with nums[0] and starting the loop at index 1 is the detail that handles all-negative input. Change the seed to 0 and [-3, -1, -2] returns 0 instead of -1.

3. Maximum Product Subarray

LeetCode 152 | Difficulty: Medium

Brief: Find the contiguous subarray with the largest product and return that product.

Why this pattern: Same structure as Kadane’s algorithm, with one twist. For sums a negative running total is always bad. For products a negative running product can become the best result after multiplying by another negative, so the minimum product must be tracked alongside the maximum.

Key Insight: At each element, the new maximum comes from three candidates. The element alone, the old maximum times the element, or the old minimum times the element. The old maximum must be saved before the new one overwrites it, because the new minimum needs it.

Visual:

    graph LR
    A["nums: 2,3,-2,4"] --> B["max: 2,6"]
    A --> C["min: 2,3"]
    B -->|"times -2"| D["max -2, min -12"]
    C -->|"times -2"| D
    D -->|"times 4"| E["max 4, best stays 6"]

Code:

var maxProduct = function(nums) {
    let maxEndingHere = nums[0];
    let minEndingHere = nums[0];
    let maxSoFar = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const tempMax = maxEndingHere;

        // A negative element flips the roles. The old minimum
        // becomes a candidate for the new maximum.
        maxEndingHere = Math.max(nums[i], maxEndingHere * nums[i], minEndingHere * nums[i]);
        minEndingHere = Math.min(nums[i], tempMax * nums[i], minEndingHere * nums[i]);

        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
};

The temporary snapshot is not an optimization, it is a correctness requirement. Without saving the old maximum, the new minimum would be computed from the already-overwritten value.

4. Maximum Sum Circular Subarray

LeetCode 918 | Difficulty: Medium

Brief: Find the maximum sum of a non-empty subarray in a circular array, where the subarray may wrap from the end of the array to the beginning.

Why this pattern: A wrapping subarray is the complement of a contiguous middle segment. Maximizing the wrap is the same as minimizing the segment it skips, so standard Kadane runs twice. Once for the maximum subarray, once for the minimum.

Key Insight: The answer is either the standard Kadane result or the total sum minus the minimum subarray sum. The all-negative case needs a guard, because there the minimum subarray is the whole array and the formula would produce an empty subarray.

Visual:

    graph LR
    A["nums: 5,-3,5"] --> B["max subarray: 7"]
    A --> C["total: 7"]
    A --> D["min subarray: -3"]
    B --> E["max(7, 7-(-3))"]
    D --> E
    E --> F["answer 10"]

Code:

var maxSubarraySumCircular = function(nums) {
    let maxEndingHere = nums[0], maxSoFar = nums[0];
    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    const total = nums.reduce((a, b) => a + b, 0);
    let minEndingHere = nums[0], minSoFar = nums[0];
    for (let i = 1; i < nums.length; i++) {
        minEndingHere = Math.min(nums[i], minEndingHere + nums[i]);
        minSoFar = Math.min(minSoFar, minEndingHere);
    }

    // All-negative input: the min subarray is the whole array,
    // so the wrap candidate would be an empty subarray.
    if (minSoFar === total) return maxSoFar;

    return Math.max(maxSoFar, total - minSoFar);
};

The all-negative guard is the detail interviewers probe. On [-3, -2, -3], the minimum subarray is the whole array, so total - minSoFar would be 0. That is an empty subarray, which the problem forbids. Standard Kadane’s answer, -2, is the correct one.

5. Maximum Subarray Sum with One Deletion

LeetCode 1186 | Difficulty: Medium

Brief: Find the maximum sum of a subarray where you may delete exactly one element (or none) from inside it.

Why this pattern: The extend-or-restart decision now runs in two states. One state has not spent the deletion yet, and one state has. Both states update in the same single pass.

Key Insight: At each element there are three choices. Extend the no-deletion state, start fresh, or spend the deletion on the current element. Spending the deletion ends the segment at the previous element, so the one-deletion state reads the previous no-deletion state.

Visual:

    graph LR
    A["arr: 1,-2,0,3"] --> B["no delete: 1,-1,0,3"]
    A --> C["one delete: 1,1,1,4"]
    B --> D["best 4"]
    C --> D
    D --> E["subarray 1,-2,0,3, delete -2"]

Code:

var maximumSum = function(arr) {
    let noDelete = arr[0];
    let oneDelete = arr[0];
    let best = arr[0];

    for (let i = 1; i < arr.length; i++) {
        const prevNoDelete = noDelete;

        noDelete = Math.max(arr[i], noDelete + arr[i]);
        // Spending the deletion on arr[i] ends the segment at
        // i-1 with no deletion used. Keeping arr[i] means the
        // deletion was already spent earlier.
        oneDelete = Math.max(prevNoDelete, oneDelete + arr[i]);

        best = Math.max(best, noDelete, oneDelete);
    }
    return best;
};

The prevNoDelete snapshot is the subtle part. The one-delete state needs the no-delete state from the previous position, so the update order matters. Compute the snapshot first, then update both states.

Hard Problems

6. Max Sum of Rectangle No Larger Than K

LeetCode 363 | Difficulty: Hard

Brief: Given a 2D matrix and an integer k, find the maximum sum of a rectangle whose sum is no larger than k.

Why this pattern: This is Kadane’s algorithm on a matrix. Fix the top and bottom rows of the rectangle, collapse each column between them into a running sum, and the row band becomes a 1D array. Kadane’s algorithm runs on that array, with one change. The cap of k means a plain maximum is not enough, so the prefix sums are kept in sorted order to find the largest subarray sum under the cap.

Key Insight: For each fixed pair of rows, the column-sum array changes by adding one row at a time. That makes the 2D problem a sequence of 1D Kadane problems, each solvable in

O(N log N)
time with a binary search.

Visual:

    graph LR
    A["matrix: [[1,0,1],[0,-2,3]]"] --> B["fix top=0, bottom=1"]
    B --> C["col sums: 1,-2,4"]
    C --> D["Kadane capped at k=2"]
    D --> E["best 2"]

Code:

var maxSumSubmatrix = function(matrix, k) {
    const rows = matrix.length, cols = matrix[0].length;
    let best = -Infinity;

    for (let top = 0; top < rows; top++) {
        const colSums = new Array(cols).fill(0);
        for (let bottom = top; bottom < rows; bottom++) {
            for (let c = 0; c < cols; c++) {
                colSums[c] += matrix[bottom][c];
            }

            // Sorted prefix sums. A binary search finds the
            // smallest prefix >= cur - k, which caps the
            // subarray sum at k while staying as large as possible.
            const prefix = [0];
            let cur = 0;
            for (const v of colSums) {
                cur += v;
                let lo = 0, hi = prefix.length;
                while (lo < hi) {
                    const mid = (lo + hi) >> 1;
                    if (prefix[mid] < cur - k) lo = mid + 1;
                    else hi = mid;
                }
                if (lo < prefix.length) {
                    best = Math.max(best, cur - prefix[lo]);
                }
                let insertAt = 0;
                while (insertAt < prefix.length && prefix[insertAt] < cur) insertAt++;
                prefix.splice(insertAt, 0, cur);
            }
        }
    }
    return best;
};

This problem combines three ideas into one solution. The row-band compression is prefix sum thinking, the column array is Kadane’s algorithm, and the sorted prefix list with binary search is the mechanism that enforces the cap. Trace it on a 2 by 3 matrix with k small to see where the cap rejects the plain maximum.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

Wrap Up

You have now seen Kadane’s algorithm in its pure form and in four disguises. The stock problem hides it behind a difference array. The product problem adds a sign-flip state. The circular problem runs it backwards. The deletion problem splits it into two states. The rectangle problem compresses a matrix into a single pass. Every one of them traces back to the same two-line decision. Extend or restart, then update the best seen so far.

If you can write that decision from memory, you can solve all of these problems in an interview. The remaining work is recognizing which variation a problem needs, and that recognition improves fastest with repeated review.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .