Data Modelling & AI Data Structure & Algorithm

Number of players whose rank is equal to or less than a given cutoff rank

23 June 2025

3

Given an array arr[] consisting of N integers and an integer R, denoting the cutoff rank, the task is to count the number of array elements with rank at most R such that the equal array element are ranked the same and distinct array elements are ranked based on their positions in the array arr[].

Examples:

Input: arr[] = {100, 50, 50, 25}, R = 3
Output: 3
Explanation:
The players are ranked as: {1, 2, 2, 4}. The players having ranked at most R(= 3) is {1, 2, 2}. Therefore, the total count is 3.

Input: arr[] = {2, 2, 3, 4, 5}, R = 4
Output: 5

Approach: The given problem can be solved by using the concept of Sorting. Follow the below step to solve this problem:

Sort the given array arr[] in decreasing order.
Initialize two variables, say rank as 1 to store the rank of the array elements and say count as 0 to store the required result.
Traverse the given array arr[], using the variable i, and perform the following steps:
- If the arr[i] is equal to the previous element then assign the same rank as the previous rank to the current element.
- Otherwise, assign the value of (count + 1)^th rank to the current element.
- If the rank is greater than R then break. Otherwise, increment the count by 1.
After completing the above steps, print the value of count as the answer.

Below is the implementation of the above approach:

C++

// C++  program for above approach
#include <algorithm>
#include <iostream>
using namespace std;
 
// Function to find the count of array
// elements having rank at most R
int countElements(int R, int N, int arr[])
{
 
  // Sort the array arr[] in the
  // decreasing order
  sort(arr, arr + N, greater<int>());
 
  // Stores the rank and required
  // count of array elements
  int rank = 1, count = 0;
 
  // store the previou element
  int prevScore = arr[0], score;
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
    score = arr[i];
 
    // If score is less than the
    // prevScore
    if (score < prevScore) {
      rank = count + 1;
    }
 
    // If the rank is greater than R
    if (rank > R) {
      break;
    }
 
    // Increment count by 1
    count++;
 
    // update prevscore
    prevScore = score;
  }
 
  // return count
  return count;
}
 
// Driver code
int main()
{
  int arr[] = { 100, 50, 50, 25 };
  int R = 2;
  int N = sizeof(arr) / sizeof(arr[0]);
  cout << countElements(R, N, arr);
  return 0;
}
 
// This code is contributed by Parth Manchanda

Java

// Java program for the above approach
import java.util.*;
 
class GFG 
{
  static void reverse(int a[])
  {
    int n = a.length;
    int[] b = new int[n];
    int j = n;
    for (int i = 0; i < n; i++) {
      b[j - 1] = a[i];
      j = j - 1;
    }
  }
 
  // Function to find the count of array
  // elements having rank at most R
  static int countElements(int R, int N, int[] arr)
  {
 
    // Sort the array arr[] in the
    // decreasing order
    Arrays.sort(arr);
    reverse(arr);
 
    // Stores the rank and required
    // count of array elements
    int rank = 1;
    int count = -1;
 
    // Stores the previous element
    int prevScore = arr[0];
 
    // Traverse the array
    for(int score : arr)
    {
 
      // If score is less than the
      // prevScore
      if (score < prevScore)
        rank = count + 1;
 
      // If the rank is greater than R
      if (rank > R)
        break;
 
      // Increment count by 1
      count = count + 1;
 
      // Update prevScore
      prevScore = score;
    }
 
    // Return the result
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 100, 50, 50, 25 };
    int R = 2;
    int N = arr.length;
 
    // Function Call
    System.out.println(countElements(R, N, arr));
  }
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program for the above approach
 
# Function to find the count of array
# elements having rank at most R
def countElements(R, N, arr):
 
    # Sort the array arr[] in the
    # decreasing order
    arr.sort(reverse = True)
 
    # Stores the rank and required
    # count of array elements
    rank = 1
    count = 0
 
    # Stores the previous element
    prevScore = arr[0]
 
    # Traverse the array
    for score in arr:
 
        # If score is less than the
        # prevScore
        if score < prevScore:
            rank = count + 1
 
        # If the rank is greater than R
        if rank > R:
            break
             
        # Increment count by 1
        count += 1
 
        # Update prevScore
        prevScore = score
 
    # Return the result
    return count
 
 
# Driver Code
arr = [100, 50, 50, 25]
R = 2
N = len(arr)
 
