CODEWITHSUNDEEP
algorithm
Avishek Ganguli
Avishek Ganguli

Reputation: 41

Finding a better than Brute Force algorithm

The problem is as follows: Given a stream of data with names of people, their height and their weight, for each employee E, find the group of employees that are taller and weigh more than E.

Obviously, this can be brute forced in O(n^2). Is this the best you can do though? If it's possible to do better, what would be the algorithm ?

Upvotes: 2

Views: 820

Answers (2)

Petar Petrovic
Petar Petrovic

Reputation: 414

If we draw a point (height_i, weight_i) on a 2D plane for every employee i, the query of employee i becomes 2D orthogonal range query, i.e. finding points within this rectangle height_i < height <= height_max and weight_i < weight <= weight_max.

From wiki[1], you can have an algorithm with time complexity O(n log log n + k) where k is the size of output.

Edit: In worst case, k can be in order of n^2

1: https://en.wikipedia.org/wiki/Range_searching#Orthogonal_range_searching

Upvotes: 3

hexaflexagonal
hexaflexagonal

Reputation: 266

If you sort the input on either height or weight, you can go through checking only the subsequent entries for each entry, so you can do (l-1) + (l-2) + (l-3) + ... + 1 comparisons instead of l * (l - 1). Obviously this is still quadratic, though. As ruakh pointed out in their comment, the output size tells us that this is the best we can do (imagine the case where every person in the sorted list is shorter and weighs less than every subsequent person).

Upvotes: 2

Related Questions