I like the way you directly calculated the distance from the I and J arrays in the second solution.
I did something similar, but then found out the meeting points and then computed the distance.
For the test cases on the OJ though that runs in 2 ms as well.
If someone's curious as to how I found those points, I did it by maintaining the lSum and rSum for each index. Then with help of some maths concluded that the min point would the the one where I[i] >= Math.abs(lSum[i]rSum[i]). And that such an i, always exists for any one dimensional array.
S
shikhs.prasad
@shikhs.prasad
0
Reputation
4
Posts
77
Profile views
0
Followers
0
Following
Posts made by shikhs.prasad

RE: O(mn) Java, 2ms

RE: Am I the only person who don't know why median could give shortest distance?
The article you point to is nice, but that is minimizing sx, whereas in the question we need to minimize sx*s, which doesn't necessarily have to be the median.