Unit 4 Session 2 (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Initialize a sliding window of size k. Compute the sum of the initial window then slide the window across the list while updating the sum and computing the new averages.
1) Initialize an empty list `result` to store the average of each subarray.
2) Use two variables, `window_sum` to store the sum of elements in the current window, and `window_start` to indicate the start of the window.
3) Iterate through `arr` with a variable `window_end`:
a) Add `arr[window_end]` to `window_sum`.
b) If `window_end` is at least k - 1 (ensuring the window has reached size k):
i) Append the average of the current window (`window_sum / k`) to `result`.
ii) Subtract `arr[window_start]` from `window_sum` to remove the element that will be out of the window.
iii) Increment `window_start` to slide the window right.
4) Return the list `result` containing all averages.
⚠️ Common Mistakes
def find_averages_of_subarrays(k, arr):
result = []
window_sum, window_start = 0.0, 0
for window_end in range(len(arr)):
window_sum += arr[window_end] # Add the next element to the window
# Slide the window if we've hit the size 'k'
if window_end >= k - 1:
result.append(window_sum / k) # Calculate the average
window_sum -= arr[window_start] # Remove the element going out
window_start += 1 # Slide the window ahead
return result