Problem 399290 · medium · Level 03 Linear Management & Searching

The Flat That Moves the Line

influential points · least-squares line · leave one out · running sums

A letting agency fits a least-squares line rent = a + b * area to its flats (area in m², monthly rent in whole euros), so the slope b is "euros per extra square metre". A colleague suspects that one unusual flat is pulling the slope around.

For every flat i, imagine refitting the line without flat i and compare that slope with the slope of all the flats. Write most_influential(area, rent) that returns a tuple (i, b_all, b_without): the index of the flat whose removal changes the slope the most (in absolute value), the slope with every flat, and the slope without flat i. If several flats change it by the same amount (within 1e-9), return the smallest index.

The least-squares slope of pairs (x, y) is b = Sxy / Sxx, with Sxy the sum of (x - mean x)(y - mean y) and Sxx the sum of (x - mean x)².

The setup provides flat_listing(n, seed, extra), which returns random lists (area, rent) of n flats; with extra=True the last flat is a very large penthouse let at a modest rent.

Examples

Input:  area = [40, 50, 60, 70, 200], rent = [800, 950, 1100, 1250, 1500]
Output: (4, 3.6143187066974596, 15.0)
Explanation: the four ordinary flats lie exactly on a line with 15 euros per m².
The large flat at 200 m² drags the slope with all five down to 3.61; without it the
slope is 15 again. Removing any other flat changes the slope far less.

Input:  area = [30, 60, 90], rent = [600, 600, 1200]
Output: (0, 10.0, 20.0)
Explanation: without flat 0 the slope is 20, without flat 2 it is 0: both change it
by 10, so the smaller index wins.

Constraints

  • 3 <= len(area) == len(rent) <= 10**5; all values are integers between 1 and 10**4
  • area holds at least three different values, so every refit has a slope
  • floats are compared with a tolerance of 1e-6
  • the largest tests need an O(n) solution: refitting from scratch for every flat is too slow

Goals

  • Measure how much a single point changes the least-squares slope
  • Refit without each point in O(1) by updating sums instead of starting again
  • Tell a point with a large influence from one that merely has an unusual value
Starting Python…