Peak finding (find_peaks) in SciPy - Time & Space Complexity

Time Complexity: Peak finding (find_peaks)

O(n)

Understanding Time Complexity

When we use peak finding in data, we want to know how long it takes to find all peaks as data grows.

We ask: How does the time to find peaks change when the data list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.signal import find_peaks

data = np.array([1, 3, 2, 5, 4, 6, 3, 2, 7, 5])
peaks, _ = find_peaks(data)
print(peaks)
    

This code finds the positions of peaks in a 1D numeric array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning through the data array once to compare neighbors.
• How many times: Each element is checked once except the first and last.

How Execution Grows With Input

As the data size grows, the time to find peaks grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 8 comparisons
100	About 98 comparisons
1000	About 998 comparisons

Pattern observation: Doubling the input roughly doubles the work because each element is checked once.

Final Time Complexity

Time Complexity: O(n)

This means the time to find peaks grows linearly with the size of the input data.

Common Mistake

[X] Wrong: "Finding peaks takes longer than checking each element once because it's complicated."

[OK] Correct: The method only compares neighbors in one pass, so it does not do extra repeated work.

Interview Connect

Understanding how peak finding scales helps you explain efficiency clearly and shows you can analyze real data tasks.

Self-Check

"What if we wanted to find peaks in a 2D array instead? How would the time complexity change?"

Practice

1. What does the find_peaks function in scipy do?

easy

A. It finds local maxima (peaks) in a 1D array of data.

B. It sorts the data in ascending order.

C. It calculates the average value of the data.

D. It removes all negative values from the data.

Solution

1. Step 1: Understand the purpose of find_peaks

   The function is designed to identify points in data where values are higher than their neighbors, called peaks.

2. Step 2: Compare options with function behavior

   Only It finds local maxima (peaks) in a 1D array of data. correctly describes this behavior; others describe unrelated operations.

3. Final Answer:

   It finds local maxima (peaks) in a 1D array of data. -> Option A

4. Quick Check:

   find_peaks locates peaks = D [OK]

Hint: Remember: find_peaks finds highs, not sorting or averaging [OK]

Common Mistakes:

• Confusing peak finding with sorting data
• Thinking it calculates statistics like mean
• Assuming it filters values instead of locating peaks

2. Which of the following is the correct way to import and use find_peaks from scipy.signal?

easy

A. import find_peaks from scipy.signal
peaks = find_peaks(data)

B. from scipy.signal import find_peaks
peaks = find_peaks(data)

C. from scipy import find_peaks
peaks = find_peaks(data)

D. import scipy.signal.find_peaks
peaks = find_peaks(data)

Solution

1. Step 1: Recall correct import syntax in Python

   Python uses 'from module import function' to import specific functions.

2. Step 2: Match syntax with options

   from scipy.signal import find_peaks peaks = find_peaks(data) uses correct syntax. Options A, C, and D have invalid import statements.

3. Final Answer:

   from scipy.signal import find_peaks\npeaks = find_peaks(data) -> Option B

4. Quick Check:

   Correct import syntax = B [OK]

Hint: Use 'from module import function' for specific imports [OK]

Common Mistakes:

• Using 'import function from module' which is invalid
• Trying to import from wrong module path
• Using dot notation in import statement incorrectly

3. Given the code below, what will be the output of peaks?

import numpy as np
from scipy.signal import find_peaks

data = np.array([0, 2, 1, 3, 0, 1, 2, 1])
peaks, _ = find_peaks(data, height=2)
print(peaks)

medium

A. [3]

B. [1 3]

C. [1 3 6]

D. [2 5]

Solution

1. Step 1: Identify peaks in the data array

   Data values: [0, 2, 1, 3, 0, 1, 2, 1]. Peaks are points higher than neighbors: indices 1 (2), 3 (3), and 6 (2).

2. Step 2: Apply height=2 filter

   Peaks with height >= 2 are kept. Index 1 (2 >= 2), 3 (3 >= 2), 6 (2 >= 2), so indices 1, 3, 6 remain.

3. Final Answer:

   [1 3 6] -> Option C

4. Quick Check:

   Peaks with height >= 2 = [1 3 6] [OK]

Hint: Check peak values against height filter carefully [OK]

Common Mistakes:

• Thinking height filter requires strictly greater than threshold (it's >=)
• Misidentifying peak positions
• Ignoring the height parameter

4. The following code is intended to find peaks at least 3 units apart, but it returns more peaks than expected. What is the error?

import numpy as np
from scipy.signal import find_peaks

data = np.array([1, 3, 2, 4, 3, 5, 2])
peaks = find_peaks(data, 3)
print(peaks)

medium

A. The distance parameter is not applied because it should be passed as a keyword argument.

B. The distance parameter is applied correctly; the issue is with the data array.

C. The code is missing parentheses around the print argument.

D. The find_peaks function does not support the distance parameter.

Solution

1. Step 1: Check how distance parameter is passed

   In find_peaks, distance must be passed as a keyword argument, e.g., distance=3.

2. Step 2: Analyze the code

   The code passes 3 positionally after data, which sets height=3 instead of distance=3. Thus distance is not applied, returning all local peaks [1,3,5] instead of filtered [1,5].

3. Step 3: Verify output type

   find_peaks returns a tuple (indices, properties). Printing peaks directly prints the tuple, which may confuse.

4. Final Answer:

   The distance parameter is not applied because it should be passed as a keyword argument. -> Option A

5. Quick Check:

   distance must be keyword argument = C [OK]

Hint: Always pass distance as keyword argument: distance=number [OK]

Common Mistakes:

• Passing distance as positional argument
• Expecting find_peaks to return only indices
• Misunderstanding output format of find_peaks

5. You have noisy sensor data and want to find peaks that are at least 5 units high and at least 10 samples apart. Which find_peaks call correctly applies these conditions?

import numpy as np
from scipy.signal import find_peaks

sensor_data = np.random.rand(100) * 10

# Which call is correct?

hard

A. peaks = find_peaks(sensor_data, height=(5, None), distance=10)

B. peaks = find_peaks(sensor_data, height=5, distance=10)

C. peaks, _ = find_peaks(sensor_data, min_height=5, min_distance=10)

D. peaks, _ = find_peaks(sensor_data, height=5, distance=10)

Solution

1. Step 1: Understand parameter usage in find_peaks

   Height is specified with 'height=5' to find peaks at least 5 units high. Distance is specified with 'distance=10' to ensure peaks are at least 10 samples apart.

2. Step 2: Evaluate each option

   peaks, _ = find_peaks(sensor_data, height=5, distance=10) correctly uses height and distance parameters and unpacks the tuple output. peaks = find_peaks(sensor_data, height=5, distance=10) misses unpacking. peaks, _ = find_peaks(sensor_data, min_height=5, min_distance=10) uses invalid parameter names. peaks = find_peaks(sensor_data, height=(5, None), distance=10) uses a tuple for height which is valid but unnecessary here.

3. Final Answer:

   peaks, _ = find_peaks(sensor_data, height=5, distance=10) -> Option D

4. Quick Check:

   Use height and distance keywords, unpack output = A [OK]

Hint: Use height= and distance= with unpacking for correct results [OK]

Common Mistakes:

• Using wrong parameter names like min_height
• Not unpacking the tuple returned by find_peaks
• Passing height as a tuple unnecessarily