Compute rolling standard deviation in O(n)

Given an array of numbers and a window size k, compute the rolling standard deviation for every contiguous window. Design an O(n) algorithm that updates statistics incrementally rather than recomputing each window from scratch. Use the variance identity by maintaining running sum and sum of squares (or adapt a one-pass method like Welford’s algorithm for a sliding window), discuss numerical stability, analyze time and space complexity, and handle edge cases (k ≤ 0, k > n, k = 1, NaNs). Implement and provide tests.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute Rolling Standard Deviation in O(n)

Given an array of numbers nums and a window size k, compute the sample rolling standard deviation for every contiguous window of length k.

Your algorithm must run in O(n) time by updating statistics incrementally as the window slides, rather than recomputing each window from scratch. Maintain a running sum S and running sum of squares Q over the current window. When the window slides by one element (dropping out, adding in):

• S += in - out
• Q += in*in - out*out

The sample variance of a window is then var = (Q - S*S/k) / (k - 1), and the standard deviation is sqrt(var) (clamp tiny negative values caused by floating-point error to 0).

Return a list with one std value per window, in left-to-right order. There are n - k + 1 windows.

Conventions / edge cases:

• If k <= 0 or k > n, return an empty list.
• If k == 1, the sample std of every single-element window is 0.0 (the k-1 denominator is degenerate, so define it as 0 by convention).
• Use the sample denominator k - 1 (ddof = 1), not the population denominator k — interviewers at quant shops are picky about this.
• Round each std to 6 decimal places.

Constraints

• 0 <= len(nums) <= 10^5
• Window size k may be any integer; k <= 0 or k > len(nums) yields an empty result
• Numbers fit in standard floating point; use the sample (k-1) denominator
• Round each window's std to 6 decimal places

Examples

Example 1

Input: ([1, 2, 3, 4, 5], 2)
Output: [0.707107, 0.707107, 0.707107, 0.707107]

Explanation: Each 2-element window has values differing by 1; sample var = ((-0.5)^2+(0.5)^2)/1 = 0.5, std = sqrt(0.5) ≈ 0.707107.

Example 2

Input: ([2, 4, 6, 8], 3)
Output: [2.0, 2.0]

Explanation: Window [2,4,6]: mean 4, sample var = (4+0+4)/2 = 4, std = 2.0. Window [4,6,8] is identical by symmetry.

Hints

1. Don't recompute the mean and variance from scratch for each window — that is O(n*k). Maintain a running sum S and running sum of squares Q over the current window so each slide is O(1).
2. Use the variance identity: sample variance = (Q - S*S/k) / (k - 1), where S is the window sum and Q is the window sum of squares. Take the square root for std.
3. Handle the denominator carefully: the interviewer cares that you use k-1 (sample), not k (population). Treat k==1 as std 0, and clamp any tiny negative variance from float error up to 0.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given an array of numbers and a window size k, compute the rolling standard deviation for every contiguous window. Design an O(n) algorithm that updates statistics incrementally rather than recomputing each window from scratch. Use the variance identity by maintaining running sum and sum of squares (or adapt a one-pass method like Welford’s algorithm for a sliding window), discuss numerical stability, analyze time and space complexity, and handle edge cases (k ≤ 0, k > n, k = 1, NaNs). Implement and provide tests.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.