Given an unsorted array arr[] of n integers and an integer k, the task is to find the kth largest element in the given index range [l, r]
Examples:
Input: arr[] = {5, 3, 2, 4, 1}, k = 4, l = 1, r = 5
Output: 4
4 will be the 4th element when arr[0…4] is sorted.
Input: arr[] = {1, 4, 2, 3, 5, 7, 6}, k = 3, l = 3, r = 6
Output: 5
Approach: A naive solution will be to sort the elements in the range and get the kth largest element, the time complexity of that solution will be nlog(n) for every query. We can solve each query in log(n) by using prefix array and binary search. All we have to do is maintain a 2d prefix array in which the ith row will contain number of elements less than equal to i in the same range as in the given array. After the prefix array is done all we need to do is a simple binary search over the prefix array. Hence the time complexity is drastically reduced.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 1001static int prefix[MAX][MAX];int ar[MAX];// Function to calculate the prefixvoid cal_prefix(int n, int arr[]){ int i, j; // Creating one based indexing for (i = 0; i < n; i++) ar[i + 1] = arr[i]; // Initializing and creating prefix array for (i = 1; i <= 1000; i++) { for (j = 0; j <= n; j++) prefix[i][j] = 0; for (j = 1; j <= n; j++) { // Creating a prefix array for every // possible value in a given range prefix[i][j] = prefix[i][j - 1] + (int)(ar[j] <= i ? 1 : 0); } }}// Function to return the kth largest element// in the index range [l, r]int ksub(int l, int r, int n, int k){ int lo, hi, mid; lo = 1; hi = 1000; // Binary searching through the 2d array // and only checking the range in which // the sub array is a part while (lo + 1 < hi) { mid = (lo + hi) / 2; if (prefix[mid][r] - prefix[mid][l - 1] >= k) hi = mid; else lo = mid + 1; } if (prefix[lo][r] - prefix[lo][l - 1] >= k) hi = lo; return hi;}// Driver codeint main(){ int arr[] = { 1, 4, 2, 3, 5, 7, 6 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; // Creating the prefix array // for the given array cal_prefix(n, arr); // Queries int queries[][3] = { { 1, n, 1 }, { 2, n - 2, 2 }, { 3, n - 1, 3 } }; int q = sizeof(queries) / sizeof(queries[0]); // Perform queries for (int i = 0; i < q; i++) cout << ksub(queries[i][0], queries[i][1], n, queries[i][2]) << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ static int MAX = 1001;static int prefix[][] = new int[MAX][MAX];static int ar[] = new int[MAX];// Function to calculate the prefixstatic void cal_prefix(int n, int arr[]){ int i, j; // Creating one based indexing for (i = 0; i < n; i++) ar[i + 1] = arr[i]; // Initializing and creating prefix array for (i = 1; i <= 1000; i++) { for (j = 0; j <= n; j++) prefix[i][j] = 0; for (j = 1; j <= n; j++) { // Creating a prefix array for every // possible value in a given range prefix[i][j] = prefix[i][j - 1] + (int)(ar[j] <= i ? 1 : 0); } }}// Function to return the kth largest element// in the index range [l, r]static int ksub(int l, int r, int n, int k){ int lo, hi, mid; lo = 1; hi = 1000; // Binary searching through the 2d array // and only checking the range in which // the sub array is a part while (lo + 1 < hi) { mid = (lo + hi) / 2; if (prefix[mid][r] - prefix[mid][l - 1] >= k) hi = mid; else lo = mid + 1; } if (prefix[lo][r] - prefix[lo][l - 1] >= k) hi = lo; return hi;}// Driver codepublic static void main(String args[]){ int arr[] = { 1, 4, 2, 3, 5, 7, 6 }; int n = arr.length; int k = 4; // Creating the prefix array // for the given array cal_prefix(n, arr); // Queries int queries[][] = { { 1, n, 1 }, { 2, n - 2, 2 }, { 3, n - 1, 3 } }; int q = queries.length; // Perform queries for (int i = 0; i < q; i++) System.out.println( ksub(queries[i][0], queries[i][1], n, queries[i][2]));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachMAX = 1001prefix = [[0 for i in range(MAX)] for j in range(MAX)]ar = [0 for i in range(MAX)]# Function to calculate the prefixdef cal_prefix(n, arr): # Creating one based indexing for i in range(n): ar[i + 1] = arr[i] # Initializing and creating prefix array for i in range(1, 1001, 1): for j in range(n + 1): prefix[i][j] = 0 for j in range(1, n + 1): # Creating a prefix array for every # possible value in a given range if ar[j] <= i: k = 1 else: k = 0 prefix[i][j] = prefix[i][j - 1] + k# Function to return the kth largest element# in the index range [l, r]def ksub(l, r, n, k): lo = 1 hi = 1000 # Binary searching through the 2d array # and only checking the range in which # the sub array is a part while (lo + 1 < hi): mid = int((lo + hi) / 2) if (prefix[mid][r] - prefix[mid][l - 1] >= k): hi = mid else: lo = mid + 1 if (prefix[lo][r] - prefix[lo][l - 1] >= k): hi = lo return hi# Driver codeif __name__ == '__main__': arr = [1, 4, 2, 3, 5, 7, 6] n = len(arr) k = 4 # Creating the prefix array # for the given array cal_prefix(n, arr) # Queries queries = [[1, n, 1], [2, n - 2, 2], [3, n - 1, 3]] q = len(queries) # Perform queries for i in range(q): print(ksub(queries[i][0], queries[i][1], n, queries[i][2])) # This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{ static int MAX = 1001;static int[,] prefix = new int[MAX,MAX];static int[] ar = new int[MAX];// Function to calculate the prefixstatic void cal_prefix(int n, int[] arr){ int i, j; // Creating one based indexing for (i = 0; i < n; i++) ar[i + 1] = arr[i]; // Initializing and creating prefix array for (i = 1; i <= 1000; i++) { for (j = 0; j <= n; j++) prefix[i, j] = 0; for (j = 1; j <= n; j++) { // Creating a prefix array for every // possible value in a given range prefix[i, j] = prefix[i, j - 1] + (int)(ar[j] <= i ? 1 : 0); } }}// Function to return the kth largest element// in the index range [l, r]static int ksub(int l, int r, int n, int k){ int lo, hi, mid; lo = 1; hi = 1000; // Binary searching through the 2d array // and only checking the range in which // the sub array is a part while (lo + 1 < hi) { mid = (lo + hi) / 2; if (prefix[mid, r] - prefix[mid, l - 1] >= k) hi = mid; else lo = mid + 1; } if (prefix[lo, r] - prefix[lo, l - 1] >= k) hi = lo; return hi;}// Driver codestatic void Main(){ int []arr = { 1, 4, 2, 3, 5, 7, 6 }; int n = arr.Length; //int k = 4; // Creating the prefix array // for the given array cal_prefix(n, arr); // Queries int [,]queries = { { 1, n, 1 }, { 2, n - 2, 2 }, { 3, n - 1, 3 } }; int q = queries.Length/queries.Rank-1; // Perform queries for (int i = 0; i < q; i++) Console.WriteLine( ksub(queries[i,0], queries[i,1], n, queries[i, 2]));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach$MAX = 101;$prefix = array_fill(0, $MAX, array_fill(0, $MAX, 0));$ar = array_fill(0, $MAX, 0);// Function to calculate the prefixfunction cal_prefix($n, $arr){ global $prefix,$ar,$MAX; // Creating one based indexing for ($i = 0; $i < $n; $i++) $ar[$i + 1] = $arr[$i]; // Initializing and creating prefix array for ($i = 1; $i <$MAX; $i++) { for ($j = 0; $j <= $n; $j++) $prefix[$i][$j] = 0; for ($j = 1; $j <= $n; $j++) { // Creating a prefix array for every // possible value in a given range $prefix[$i][$j] = $prefix[$i][$j - 1] + (int)($ar[$j] <= $i ? 1 : 0); } }}// Function to return the kth largest element// in the index range [l, r]function ksub($l, $r, $n, $k){ global $prefix, $ar, $MAX; $lo = 1; $hi = $MAX-1; // Binary searching through the 2d array // and only checking the range in which // the sub array is a part while ($lo + 1 < $hi) { $mid = (int)(($lo + $hi) / 2); if ($prefix[$mid][$r] - $prefix[$mid][$l - 1] >= $k) $hi = $mid; else $lo = $mid + 1; } if ($prefix[$lo][$r] - $prefix[$lo][$l - 1] >= $k) $hi = $lo; return $hi;} // Driver code $arr = array( 1, 4, 2, 3, 5, 7, 6 ); $n = count($arr); $k = 4; // Creating the prefix array // for the given array cal_prefix($n, $arr); // Queries $queries = array(array( 1, $n, 1 ), array( 2, $n - 2, 2 ), array( 3, $n - 1, 3 )); $q = count($queries); // Perform queries for ($i = 0; $i < $q; $i++) echo ksub($queries[$i][0], $queries[$i][1],$n, $queries[$i][2])."\n"; // This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of the approachlet MAX = 101;let prefix = new Array(MAX);for (let i = 0; i < MAX; i++) { prefix[i] = new Array(MAX).fill(0)}let ar = new Array(MAX).fill(0);// Function to calculate the prefixfunction cal_prefix(n, arr) { // Creating one based indexing for (let i = 0; i < n; i++) ar[i + 1] = arr[i]; // Initializing and creating prefix array for (let i = 1; i < MAX; i++) { for (let j = 0; j <= n; j++) prefix[i][j] = 0; for (let j = 1; j <= n; j++) { // Creating a prefix array for every // possible value in a given range prefix[i][j] = prefix[i][j - 1] + (ar[j] <= i ? 1 : 0); } }}// Function to return the kth largest element// in the index range [l, r]function ksub(l, r, n, k) { let lo = 1; let hi = MAX - 1; // Binary searching through the 2d array // and only checking the range in which // the sub array is a part while (lo + 1 < hi) { let mid = Math.floor((lo + hi) / 2); if (prefix[mid][r] - prefix[mid][l - 1] >= k) hi = mid; else lo = mid + 1; } if (prefix[lo][r] - prefix[lo][l - 1] >= k) hi = lo; return hi;}// Driver codelet arr = new Array(1, 4, 2, 3, 5, 7, 6);let n = arr.length;let k = 4;// Creating the prefix array// for the given arraycal_prefix(n, arr);// Querieslet queries = new Array(new Array(1, n, 1), new Array(2, n - 2, 2), new Array(3, n - 1, 3));let q = queries.length;// Perform queriesfor (let i = 0; i < q; i++) document.write(ksub(queries[i][0], queries[i][1], n, queries[i][2]) + "<br>");// This code is contributed by _saurabh_jaiswal</script> |
Output:
1 3 5
Time Complexity : O(n + q*log(MAX)) ,where n is the size of the array, q is the number of queries and MAX is the number of rows or columns of 2D prefix array.
Space Complexity : O(MAX*MAX) , to store elements in prefix matrix.
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!
