Find maximum frequency of any point across all ranges
Given a 2D array ranges[][] of size N denoting N ranges of points. Find the maximum frequency of any point across all the ranges.
Examples:
Input: ranges[][] = {{1, 4}, {3, 7}, {9, 10}, {2, 11}, {4, 6}}
Output: 4
Explanation:
- Point 1 occurs 1 times
- Point 2 occurs 2 times
- Point 3 occurs 3 times
- Point 4 occurs 4 times
- Point 5 occurs 3 times
- Point 6 occurs 3 times
- Point 7 occurs 2 times
- Point 8 occurs 1 times
- Point 9 occurs 2 times
- Point 10 occurs 2 times
- Point 11 occurs 1 times
Hence, the maximum frequency of any point is 4.
Input: ranges[][] = {{2, 6}, {3, 7}, {1, 3}, {8, 8}}
Output: 3
- Point 1 occurs 1 times
- Point 2 occurs 2 times
- Point 3 occurs 3 times
- Point 4 occurs 2 times
- Point 5 occurs 2 times
- Point 6 occurs 2 times
- Point 7 occurs 1 times
- Point 8 occurs 1 times
Hence, the maximum frequency of any point is 3.
Approach: To solve the problem, follow the below idea:
Create a vector of pair of integer and character ( β+β / β-β). Traverse the array of segments, push the starting point of the segment as (element, β+β) and ending point of the segment as (element, β-β). Sort the array on the basis of the first element of pair. Now traverse the array again and increment counter every time you encounter a β+β otherwise decrease the counter. Store the maximum result in another variable.
Step-by-step algorithm:
- Create a pair of integer and character(β+β / β-β).
- Iterate through the entire segment array.
- For starting point of the current segment push it in our vector of pair as {point, β+β}.
- For ending point of the current segment push it in our vector of pair as {point, β-β}.
- Sort the vector of pairs.
- Maintain a counter and maximum value.
- If character is β+β increment the counter otherwise decrement it and store the maximum.
- The maximum will the answer i.e. the maximum frequency of the point shared maximum number of times.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N = 5;
vector<array<int, 2> > ranges{
{ 1, 5 }, { 3, 7 }, { 9, 10 }, { 2, 11 }, { 4, 6 }
};
vector<pair<int, char> > points;
for (int i = 0; i < N; i++) {
points.push_back({ ranges[i][0], '+' });
points.push_back({ ranges[i][1], '-' });
}
sort(begin(points), end(points));
int mx = 0, cnt = 0;
for (int i = 0; i < (int)points.size(); i++) {
if (points[i].second == '+')
cnt++;
else
cnt--;
mx = max(mx, cnt);
}
cout << "The maximum frequency of the point that is "
"shared the most is: "
<< mx << '\n';
return 0;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
int N = 5;
List<int[]> ranges = new ArrayList<>(Arrays.asList(
new int[]{1, 5}, new int[]{3, 7}, new int[]{9, 10}, new int[]{2, 11}, new int[]{4, 6}
));
List<Pair<Integer, Character>> points = new ArrayList<>();
for (int i = 0; i < N; i++) {
points.add(new Pair<>(ranges.get(i)[0], '+'));
points.add(new Pair<>(ranges.get(i)[1], '-'));
}
// Sorting the points based on their values
Collections.sort(points, Comparator.comparingInt(Pair::getKey));
int mx = 0, cnt = 0;
for (int i = 0; i < points.size(); i++) {
if (points.get(i).getValue() == '+') {
cnt++;
} else {
cnt--;
}
mx = Math.max(mx, cnt);
}
System.out.println("The maximum frequency of the point that is " +
"shared the most is: " + mx);
}
}
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;
}
}
// This code is contributed by shivamgupta0987654321
# Given input
N = 5
ranges = [
[1, 5],
[3, 7],
[9, 10],
[2, 11],
[4, 6]
]
points = []
# Convert ranges into points with signs
for i in range(N):
points.append((ranges[i][0], '+'))
points.append((ranges[i][1], '-'))
# Sort the points based on their positions
points.sort()
# Initialize variables for maximum frequency and current count
mx = 0
cnt = 0
# Iterate through the sorted points to find maximum frequency
for i in range(len(points)):
if points[i][1] == '+':
cnt += 1
else:
cnt -= 1
mx = max(mx, cnt)
# Display the result
print("The maximum frequency of the point that is shared the most is:", mx)
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
int N = 5;
// Define the ranges as pairs (start, end)
List<int[]> ranges = new List<int[]>
{
new int[] {1, 5}, new int[] {3, 7}, new int[] {9, 10}, new int[] {2, 11}, new int[] {4, 6}
};
// Create a list to store points and their type (+ or -)
List<Tuple<int, char>> points = new List<Tuple<int, char>>();
// Fill the points list by converting ranges to points with their respective type
for (int i = 0; i < N; i++)
{
points.Add(new Tuple<int, char>(ranges[i][0], '+'));
points.Add(new Tuple<int, char>(ranges[i][1], '-'));
}
// Sort the points based on their values
points = points.OrderBy(p => p.Item1).ToList();
int mx = 0; // Variable to store the maximum frequency
int cnt = 0; // Variable to keep track of the current frequency
// Traverse through the sorted points to find the maximum frequency
for (int i = 0; i < points.Count; i++)
{
if (points[i].Item2 == '+')
cnt++;
else
cnt--;
// Update the maximum frequency
mx = Math.Max(mx, cnt);
}
// Print the result
Console.WriteLine("The maximum frequency of the point that is shared the most is: " + mx);
}
}
function main() {
// Define the number of ranges
const N = 5;
// Define the ranges as an array of arrays
const ranges = [
[1, 5],
[3, 7],
[9, 10],
[2, 11],
[4, 6]
];
// Initialize an array to store points
const points = [];
// Iterate over each range and add its start and end points to the points array
for (let i = 0; i < N; i++) {
points.push([ranges[i][0], '+']); // Start point with '+'
points.push([ranges[i][1], '-']); // End point with '-'
}
// Sort the points array based on their positions
points.sort((a, b) => a[0] - b[0]);
// Initialize variables for maximum frequency and current count
let mx = 0,
cnt = 0;
// Iterate over each point and update count based on whether it's a start or end point
for (let i = 0; i < points.length; i++) {
if (points[i][1] === '+') { // Start point
cnt++;
} else { // End point
cnt--;
}
// Update the maximum frequency
mx = Math.max(mx, cnt);
}
// Print the result
console.log("The maximum frequency of the point that is shared the most is: " + mx);
}
// Call the main function to execute the code
main();
Output
The maximum frequency of the point that is shared the most is: 4
Time Complexity: O(N log N), where N is the size of ranges[][].
Auxiliary Space: O(N)