Last active 5 days ago

Interview prep notes

Revision d9a061cabd4af9d0c356a31d66ffcad33422999b

kadane.md Raw

Kadane's Algorithm: Maximum Subarray in One Pass

Maximum Subarray (LeetCode 53) asks for the largest sum of any contiguous subarray. Brute force checks every pair of endpoints, which is O(n²). Kadane's algorithm does it in O(n) with O(1) memory.

The insight

At each index, the best subarray ending here either extends the previous best one or starts fresh. You start fresh whenever the running sum has gone negative, because a negative prefix can only make things worse.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

Initialising with nums[0] (not 0) correctly handles arrays that are all negative, a case interviewers like to test.

Variations

  • Return the indices: remember where cur was last reset; update start/end whenever best improves.
  • Maximum Product Subarray (152): track both the max and the min product, because a negative number flips them.
  • Circular array (918): answer = max(normal Kadane, total sum minus the minimum subarray), unless every number is negative.
  • Best Time to Buy and Sell Stock (121): Kadane on the daily price differences.

Explaining it as DP

Say: "dp[i] is the best sum of a subarray ending at i; dp[i] = max(nums[i], dp[i-1] + nums[i]), and I only need the previous value, so I keep one variable." Framing it this way shows you understand why it works, not just the trick.


Disclosure: I'm part of the Linkjob AI team (an AI interview assistant). Free to share.