3464. Maximize the Distance Between Points on a Square LeetCode Solution
In this guide, you will get 3464. Maximize the Distance Between Points on a Square LeetCode Solution with the best time and space complexity. The solution to Maximize the Distance Between Points on a Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize the Distance Between Points on a Square
You are given an integer side, representing the edge length of a square with corners at (0, 0), (0, side), (side, 0), and (side, side) on a Cartesian plane.
You are also given a positive integer k and a 2D integer array points, where points[i] = [xi, yi] represents the coordinate of a point lying on the boundary of the square.
You need to select k elements among points such that the minimum Manhattan distance between any two points is maximized.
Return the maximum possible minimum Manhattan distance between the selected k points.
The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi – xj| + |yi – yj|.
Example 1:
Input: side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
Output: 2
Explanation:
Select all four points.
Example 2:
Input: side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4
Output: 1
Explanation:
Select the points (0, 0), (2, 0), (2, 2), and (2, 1).
Example 3:
Input: side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5
Output: 1
Explanation:
Select the points (0, 0), (0, 1), (0, 2), (1, 2), and (2, 2).
Constraints:
1 <= side <= 109
4 <= points.length <= min(4 * side, 15 * 103)
points[i] == [xi, yi]
The input is generated such that:
points[i] lies on the boundary of the square.
All points[i] are unique.
4 <= k <= min(25, points.length)
Complexity Analysis
Time Complexity: O(n\log\texttt{side})
Space Complexity: O(n)
3464. Maximize the Distance Between Points on a Square LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3464. Maximize the Distance Between Points on a Square LeetCode Solution in Java
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(p -> p[1]));
top.sort(Comparator.comparingInt(p -> p[0]));
right.sort((a, b) -> Integer.compare(b[1], a[1]));
bottom.sort((a, b) -> Integer.compare(b[0], a[0]));
List<int[]> ordered = new ArrayList<>();
ordered.addAll(left);
ordered.addAll(top);
ordered.addAll(right);
ordered.addAll(bottom);
return ordered;
}
} // code provided by PROGIEZ
3464. Maximize the Distance Between Points on a Square LeetCode Solution in Python
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 # code by PROGIEZ