# Function Call
print(countElements(R, N, arr))

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the count of array
// elements having rank at most R
static int countElements(int R, int N, int[] arr)
{
     
    // Sort the array arr[] in the
    // decreasing order
    Array.Sort(arr);
    Array.Reverse(arr);
 
    // Stores the rank and required
    // count of array elements
    int rank = 1;
    int count = 0;
 
    // Stores the previous element
    int prevScore = arr[0];
 
    // Traverse the array
    foreach(int score in arr)
    {
         
        // If score is less than the
        // prevScore
        if (score < prevScore)
            rank = count + 1;
 
        // If the rank is greater than R
        if (rank > R)
            break;
 
        // Increment count by 1
        count = count + 1;
 
        // Update prevScore
        prevScore = score;
    }
     
    // Return the result
    return count;
}
 
 
// Driver code
static public void Main()
{
    int[] arr = { 100, 50, 50, 25 };
    int R = 2;
    int N = arr.Length;
 
    // Function Call
    Console.WriteLine(countElements(R, N, arr));
}
}
 
// This code is contributed by target_2.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the count of array
// elements having rank at most R
function countElements(R, N, arr)
{
     
    // Sort the array arr[] in the
    // decreasing order
    arr.sort(function(a, b){ return b - a; });
 
    // Stores the rank and required
    // count of array elements
    let rank = 1;
    let count = 0;
 
    // Stores the previous element
    let prevScore = arr[0];
 
    // Traverse the array
    for(let score of arr)
    {
         
        // If score is less than the
        // prevScore
        if (score < prevScore)
            rank = count + 1;
 
        // If the rank is greater than R
        if (rank > R)
            break;
 
        // Increment count by 1
        count = count + 1;
 
        // Update prevScore
        prevScore = score;
    }
     
    // Return the result
    return count;
}
 
// Driver Code
let arr = [ 100, 50, 50, 25 ];
let R = 2;
let N = arr.length;
 
// Function Call
document.write(countElements(R, N, arr));
 
// This code is contributed by lokeshpotta20
 
</script>

Output:

Time Complexity: O(N*log N)
Auxiliary Space: O(1)

Method 2:using a heap data structure

One method to solve the problem of finding the count of array elements having rank at most R is by using a heap data structure. This method involves creating a max heap of size R and traversing the array elements. For each element, if it is greater than the smallest element in the heap, then remove the smallest element from the heap and add the current element to the heap. At the end of the traversal, the count of elements in the heap is the required answer.

C++

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
int countElements(int R, int N, vector<int> arr)
{
    // Create a min heap of size R
    priority_queue<int, vector<int>, greater<int> > heap;
 
    for (int i = 0; i < R; i++) {
        heap.push(arr[i]);
    }
 
    // Traverse the array elements
    for (int i = R; i < N; i++) {
        if (arr[i] > heap.top()) {
            heap.pop();
            heap.push(arr[i]);
        }
    }
 
    // Return the count of elements in heap
    return heap.size();
}
 
// Driver Code
int main()
{
    vector<int> arr = { 100, 50, 50, 25 };
    int R = 2;
    int N = arr.size();
 
    // Function Call
    cout << countElements(R, N, arr);
    return 0;
}

Java

import java.util.PriorityQueue;
import java.util.Vector;
 
public class Main {
    public static int countElements(int R, int N,
                                    Vector<Integer> arr)
    {
 
        // Create a min heap of size R
        PriorityQueue<Integer> heap
            = new PriorityQueue<Integer>();
 
        for (int i = 0; i < R; i++) {
            heap.add(arr.get(i));
        }
 
        // Traverse the array elements
        for (int i = R; i < N; i++) {
            if (arr.get(i) > heap.peek()) {
                heap.poll();
                heap.add(arr.get(i));
            }
        }
 
        // Return the count of elements in heap
        return heap.size();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        Vector<Integer> arr = new Vector<Integer>();
        arr.add(100);
        arr.add(50);
        arr.add(50);
        arr.add(25);
        int R = 2;
        int N = arr.size();
 
        // Function Call
        System.out.println(countElements(R, N, arr));
    }
}

Python3

import heapq
 
 
def countElements(R, N, arr):
 
    # Create a max heap of size R
    heap = []
 
    for i in range(R):
        heapq.heappush(heap, arr[i])
 
    # Traverse the array elements
    for i in range(R, N):
        if arr[i] > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, arr[i])
 
    # Return the count of elements in heap
    return len(heap)
 
 
# Driver Code
arr = [100, 50, 50, 25]
R = 2
N = len(arr)
 
# Function Call
print(countElements(R, N, arr))

C#

using System;
using System.Collections.Generic;
 
public class Program {
    public static int CountElements(int R, int N,
                                    List<int> arr)
    {
        // Create a min heap of size R
        var heap = new PriorityQueue<int>();
        for (int i = 0; i < R; i++) {
            heap.Enqueue(arr[i]);
        }
 
        // Traverse the array elements
        for (int i = R; i < N; i++) {
            if (arr[i] > heap.Peek()) {
                heap.Dequeue();
                heap.Enqueue(arr[i]);
            }
        }
 
        // Return the count of elements in heap
        return heap.Count;
    }
 
