High Temperature

Easy
0/40
1 upvote
Asked in company
Intuit

Problem statement

You are given data representing a list of cities. Each city has a name and a temperature. You are also given an integer 'K'.


The task is to find the top 'K' cities with the highest temperatures from this data.


For Example : 
Let 'N' = 4, 'K' = 2. The cities are:
Delhi 30
Mumbai 35
Chennai 32
Kolkata 28
The cities sorted by temperature descending are: Mumbai (35), Chennai (32), Delhi (30), Kolkata (28).
The top 2 cities are Mumbai and Chennai.
Therefore, the answer is Mumbai Chennai.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two integers, 'N' and 'K'.
The following 'N' lines each contain a string representing the city name and an integer representing its temperature, separated by a space.
Output Format : 
Return a list of strings representing the names of the top 'K' cities with the highest temperatures, sorted in descending order of temperature. If two cities have the same temperature, their relative order in the output doesn't matter.
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
1 <= 'N' <= 10^5
1 <= 'K' <= 'N'
-100 <= temperature <= 100
City names consist of lowercase and uppercase English letters.

Time Limit: 1 sec
Sample Input 1 :
3 1
Pune 25
Bangalore 28
Hyderabad 26
Sample Output 1 :
Bangalore
Explanation of sample input 1 :
There are 3 cities: Pune (25), Bangalore (28), and Hyderabad (26). We need the top K = 1 city.
Sorting the cities by temperature descending gives: Bangalore (28), Hyderabad (26), Pune (25).
The top 1 city is Bangalore.
Thus, the answer is Bangalore.
Sample Input 2 :
4 4
Jaipur 40
Agra 38
Varanasi 39
Lucknow 37
Sample Output 2 :
Jaipur Varanasi Agra Lucknow
Hint

Sorting the cities based on their temperature will help in easily identifying the top 'K' cities.

Approaches (1)
Sorting

Approach:

  • Read the input data, storing each city's name and temperature.
  • Sort the cities based on their temperature in descending order.
  • Take the first 'K' cities from the sorted list.
  • Extract the names of these 'K' cities.

Algorithm:

  • Read the integers 'N' and 'K'.
  • Create a list of pairs (temperature, city_name) to store the city data.
  • Iterate 'N' times:
    • Read the city name and temperature.
    • Add the pair (temperature, city_name) to the list.
  • Sort the list in descending order based on the temperature.
  • Create an empty list called 'top_cities_names'.
  • Iterate using 'i' from 0 to 'K - 1':
    • Add the city name from the i-th pair in the sorted list to 'top_cities_names'.
  • Return the 'top_cities_names' list.
Time Complexity

O(N log N), where 'N' is the number of cities.

 

We read 'N' cities and store them, which takes O(N) time. Sorting the list of 'N' cities takes O(N log N) time. Extracting the top 'K' city names takes O(K) time. Since K <= N and O(N log N) dominates O(N) and O(K), the overall time complexity is of the order O(N log N).

Space Complexity

O(N), where 'N' is the number of cities.

 

We store the data for 'N' cities in a list of pairs, which requires O(N) space. The resulting list of top 'K' city names requires O(K) space. Since K <= N, the overall space complexity is of the order O(N).

Code Solution
(100% EXP penalty)
High Temperature
Full screen
Console