Kadane's Algorithm Maximum Subarray in DSA Javascript - Time & Space Complexity

Time Complexity: Kadane's Algorithm Maximum Subarray

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum sum of a continuous subarray changes as the input array grows.

How does the number of steps grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the largest sum of any continuous part of the array using a single pass.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop that goes through each number in the array once.
• How many times: Exactly once for each element, so n times if the array has n elements.

How Execution Grows With Input

As the array size grows, the number of steps grows directly in proportion.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the input roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum subarray sum grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "Because we check sums, the time must be quadratic O(n²) because of nested loops."

[OK] Correct: Kadane's algorithm cleverly keeps track of sums as it goes, so it only needs one pass through the array, not nested loops.

Interview Connect

Understanding this linear time solution shows you can find efficient answers to problems that seem complex at first, a skill valued in real coding challenges.

Self-Check

"What if we changed the algorithm to check all possible subarrays with nested loops? How would the time complexity change?"

Practice

1. What does Kadane's Algorithm primarily help to find in an array of numbers?

easy

A. The maximum sum of a contiguous subarray

B. The minimum element in the array

C. The total sum of all elements

D. The maximum product of any two elements

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers.

2. Step 2: Compare with other options

   Options A, B, and D describe different problems not solved by Kadane's Algorithm.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option A

4. Quick Check:

   Kadane's Algorithm = Maximum subarray sum [OK]

Hint: Kadane's finds max sum in a continuous slice [OK]

Common Mistakes:

• Confusing max sum with max product
• Thinking it finds minimum element
• Assuming it sums all elements

2. Which of the following is the correct initialization step in Kadane's Algorithm in JavaScript?

easy

A. let maxSoFar = null, maxEndingHere = null;

B. let maxSoFar = 0, maxEndingHere = 0;

C. let maxSoFar = 0, maxEndingHere = -Infinity;

D. let maxSoFar = -Infinity, maxEndingHere = 0;

Solution

1. Step 1: Understand initialization in Kadane's Algorithm

   We start with maxSoFar as the smallest possible number to handle negative values, so -Infinity is used. maxEndingHere starts at 0 to accumulate sums.

2. Step 2: Check each option

   let maxSoFar = -Infinity, maxEndingHere = 0; correctly initializes maxSoFar to -Infinity and maxEndingHere to 0. Other options either initialize incorrectly or use null which is invalid for numeric operations.

3. Final Answer:

   let maxSoFar = -Infinity, maxEndingHere = 0; -> Option D

4. Quick Check:

   Initialization = maxSoFar -Infinity, maxEndingHere 0 [OK]

Hint: Start maxSoFar at -Infinity to handle negatives [OK]

Common Mistakes:

• Initializing maxSoFar to 0 causes wrong results with negatives
• Using null instead of numbers
• Swapping initial values of variables

3. What is the output of the following JavaScript code using Kadane's Algorithm?

const arr = [-2, 3, 2, -1];
let maxSoFar = -Infinity, maxEndingHere = 0;
for (let num of arr) {
  maxEndingHere = Math.max(num, maxEndingHere + num);
  maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
console.log(maxSoFar);

medium

A. 4

B. 5

C. 3

D. 2

Solution

1. Step 1: Trace the loop iterations

   Start: maxSoFar = -Infinity, maxEndingHere = 0 - num = -2: maxEndingHere = max(-2, 0 + -2) = -2; maxSoFar = max(-Infinity, -2) = -2 - num = 3: maxEndingHere = max(3, -2 + 3) = 3; maxSoFar = max(-2, 3) = 3 - num = 2: maxEndingHere = max(2, 3 + 2) = 5; maxSoFar = max(3, 5) = 5 - num = -1: maxEndingHere = max(-1, 5 + -1) = 4; maxSoFar = max(5, 4) = 5

2. Step 2: Determine final maxSoFar value

   After the loop, maxSoFar is 5, which is the maximum sum of a contiguous subarray.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max subarray sum = 5 [OK]

Hint: Track maxEndingHere and maxSoFar each step [OK]

Common Mistakes:

• Not updating maxSoFar correctly
• Confusing maxEndingHere with maxSoFar
• Ignoring negative numbers impact

4. Identify the bug in this Kadane's Algorithm implementation and select the fix:

function maxSubArray(arr) {
  let maxSoFar = 0;
  let maxEndingHere = 0;
  for (let i = 0; i < arr.length; i++) {
    maxEndingHere += arr[i];
    if (maxEndingHere < 0) maxEndingHere = 0;
    if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
  }
  return maxSoFar;
}

medium

A. Return maxEndingHere instead of maxSoFar

B. Remove resetting maxEndingHere to 0 when negative

C. Initialize maxSoFar to -Infinity to handle all negative arrays

D. Change maxEndingHere += arr[i] to maxEndingHere = arr[i]

Solution

1. Step 1: Understand the bug with initialization

   Initializing maxSoFar to 0 causes wrong results if all numbers are negative, because maxSoFar will never be less than 0.

2. Step 2: Fix initialization to handle negative arrays

   Setting maxSoFar to -Infinity allows the algorithm to correctly track the maximum subarray sum even if all elements are negative.

3. Final Answer:

   Initialize maxSoFar to -Infinity to handle all negative arrays -> Option C

4. Quick Check:

   maxSoFar init = -Infinity fixes negative array bug [OK]

Hint: Use -Infinity for maxSoFar to handle negatives [OK]

Common Mistakes:

• Leaving maxSoFar at 0 causes wrong max for negatives
• Removing reset breaks algorithm logic
• Returning wrong variable

5. Given the array [-3, -1, -2, -5], what is the maximum subarray sum using Kadane's Algorithm, and why?

hard

A. -1 because the algorithm picks the least negative single element

B. -3 because it is the first element and the algorithm stops early

C. 0 because the algorithm resets sums to zero on negatives

D. -11 because it sums all negative elements

Solution

1. Step 1: Understand Kadane's behavior with all negatives

   When all numbers are negative, Kadane's Algorithm returns the maximum single element (least negative) because any sum of multiple negatives is smaller.

2. Step 2: Identify the maximum element in the array

   Array elements: -3, -1, -2, -5. The maximum single element is -1.

3. Final Answer:

   -1 because the algorithm picks the least negative single element -> Option A

4. Quick Check:

   Max subarray sum in all negatives = max element [OK]

Hint: Max subarray in negatives = max single element [OK]

Common Mistakes:

• Assuming sum resets to zero means result is zero
• Summing all negatives incorrectly
• Stopping early without checking all elements