Given a list of items and their values. The task is to find top k items with the highest value. It is possible that two items have the same value, in that case item whose name comes first (lexicographically) will be given higher priority. Examples:
Input: items[] = {Bat, Gloves, Wickets, Ball}, values[] = {100, 50, 200, 100} k = 2 Output: Wickets Ball Wickets has the highest value. Bat, Ball has the same value but Ball comes first lexicographically.
Approach: This question can be solved by picking the items greedily according to the values. We will sort use the items list in the decreasing order of the values and in case of the same values items will be sorted lexicographical order increasing order. We will store the data in the form of pairs in a vector and will use an inbuilt sort function with boolean comparator function which will be used to compare two items. Below is the implementation of the above approach:
CPP
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Boolean Comparator Function// to compare two pairs of item-valuebool comp(pair<string, int> A, pair<string, int> B){ // Compare the name if the values are equal if (A.second == B.second) return A.first < B.first; // Else compare values return A.second > B.second;}// Driver codeint main(){ int k = 2; int n = 3; // Store data in a vector of Item-Value Pair vector<pair<string, int> > items; // inserting items-value pairs in the vector items.push_back(make_pair("Bat", 100)); items.push_back(make_pair("Gloves", 50)); items.push_back(make_pair("Wickets", 200)); items.push_back(make_pair("Ball", 100)); // Sort items using Inbuilt function sort(items.begin(), items.end(), comp); // Print top k values // or if n is less than k // Print all n items for (int i = 0; i < min(n, k); ++i) { cout << items[i].first << '\n'; } return 0;} |
Java
import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Main { // Boolean Comparator Function // to compare two pairs of item-value static class ItemComparator implements Comparator<Pair<String, Integer>> { @Override public int compare(Pair<String, Integer> A, Pair<String, Integer> B) { // Compare the name if the values are equal if (A.getValue().equals(B.getValue())) { return A.getKey().compareTo(B.getKey()); } // Else compare values return B.getValue() - A.getValue(); } } // Driver code public static void main(String[] args) { int k = 2; int n = 3; // Store data in a list of Item-Value Pair List<Pair<String, Integer>> items = new ArrayList<>(); // inserting items-value pairs in the list items.add(new Pair<>("Bat", 100)); items.add(new Pair<>("Gloves", 50)); items.add(new Pair<>("Wickets", 200)); items.add(new Pair<>("Ball", 100)); // Sort items using Inbuilt function Collections.sort(items, new ItemComparator()); // Print top k values // or if n is less than k // Print all n items for (int i = 0; i < Math.min(n, k); i++) { System.out.println(items.get(i).getKey()); } } // Pair class to represent item-value pairs static class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } }} |
Python3
# Python3 implementation of above approach# Boolean Comparator Function# to compare two pairs of item-valuedef comp(A, B): # Compare the name if the values are equal if (A[1] == B[1]): return A[0] < B[0] # Else compare values return A[1] > B[1]# Driver codek = 2n = 3# Store data in a list of Item-Value Pairitems = []# inserting items-value pairs in the listitems.append(("Bat", 100))items.append(("Gloves", 50))items.append(("Wickets", 200))items.append(("Ball", 100))# Sort items using Inbuilt functionitems.sort(key=lambda x: (-x[1], x[0]))# Print top k values# or if n is less than k# Print all n itemsfor i in range(min(n, k)): print(items[i][0])# This code is contributed by phasing17 |
Javascript
// JavaScript implementation of above approach// Boolean Comparator Function// to compare two pairs of item-valuefunction comp(A, B) { // Compare the name if the values are equal if (A[1] == B[1]) { return A[0] < B[0]; } // Else compare values return A[1] > B[1];}// Driver codelet k = 2;let n = 3;// Store data in a list of Item-Value Pairlet items = [];// inserting items-value pairs in the listitems.push(["Bat", 100]);items.push(["Gloves", 50]);items.push(["Wickets", 200]);items.push(["Ball", 100]);// Sort items using Inbuilt functionitems.sort(function(a, b) { return comp(a, b) ? -1 : 1;});// Print top k values// or if n is less than k// Print all n itemsfor (let i = 0; i < Math.min(n, k); i++) { console.log(items[i][0]);} |
C#
using System;using System.Collections.Generic;public class MainClass{ // Boolean Comparator Function // to compare two pairs of item-value static int ItemComparator(Pair<string, int> A, Pair<string, int> B) { // Compare the name if the values are equal if (A.Value.Equals(B.Value)) { return A.Key.CompareTo(B.Key); } // Else compare values return B.Value - A.Value; } // Driver code public static void Main() { int k = 2; int n = 3; // Store data in a list of Item-Value Pair List<Pair<string, int>> items = new List<Pair<string, int>>(); // inserting items-value pairs in the list items.Add(new Pair<string, int>("Bat", 100)); items.Add(new Pair<string, int>("Gloves", 50)); items.Add(new Pair<string, int>("Wickets", 200)); items.Add(new Pair<string, int>("Ball", 100)); // Sort items using Inbuilt function items.Sort(ItemComparator); // Print top k values // or if n is less than k // Print all n items for (int i = 0; i < Math.Min(n, k); i++) { Console.WriteLine(items[i].Key); } } // Pair class to represent item-value pairs public class Pair<K, V> { public K Key { get; } public V Value { get; } public Pair(K key, V value) { Key = key; Value = value; } }} |
Output:
Wickets Ball
Time Complexity: O(NlogN) Further Optimization : We can further optimize above solutions using Heap Data Structure. Please see k largest elements in an array.
Space Complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
