Find Maximum Sum of Contiguous Subarray Length k
Company: Apple
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
Monitoring website traffic and needing the highest traffic within any fixed-length time window.
##### Question
Given an array of positive integers representing hits per minute and an integer k, return the maximum sum of any contiguous subarray of length k. Provide time and space complexity.
##### Hints
Two-pointer sliding window keeps running sum; O(n) time, O(
1) space.
Quick Answer: This question evaluates skill in array manipulation and computing aggregate metrics over fixed-length intervals, along with understanding of algorithmic complexity and trade-offs between runtime and memory.
Given an array of positive integers nums and an integer k, return the maximum sum of any contiguous subarray of length k. Assume 1 <= k <= len(nums).
Constraints
- 1 <= n <= 200000 where n = len(nums)
- 1 <= k <= n
- 1 <= nums[i] <= 1000000000
- Result fits in 64-bit signed integer
Solution
from typing import List
def max_sum_subarray_k(nums: List[int], k: int) -> int:
n = len(nums)
# Assumes 1 <= k <= n
curr = sum(nums[:k])
max_sum = curr
for i in range(k, n):
curr += nums[i] - nums[i - k]
if curr > max_sum:
max_sum = curr
return max_sum
Explanation
Use a sliding window of size k. Initialize the sum of the first k elements. For each subsequent position, add the entering element and subtract the leaving element to update the running sum in O(1). Keep track of the maximum running sum encountered.
Time complexity: O(n). Space complexity: O(1).
Hints
- Compute the sum of the first k elements as the initial window.
- Slide the window by adding the next element and subtracting the element that leaves; track the maximum sum.