Skip to content

3464. Maximize the Distance Between Points on a Square 👍

  • Time: $O(n\log\texttt{side})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
struct Sequence {
  int startX;
  int startY;
  int endX;
  int endY;
  int length;
};

class Solution {
 public:
  int maxDistance(int side, vector<vector<int>>& points, int k) {
    const vector<pair<int, int>> ordered = getOrderedPoints(side, points);
    int l = 0;
    int r = side;

    while (l < r) {
      const int m = (l + r + 1) / 2;
      if (isValidDistance(ordered, k, m))
        l = m;
      else
        r = m - 1;
    }

    return l;
  }

 private:
  // Returns true if we can select `k` points such that the minimum Manhattan
  // distance between any two consecutive chosen points is at least `m`.
  bool isValidDistance(const vector<pair<int, int>>& ordered, int k, int d) {
    deque<Sequence> dq{{ordered[0].first, ordered[0].second, ordered[0].first,
                        ordered[0].second, 1}};
    int maxLength = 1;

    for (int i = 1; i < ordered.size(); ++i) {
      const auto& [x, y] = ordered[i];
      int startX = x;
      int startY = y;
      int length = 1;
      while (!dq.empty() &&
             (abs(x - dq.front().endX) + abs(y - dq.front().endY) >= d)) {
        if (abs(x - dq.front().startX) + abs(y - dq.front().startY) >= d &&
            dq.front().length + 1 >= length) {
          startX = dq.front().startX;
          startY = dq.front().startY;
          length = dq.front().length + 1;
          maxLength = max(maxLength, length);
        }
        dq.pop_front();
      }
      dq.emplace_back(startX, startY, x, y, length);
    }

    return maxLength >= k;
  }

