Problem
Linear regression finds the line y = slope × x + intercept that best fits the data, meaning the sum of squared errors is as small as possible. For one input variable there is an exact formula:
- slope = Σ(x - x̄)(y - ȳ) / Σ(x - x̄)²
- intercept = ȳ - slope × x̄
where x̄ and ȳ are the means of xs and ys. If all xs are equal, return slope 0 and intercept ȳ.
Implement linear_regression(xs, ys).
Input
xs, ys: The x and y values of the data points (same length).
Output
Return [slope, intercept].
Constraints
1 ≤ number of points ≤ 10,000
-10,000 ≤ each value ≤ 10,000
Examples
Input:
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]
Expected output:
expected = [2.0, 1.0]Input:
std::vector<double> xs = {1.0, 2.0, 3.0, 4.0};
std::vector<double> ys = {3.0, 5.0, 7.0, 9.0};
Expected output:
std::vector<double> expected = {2.0, 1.0};Input:
double[] xs = new double[] {1.0, 2.0, 3.0, 4.0};
double[] ys = new double[] {3.0, 5.0, 7.0, 9.0};
Expected output:
double[] expected = new double[] {2.0, 1.0};Explanation
The points lie exactly on y = 2x + 1. x̄ = 2.5, ȳ = 6, Σ(x - x̄)(y - ȳ) = 10 and Σ(x - x̄)² = 5, so slope = 2 and intercept = 6 - 2 × 2.5 = 1.
Input:
xs = [0.0, 1.0, 2.0]
ys = [1.0, 3.0, 2.0]
Expected output:
expected = [0.5, 1.5]Input:
std::vector<double> xs = {0.0, 1.0, 2.0};
std::vector<double> ys = {1.0, 3.0, 2.0};
Expected output:
std::vector<double> expected = {0.5, 1.5};Input:
double[] xs = new double[] {0.0, 1.0, 2.0};
double[] ys = new double[] {1.0, 3.0, 2.0};
Expected output:
double[] expected = new double[] {0.5, 1.5};Explanation
x̄ = 1 and ȳ = 2. Σ(x - x̄)(y - ȳ) = (-1)(-1) + 0 + (1)(0) = 1 and Σ(x - x̄)² = 2, so slope = 0.5 and intercept = 2 - 0.5 × 1 = 1.5.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
The best-fit line comes from how x and y vary together around their means.
Hint 2
Compute the means first, then accumulate the numerator and denominator for the slope formula.
Hint 3
If all x-values are the same, the slope is undefined, so return a flat line through the average y-value.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.