Given N pairs, the task is to find the Kth smallest pair and the number of pairs less than the given pair (x, y).
Examples:
Input: pairs[][] = {{23, 20}, {23, 10}, {23, 30}, {12, 35}, {12, 22}}, K = 3, (x, y) = (23, 20)
Output: {23, 10} 3Input: pairs[][] = {{23, 20}, {23, 10}, {23, 30}, {12, 35}, {12, 22}}, K = 2, (x, y) = (12, 35)
Output: {12, 35} 1
Approach:
- Create a vector of pairs to store the given pairs.
- Sort the vector in increasing order of the first element and then in increasing order of the second element.
- Create a priority queue to store the pairs.
- Traverse the sorted vector and insert the pairs into the priority queue.
- When the size of the priority queue exceeds K, remove the top element.
- After traversing the vector, the top element of the priority queue will be the Kth smallest pair.
- To count the number of pairs less than the given pair (x, y), we can iterate over the vector and count the pairs that have a smaller first element than x or have the same first element but a smaller second element than y.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the Kth smallest pair and the number of pairs less than the given pairpair<pair<int, int>, int> findKthSmallestAndCount(vector<pair<int, int>> pairs, int K, pair<int, int> givenPair) { sort(pairs.begin(), pairs.end()); priority_queue<pair<int, int>> pq; int count = 0; for (pair<int, int> p : pairs) { if (p.first < givenPair.first || (p.first == givenPair.first && p.second < givenPair.second)) { count++; } pq.push(p); if (pq.size() > K) { pq.pop(); } } return make_pair(pq.top(), count);}// Driver codeint main() { vector<pair<int, int>> pairs = {{23, 20}, {23, 10}, {23, 30}, {12, 35}, {12, 22}}; int K = 3; pair<int, int> givenPair = {23, 20}; pair<pair<int, int>, int> result = findKthSmallestAndCount(pairs, K, givenPair); cout << "{" << result.first.first << ", " << result.first.second << "} " << result.second << endl; return 0;} |
Java
// Java Codeimport java.util.*;public class Main { // Function to find the Kth smallest pair and the number of pairs less than the given pair public static Map.Entry<Map.Entry<Integer, Integer>, Integer> findKthSmallestAndCount(List<Map.Entry<Integer, Integer>> pairs, int K, Map.Entry<Integer, Integer> givenPair) { pairs.sort((x, y) -> { // Custom comparison for sorting pairs based on first and second elements if (!x.getKey().equals(y.getKey())) { return x.getKey().compareTo(y.getKey()); } return x.getValue().compareTo(y.getValue()); }); PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((x, y) -> { // Custom comparison for the priority queue based on first and second elements if (!x.getKey().equals(y.getKey())) { return x.getKey().compareTo(y.getKey()); } return x.getValue().compareTo(y.getValue()); }); int count = 0; for (Map.Entry<Integer, Integer> p : pairs) { if (p.getKey() < givenPair.getKey() || (p.getKey().equals(givenPair.getKey()) && p.getValue() < givenPair.getValue())) { count++; } heap.add(p); if (heap.size() > K) { heap.poll(); } } return new AbstractMap.SimpleEntry<>(heap.peek(), count); } public static void main(String[] args) { List<Map.Entry<Integer, Integer>> pairs = new ArrayList<>(); pairs.add(new AbstractMap.SimpleEntry<>(23, 20)); pairs.add(new AbstractMap.SimpleEntry<>(23, 10)); pairs.add(new AbstractMap.SimpleEntry<>(23, 30)); pairs.add(new AbstractMap.SimpleEntry<>(12, 35)); pairs.add(new AbstractMap.SimpleEntry<>(12, 22)); int K = 3; Map.Entry<Integer, Integer> givenPair = new AbstractMap.SimpleEntry<>(23, 20); Map.Entry<Map.Entry<Integer, Integer>, Integer> result = findKthSmallestAndCount(pairs, K, givenPair); System.out.println("{" + result.getKey().getKey() + ", " + result.getKey().getValue() + "} " + result.getValue()); }}// This code is contributed by guptapratik |
Python3
import heapq# Function to find the Kth smallest pair and the number of pairs less than the given pairdef find_kth(pairs, K, given_pair): # Sort the pairs in ascending order pairs.sort() heap = [] count = 0 for p in pairs: if p[0] < given_pair[0] or (p[0] == given_pair[0] and p[1] < given_pair[1]): count += 1 heapq.heappush(heap, p) if len(heap) > K: heapq.heappop(heap) return (heap[0], count)# Driver codepairs = [(23, 20), (23, 10), (23, 30), (12, 35), (12, 22)]K = 3given_pair = (23, 20)result = find_kth(pairs, K, given_pair)print(f"{{{result[0][0]}, {result[0][1]}}} {result[1]}") |
C#
using System;using System.Collections.Generic;class Program{ // Function to find the Kth smallest pair and the number of pairs less than the given pair static Tuple<Tuple<int, int>, int> FindKthSmallestAndCount(List<Tuple<int, int>> pairs, int K, Tuple<int, int> givenPair) { pairs.Sort(); PriorityQueue<Tuple<int, int>> pq = new PriorityQueue<Tuple<int, int>>((x, y) => { // Custom comparison for the priority queue based on first and second elements if (x.Item1 != y.Item1) return x.Item1.CompareTo(y.Item1); return x.Item2.CompareTo(y.Item2); }); int count = 0; foreach (Tuple<int, int> p in pairs) { if (p.Item1 < givenPair.Item1 || (p.Item1 == givenPair.Item1 && p.Item2 < givenPair.Item2)) { count++; } pq.Enqueue(p); if (pq.Count > K) { pq.Dequeue(); } } return new Tuple<Tuple<int, int>, int>(pq.Peek(), count); } static void Main() { List<Tuple<int, int>> pairs = new List<Tuple<int, int>> { Tuple.Create(23, 20), Tuple.Create(23, 10), Tuple.Create(23, 30), Tuple.Create(12, 35), Tuple.Create(12, 22) }; int K = 3; Tuple<int, int> givenPair = Tuple.Create(23, 20); Tuple<Tuple<int, int>, int> result = FindKthSmallestAndCount(pairs, K, givenPair); Console.WriteLine("{" + result.Item1.Item1 + ", " + result.Item1.Item2 + "} " + result.Item2); } // Custom priority queue implementation class PriorityQueue<T> { private List<T> list; private Comparison<T> comparison; public int Count { get { return list.Count; } } public PriorityQueue(Comparison<T> comparison) { this.list = new List<T>(); this.comparison = comparison; } public void Enqueue(T item) { list.Add(item); int i = list.Count - 1; while (i > 0) { int parent = (i - 1) / 2; if (comparison(list[parent], item) <= 0) break; list[i] = list[parent]; i = parent; } list[i] = item; } public T Dequeue() { if (list.Count == 0) throw new InvalidOperationException("Queue is empty"); T front = list[0]; int last = list.Count - 1; T end = list[last]; list.RemoveAt(last); if (last > 0) { int i = 0; while (true) { int leftChild = i * 2 + 1; if (leftChild >= last) break; int rightChild = leftChild + 1; int child = (rightChild < last && comparison(list[rightChild], list[leftChild]) < 0) ? rightChild : leftChild; if (comparison(list[child], end) >= 0) break; list[i] = list[child]; i = child; } list[i] = end; } return front; } public T Peek() { if (list.Count == 0) throw new InvalidOperationException("Queue is empty"); return list[0]; } }} |
Javascript
// Function to find the Kth smallest pair and the number of pairs less than the given pairfunction findKthSmallestAndCount(pairs, K, givenPair) { pairs.sort((a, b) => { if (a[0] === b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }); let pq = []; let count = 0; for (let p of pairs) { if (p[0] < givenPair[0] || (p[0] === givenPair[0] && p[1] < givenPair[1])) { count++; } pq.push(p); if (pq.length > K) { pq.sort((a, b) => { if (a[0] === b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }); pq.pop(); } } return [{ first: pq[pq.length - 1][0], second: pq[pq.length - 1][1] }, count];}// Driver codelet pairs = [[23, 20], [23, 10], [23, 30], [12, 35], [12, 22]];let K = 3;let givenPair = [23, 20];let result = findKthSmallestAndCount(pairs, K, givenPair);console.log(`{${result[0].first}, ${result[0].second}} ${result[1]}`); |
Output
{23, 10} 3
Time Complexity: Sorting the pairs takes O(N log N) time, Inserting N pairs into a priority queue takes O(N log K) time, Traversing the vector to count the number of pairs less than the given pair takes O(N) time, Therefore, the total time complexity of the algorithm is O(N log N + N log K).
Space Complexity: The space used by the vector to store the pairs is O(N), The space used by the priority queue is O(K), Therefore, the total space complexity of the algorithm is O(N + K).
Naive Approach: The above problem can be solved by finding all pairs from array, and then printing the Kth smallest pair and the count of pairs less than (x, y) respectively. Policy Based Data Structure Approach: Following is a code showing policy-based data structure as MAP. It can add/remove pair of elements, can find the number of pairs less than (x, y), Kth smallest pair, etc in O(log N) time. The specialty of this map is that we have access to the indices that the pair of elements would have in a sorted 2D array. If the pair does not appear in the map, we get the position that the pair would have in the map.
CPP
// C++ implementation of the approach #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> #include <iostream> using namespace __gnu_pbds; using namespace std; // A new data structure is defined // Please refer https:// goo.gl/WVDL6g typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_map; // Driver code int main() { ordered_map om; om.insert({ 23, 20 }); om.insert({ 23, 10 }); om.insert({ 23, 30 }); om.insert({ 12, 35 }); om.insert({ 12, 22 }); int K = 2, x = 12, y = 35; cout << "{" << om.find_by_order(K - 1)->first << ", " << om.find_by_order(K - 1)->second << "}\n"; cout << om.order_of_key({ x, y }) << endl; return 0; } |
Java
// Java program for the above approachimport java.util.*;import java.io.*;import java.math.*;import java.lang.*;import static java.lang.Math.*;import static java.util.stream.Collectors.*;import java.util.TreeMap;// A new data structure is defined// Please refer https://goo.gl/WVDL6gclass Main { public static void main(String[] args) throws Exception { TreeMap<Pair, Integer> om = new TreeMap<>(); om.put(new Pair(23, 20), 0); om.put(new Pair(23, 10), 0); om.put(new Pair(23, 30), 0); om.put(new Pair(12, 35), 0); om.put(new Pair(12, 22), 0); int K = 2, x = 12, y = 35; System.out.println("{" + om.keySet().toArray()[K - 1] + "}"); System.out.println(om.headMap(new Pair(x, y)).size()); } static class Pair implements Comparable<Pair> { int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } public int compareTo(Pair other) { if (this.first != other.first) { return this.first - other.first; } return this.second - other.second; } public String toString() { return "(" + first + "," + second + ")"; } }}// This code is contributed by sdeadityasharma |
Python3
# Python code for the above approachfrom bisect import bisect_left, bisect_right# A new data structure is defined# using the built-in Python listom = []# Driver codeom.append((23, 20))om.append((23, 10))om.append((23, 30))om.append((12, 35))om.append((12, 22))K = 2x, y = 12, 35# sort the list of pairs in increasing orderom.sort()# find the K-th smallest pairprint("{}, {}".format(om[K - 1][0], om[K - 1][1]))# find the number of pairs less than (x, y)i = bisect_left(om, (x, y))print(i)# This code is contributed by adityashatmfh |
C#
using System;using System.Collections.Generic;using System.Linq;// A new data structure is defined// Please refer https://goo.gl/WVDL6gclass MainClass { public static void Main(string[] args) { SortedDictionary<Pair, int> om = new SortedDictionary<Pair, int>(); // Add elements to the sorted dictionary om.Add(new Pair(23, 20), 0); om.Add(new Pair(23, 10), 0); om.Add(new Pair(23, 30), 0); om.Add(new Pair(12, 35), 0); om.Add(new Pair(12, 22), 0); int K = 2, x = 12, y = 35; Console.WriteLine("{" + om.Keys.ToArray()[K - 1] + "}"); Console.WriteLine(om.Where(pair => pair.Key.first < x || (pair.Key.first == x && pair.Key.second < y)).Count()); } class Pair : IComparable<Pair> { public int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(Pair other) { if (this.first != other.first) { return this.first - other.first; } return this.second - other.second; } public override string ToString() { return "(" + first + "," + second + ")"; } }} |
Javascript
// JS code for the above approach// A new data structure is defined// using the built-in JavaScript arraylet om = [];// Driver codeom.push([23, 20]);om.push([23, 10]);om.push([23, 30]);om.push([12, 35]);om.push([12, 22]);let K = 2;let x = 12, y = 35;// sort the array of pairs in increasing orderom.sort();// find the K-th smallest pairconsole.log(`${om[K - 1][0]}, ${om[K - 1][1]}`);// find the number of pairs less than (x, y)let i = om.findIndex(([a, b]) => a > x || (a === x && b >= y));console.log(i); |
Output
{12, 35}
1
Time Complexity: O( log n )
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!
