Dsa
Dynamic Programming
Easy
Data Stream Clustering
You are given a sorted list of N sensor readings. You need to partition them into clusters. The cost of a cluster containing readings from index i to j is calculated as: (Reading[j] - Reading[i])^2 + K, where K is a fixed setup cost for any cluster. Minimize the total cost to cover all readings.
Input Format:
Line 1: N K
Line 2: N sorted integers
Output Format:
A single integer (min cost).
Example:
Input:
4 10
1 5 6 10
Output:
31
Explanation: Clusters [1] and [5, 6] and [10]. Costs: (1-1)^2+10=10, (6-5)^2+10=11, (10-10)^2+10=10. Total 31.
Key concepts
dynamic_programmingsegmentation
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now