SORTCOORD - Editorial

editorial
1

Prerequisites: Basics C++ STL

Problem:
Given a set of 2D coordinates represented as pairs of integers (x, y), sort these coordinates based on their distance from the origin (0, 0).

Solution Approach:
The core idea of the solution is to compute the squared distances of each 2D coordinate from the origin and then sort these coordinates based on these squared distances. By using squared distances instead of actual distances, we avoid the computational overhead of square root operations, leading to faster execution.

  1. We first calculate the squared distance of each coordinate using the distance_squared function and store them along with their indices in a separate vector.
  2. Then, we sort this vector of distances. As the distances are squared, sorting them will effectively sort the original coordinates based on their distances from the origin.
  3. Finally, we create a result vector to rearrange the original coordinates based on the sorted indices from the distances vector, giving us the sorted coordinates based on their distances from the origin.

Time Complexity:
O(N log N) due to sorting.

Space Complexity:
O(N)