Convolve 1D Signal

Implement 1D convolution without built-in convolution functions.

convolution arrays sliding-window list-operations

Write a function `convolve1d(signal, kernel)` that returns the 1D discrete convolution of `signal` with `kernel` in 'full' mode. The output length equals `len(signal) + len(kernel) - 1`.

For each output index `n` (0 ≤ n < N+M-1), where N is the signal length and M is the kernel length, the output is:

out[n] = sum_{k} signal[n-k] * kernel[k] for all k where 0 ≤ k < M and 0 ≤ n-k < N.

Inputs are python lists of integers or floats. The output must be a list of the same type as the natural multiplication of inputs (e.g., int*int -> int, float*int -> float). Do NOT use any convolution functions from libraries (e.g., numpy.convolve, scipy.signal.convolve). You may use loops and list comprehensions.

Function signature: `def convolve1d(signal: list, kernel: list) -> list:`

Return a list.

Do NOT modify the input lists.

Constraints

- Input lists are non-empty, length 1 to 10^5.
- Values are real numbers (integers or floats).
- Time complexity O(N*M) is acceptable, but vectorization is not required.
- Output length is len(signal) + len(kernel) - 1.
- Must preserve numeric types correctly.

Example

>>> signal = [1, 2, 3]
>>> kernel = [0.5, 1]
>>> convolve1d(signal, kernel)
[0.5, 2.0, 3.5, 3.0]
>>> signal = [-1, 0, 1]
>>> kernel = [1, 2, 3]
>>> convolve1d(signal, kernel)
[-1, -2, -2, 2, 3]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

For each output index, determine the valid overlap range between the kernel and the signal.

Use two pointers or slicing to align the kernel reversed against the signal.

A nested loop over output indices and kernel indices works fine.

Avoid importing any modules; plain Python is enough.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.