  // Returns the ordered points on the perimeter of a square of side length
  // `side`, starting from left, top, right, and bottom boundaries.
  vector<pair<int, int>> getOrderedPoints(int side,
                                          vector<vector<int>>& points) {
    vector<pair<int, int>> left;
    vector<pair<int, int>> top;
    vector<pair<int, int>> right;
    vector<pair<int, int>> bottom;

    for (const vector<int>& point : points) {
      const int x = point[0];
      const int y = point[1];
      if (x == 0 && y > 0)
        left.emplace_back(x, y);
      else if (x > 0 && y == side)
        top.emplace_back(x, y);
      else if (x == side && y < side)
        right.emplace_back(x, y);
      else
        bottom.emplace_back(x, y);
    }

    ranges::sort(left);
    ranges::sort(top);
    ranges::sort(right, greater<>());
    ranges::sort(bottom, greater<>());
    left.insert(left.end(), top.begin(), top.end());
    left.insert(left.end(), right.begin(), right.end());
    left.insert(left.end(), bottom.begin(), bottom.end());
    return left;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
  public int maxDistance(int side, int[][] points, int k) {
    List<int[]> ordered = getOrderedPoints(side, points);
    int l = 0;
    int r = side;

    while (l < r) {
      final int m = (l + r + 1) / 2;
      if (isValidDistance(ordered, k, m))
        l = m;
      else
        r = m - 1;
    }

    return l;
  }

  private record Sequence(int startX, int startY, int endX, int endY, int length) {}

  // Returns true if we can select `k` points such that the minimum Manhattan
  // distance between any two consecutive chosen points is at least `m`.
  private boolean isValidDistance(List<int[]> ordered, int k, int d) {
    Deque<Sequence> dq = new ArrayDeque<>(List.of(new Sequence(
        ordered.get(0)[0], ordered.get(0)[1], ordered.get(0)[0], ordered.get(0)[1], 1)));
    int maxLength = 1;

    for (int i = 1; i < ordered.size(); ++i) {
      final int x = ordered.get(i)[0];
      final int y = ordered.get(i)[1];
      int startX = x;
      int startY = y;
      int length = 1;
      while (!dq.isEmpty() &&
             (Math.abs(x - dq.peekFirst().endX()) + Math.abs(y - dq.peekFirst().endY()) >= d)) {
        if (Math.abs(x - dq.peekFirst().startX()) + Math.abs(y - dq.peekFirst().startY()) >= d &&
            dq.peekFirst().length() + 1 >= length) {
          startX = dq.peekFirst().startX();
          startY = dq.peekFirst().startY();
          length = dq.peekFirst().length() + 1;
          maxLength = Math.max(maxLength, length);
        }
        dq.pollFirst();
      }
      dq.addLast(new Sequence(startX, startY, x, y, length));
    }

    return maxLength >= k;
  }

  // Returns the ordered points on the perimeter of a square of side length
  // `side`, starting from left, top, right, and bottom boundaries.
  private List<int[]> getOrderedPoints(int side, int[][] points) {
    List<int[]> left = new ArrayList<>();
    List<int[]> top = new ArrayList<>();
    List<int[]> right = new ArrayList<>();
    List<int[]> bottom = new ArrayList<>();

    for (int[] point : points) {
      final int x = point[0];
      final int y = point[1];
      if (x == 0 && y > 0)
        left.add(point);
      else if (x > 0 && y == side)
        top.add(point);
      else if (x == side && y < side)
        right.add(point);
      else
        bottom.add(point);
    }

    left.sort(Comparator.comparingInt(a -> a[1]));
    top.sort(Comparator.comparingInt(a -> a[0]));
    right.sort(Comparator.comparingInt(a -> - a[1]));
    bottom.sort(Comparator.comparingInt(a -> - a[0]));
    List<int[]> ordered = new ArrayList<>();
    ordered.addAll(left);
    ordered.addAll(top);
    ordered.addAll(right);
    ordered.addAll(bottom);
    return ordered;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from dataclasses import dataclass


@dataclass(frozen=True)
class Sequence:
  startX: int
  startY: int
  endX: int
  endY: int
  length: int

  def __iter__(self):
    yield self.startX
    yield self.startY
    yield self.endX
    yield self.endY
    yield self.length


class Solution:
  def maxDistance(self, side: int, points: list[list[int]], k: int) -> int:
    ordered = self._getOrderedPoints(side, points)

    def isValidDistance(m: int) -> bool:
      """
      Returns True if we can select `k` points such that the minimum Manhattan
      distance between any two consecutive chosen points is at least `m`.
      """
      dq = collections.deque([Sequence(*ordered[0], *ordered[0], 1)])
      maxLength = 1

      for i in range(1, len(ordered)):
        x, y = ordered[i]
        startX, startY = ordered[i]
        length = 1
        while dq and abs(x - dq[0].endX) + abs(y - dq[0].endY) >= m:
          if (abs(x - dq[0].startX) + abs(y - dq[0].startY) >= m
                  and dq[0].length + 1 >= length):
            startX = dq[0].startX
            startY = dq[0].startY
            length = dq[0].length + 1
            maxLength = max(maxLength, length)
          dq.popleft()
        dq.append(Sequence(startX, startY, x, y, length))

      return maxLength >= k

    l = 0
    r = side

    while l < r:
      m = (l + r + 1) // 2
      if isValidDistance(m):
        l = m
      else:
        r = m - 1

    return l

  def _getOrderedPoints(self, side: int, points: list[list[int]]) -> list[list[int]]:
    """
    Returns the ordered points on the perimeter of a square of side length
    `side`, starting from left, top, right, and bottom boundaries.
    """
    left = sorted([(x, y) for x, y in points if x == 0 and y > 0])
    top = sorted([(x, y) for x, y in points if x > 0 and y == side])
    right = sorted([(x, y) for x, y in points if x == side and y < side],
                   reverse=True)
    bottom = sorted([(x, y) for x, y in points if y == 0], reverse=True)
    return left + top + right + bottom