Magnetic Force Between Two Balls LeetCode solution in C++

1
// OJ:
2
// https://leetcode.com/contest/weekly-contest-202/problems/magnetic-force-between-two-balls/
3
// Author: github.com/lzl124631x
4
// Time: O(log(max(A)) * N + NlogN)
5
// Space: O(1)
6
class Solution {
7
  bool valid(vector<int> &A, int M, int m) {
8
    int prev = 0;
9
    for (int i = 1, j = 1; i < m; ++i) {
10
      while (j < A.size() && A[j] < A[prev] + M) ++j;
11
      if (j >= A.size()) return false;
12
      prev = j;
13
    }
14
    return true;
15
  }
16

17
 public:
18
  int maxDistance(vector<int> &A, int m) {
19
    sort(begin(A), end(A));
20
    if (m == 2) return A.back() - A[0];
21
    int L = 1, R = A.back() - A[0];
22
    while (L <= R) {
23
      int M = (L + R) / 2;
24
      if (valid(A, M, m))
25
        L = M + 1;
26
      else
27
        R = M - 1;
28
    }
29
    return R;
30
  }
31
};