    // Driver Code
    public static void Main()
    {
        var arr = new List<int>{ 100, 50, 50, 25 };
        int R = 2;
        int N = arr.Count;
 
        // Function Call
        Console.WriteLine(CountElements(R, N, arr));
    }
}
 
public class PriorityQueue<T> where T : IComparable<T> {
    private List<T> list;
    public PriorityQueue() { list = new List<T>(); }
 
    public void Enqueue(T value)
    {
        list.Add(value);
        int i = list.Count - 1;
        while (i > 0) {
            int j = (i - 1) / 2;
            if (list[j].CompareTo(list[i]) <= 0) {
                break;
            }
            T temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i = j;
        }
    }
 
    public T Dequeue()
    {
        int last = list.Count - 1;
        T frontItem = list[0];
        list[0] = list[last];
        list.RemoveAt(last);
 
        last--;
 
        int i = 0;
        while (true) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            if (left > last) {
                break;
            }
            int j = left;
            if (right <= last
                && list[right].CompareTo(list[left]) < 0) {
                j = right;
            }
            if (list[i].CompareTo(list[j]) <= 0) {
                break;
            }
            T temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i = j;
        }
        return frontItem;
    }
 
    public T Peek()
    {
        T frontItem = list[0];
        return frontItem;
    }
 
    public int Count
    {
        get { return list.Count; }
    }
}
// This code is contributed by user_dtewbxkn77n

Javascript

function countElements(R, N, arr) {
  let heap = new PriorityQueue();
  for (let i = 0; i < R; i++) {
    heap.add(arr[i]);
  }
  // Traverse the array elements
  for (let i = R; i < N; i++) {
    if (arr[i] > heap.peek()) {
      heap.poll();
      heap.add(arr[i]);
    }
  }
  return heap.size();
}
// Create a min heap of size R
class PriorityQueue {
  constructor() {
    this.heap = [];
  }
 
  add(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
 
  poll() {
    if (this.heap.length === 0) {
      return null;
    }
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }
 
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }
 
  bubbleUp(idx) {
    const element = this.heap[idx];
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.heap[parentIdx];
      if (element >= parent) {
        break;
      }
      this.heap[parentIdx] = element;
      this.heap[idx] = parent;
      idx = parentIdx;
    }
  }
 
  bubbleDown(idx) {
    const element = this.heap[idx];
    const length = this.heap.length;
    while (true) {
      const leftChildIdx = idx * 2 + 1;
      const rightChildIdx = idx * 2 + 2;
      let leftChild, rightChild;
      let swap = null;
 
      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx];
        if (leftChild < element) {
          swap = leftChildIdx;
        }
      }
 
      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx];
        if (
          (swap === null && rightChild < element) ||
          (swap !== null && rightChild < leftChild)
        ) {
          swap = rightChildIdx;
        }
      }
 
      if (swap === null) {
        break;
      }
      this.heap[idx] = this.heap[swap];
      this.heap[swap] = element;
      idx = swap;
    }
  }
 
  size() {
       
    // Return the count of elements in heap
    return this.heap.length;
  }
}
// Driver Code
let arr = [100, 50, 50, 25];
let R = 2;
let N = arr.length;
// Function Call
console.log(countElements(R, N, arr));
 
// This code is contributed by shiv1o43g

Output

The time complexity of the above implementation using the heapq module is O(NlogR), where N is the length of the input array and R is the given rank.

The auxiliary space complexity of this implementation is O(R), since we are using a max heap of size R to keep track of the top R elements

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!

Number of players whose rank is equal to or less than a given cutoff rank

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

7 Years, 2 Major Rebuilds, 40K+ GitHub Stars: The Rise of Milvus as the Leading Open-Source Vector Database

Gemini 3 Pro + Milvus: Building a More Robust RAG With Advanced Reasoning and Multimodal Power

Multimodal RAG Made Simple: RAG-Anything + Milvus Instead of 20 Separate Tools

LEAVE A REPLY Cancel reply

Most Popular

This is the smartwatch to get if you’re looking for something different

Google’s ‘Preferred Sources’ is finally going global

YouTube TV will give users more control over their content with tailored subscriptions

7 Years, 2 Major Rebuilds, 40K+ GitHub Stars: The Rise of Milvus as the Leading Open-Source Vector Database

EDITOR PICKS

This is the smartwatch to get if you’re looking for something different

Google’s ‘Preferred Sources’ is finally going global

YouTube TV will give users more control over their content with tailored subscriptions

POPULAR POSTS

This is the smartwatch to get if you’re looking for something different

Google’s ‘Preferred Sources’ is finally going global

YouTube TV will give users more control over their content with tailored subscriptions

POPULAR CATEGORY

ABOUT US

FOLLOW US