Let A[1..n] be an array of points in the plane, where A[i] contains the coordina

ID: 3705797 • Letter: L

Question

Let A[1..n] be an array of points in the plane, where A[i] contains the coordinates (xi, yi) of a point pi, for i = 1, . . . , n. Give an O(n lg n) time algorithm that determines whether any two points in A are identical(that is, have the same x and y coordinates).

Remarks:

If needed, you may assume that sorting n numbers can be done in time O(n lg n) (e.g., using Heap Sort). If you need to sort, you can directly apply such a sorting algorithm (without writing the pseudocode), and claim that it runs in O(n lg n) time, where n is the number of elements/numbers being sorted. When asked to give an algorithm that meets a certain time bound, you need to give the algorithm (pseudocode/description) and analyze its running time to show that it meets the required bound.

Explanation / Answer

Hi Dear,

Please find my answer:

You are given an array of points, A[], where each A[i] is a point.

Say , Point class is
class Point{
int x, int y;
}

Point A[] = new Point[n];

This means, A is an array of n point objects

inorder to find identical points (points having similar coordinates.) we can sort the points.

By sorting I mean, we can sort the points by using their x coordinates or, y coordines.

Eg, I have the below list of points in the array

(1,4)
(6,4)
(4,3)
(9,-6)
(6,4)
(2,8)

When you sort the points according to their x coordinates, you will get

(1,4), (2,8), (4,3), (6,4), (6,4), (9,-6)

If you observe the x coordintes, they are in sorted order.

You can also see that identical points (6,4) are adjacent.

So, inorder to find the identical points, you have to first sort the points. We have sorting algorithms with complexity O(nlogN)

Once we sort the points, we can iterate through the sorted array and check if two adjacent points are identical.

So total time complexity is O(nlogn) + O(n) = O(nlogn)

Please DONT forgot to rate my answer. We are working hard for you Guys!!

Navigate

Let A[1..n] be an array of n distinct numbers. (i, j) is called an inversion of

Let A[1..n] be an array of positive integers (A is not sorted). Pinocchio claims

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let A[1..n] be an array of points in the plane, where A[i] contains the coordina

Question

Explanation / Answer

Related Questions

Navigate