Implement local maxima, bagging, and k-means

Part 1: Local Maxima

Given an array of integers nums, return the indices of all local maxima. A local maximum is defined as an element that is strictly greater than its immediate neighbors (if neighbors exist). For boundaries, the element is a local maximum if it is greater than its only neighbor.

def find_local_maxima(nums: List[int]) -> List[int]:

Part 2: Bagging Classifier

Implement a simple Bagging classifier that trains n_estimators decision trees using bootstrap sampling (sampling with replacement). The final prediction for a given input should be the majority vote of the individual trees.

class SimpleBaggingClassifier: def __init__(self, n_estimators: int): # Initialize trees here def fit(self, X: List[List[float]], y: List[int]): # Train estimators on bootstrapped samples def predict(self, X: List[List[float]]) -> List[int]: # Return majority vote

Part 3: K-Means Clustering

Implement the k-means clustering algorithm for a 2D dataset. Initialize centroids by picking k random points from the input. Run the algorithm until the centroids no longer change or a maximum number of iterations is reached.

def k_means(points: List[List[float]], k: int, max_iters: int) -> List[List[float]]:

Examples

Local Maxima: [1, 3, 2, 5, 4] -> [1, 3] (Indices of 3 and 5). K-Means: Input [[1,1], [1,2], [10,10], [10,11]], k=2. Expected output: [[1, 1.5], [10, 10.5]] (approximated).

Constraints

• nums length up to 10^5.
• k is smaller than the number of data points.
• Use Euclidean distance for k-means.