Quick Overview

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.

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.

Overview: 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

Hints

  1. Compute the sum of the first k elements as the initial window.
  2. Slide the window by adding the next element and subtracting the element that leaves; track the maximum sum.

Loading coding console...

Show the approach

Approach

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)