Sponsored
Sponsored
This approach involves sorting the x-coordinates of the points and then finding the maximum difference between consecutive sorted x-coordinates. This difference gives the widest vertical area between any two points.
Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(n), due to the additional array holding the sorted x-coordinates.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int maxWidthOfVerticalArea(int points[][2], int pointsSize) {
9 int xCoords[pointsSize];
10 for (int i = 0; i < pointsSize; i++) {
11 xCoords[i] = points[i][0];
12 }
13 qsort(xCoords, pointsSize, sizeof(int), compare);
14 int maxWidth = 0;
15 for (int i = 1; i < pointsSize; i++) {
16 int width = xCoords[i] - xCoords[i - 1];
17 if (width > maxWidth) {
18 maxWidth = width;
19 }
20 }
21 return maxWidth;
22}
23
24int main() {
25 int points[][2] = {{3, 1}, {9, 0}, {1, 0}, {1, 4}, {5, 3}, {8, 8}};
26 int pointsSize = sizeof(points) / sizeof(points[0]);
27 printf("%d\n", maxWidthOfVerticalArea(points, pointsSize));
28 return 0;
29}This solution uses a simple array to extract x-coordinates, sorts it, and finds the maximum gap between consecutive sorted x-coordinates. The function qsort() is used for sorting, and a loop is used after sorting to determine the maximum width.
Although not commonly necessary due to the constraints provided, if x-coordinates were to be over a smaller range, a variant of bucket sort could be used to place x-coordinates in a collection of buckets. This helps find consecutive x-coordinate gaps in nearly constant time, potentially improving performance by eliminating the general-purpose sort with more specialized data placement.
Time Complexity: O(n) expected when bucket conditions are met.
Space Complexity: O(m) where m is the bucket range size.
For tiny x-coordinate ranges, this approach might compete with general sorting or hashing tactics, but the practical use case here doesn't demand such specificity.