SEATS solution intuition


#1

Sol :slight_smile:

Make an array and store (index of 1st x - 0) , (index of 2nd x- 1) , … (index of kth x -(k-1)).
Take the median of this array and then take sum of abs(median - i th element of array) where i starts from 0 to the size of array.

Explanation :wink:

Assume that 1st x goes to index 0, 2nd x to index 1 and so on kth x to index k-1. So the total moves reqd will be

(index of 1st x - 0) + (index of 2nd x- 1) + … (index of kth x -(k-1))

Now assume if we have to start sequence from jth position so moves reqd will be

abs (index of 1st x - j) + abs (index of 2nd x- 1 - j) … + abs(index of kth x -(k-1)-j)

Since we need to find optimal j in this case it reduces to finding the minimum sum of points distance from a point . Which is minimum for the median of the array.


#2

Thanks man, it helped !!


#3

Thanks, the explanation was helpful.


#4

Thanks mate ! Really helpful


#5

This is quite helpful. Thank u for taking the time to post it.


#6

Can you prove why this approach works