Given N ranges of the form L to R, the task is to find the maximum occurred integer in all the ranges. If more than one such integer exists, print the smallest one.
Examples:
Input: points[] = { {1, 6}, {2, 3}, {2, 5}, {3, 8} }
Output: 3
Explanation :
1 occurs in 1 range {1, 6}
2 occurs 3 in 3 range {1, 6}, {2, 3}, {2, 5}
3 occurs 4 in 4 range {1, 6}, {2, 3}, {2, 5}, {3, 8}
4 occurs 3 in 3 range {1, 6}, {2, 5}, {3, 8}
5 occurs 3 in 3 range {1, 6}, {2, 5}, {3, 8}
6 occurs 2 in 2 range {1, 6}, {3, 8}
7 occurs 1 in 1 range {3, 8}
8 occurs 1 in 1 range {3, 8}
Hence, the most occurred integer is 3.Input: points[] = { {1, 4}, {1, 9}, {1, 2}};
Output: 1
Approach: This is the improvised approach of Maximum occurred integer in n ranges. The main idea is to use coordinate compression using Hashing. So there is no need to create a frequency array that will exceed the memory limit for large ranges. Below is the step by step algorithm to solve this problem:
- Initialize an ordered map name points, to keep track of the starting and ending points of the given ranges.
- Increase the value of the point[L] by 1, for every starting index of the given range.
- Decrease the value of the point[R+1] by 1, for every ending index of the given range.
- Iterate the map in the increasing order of value of points. Note that the frequency[current point] = frequency[previous point] + points[current point]. Maintain the value of the frequency of the current point in a variable cur_freq.
- The point with the maximum value of cur_freq will be the answer.
- Store the index and return it.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to print the most// occurred element in given rangesvoid maxOccurring(int range[][2], int n){ // STL map for storing start // and end points map<int, int> points; for (int i = 0; i < n; i++) { int l = range[i][0]; int r = range[i][1]; // Increment at starting point points[l]++; // Decrement at ending point points[r + 1]--; } // Stores current frequency int cur_freq = 0; // Store element with maximum frequency int ans = 0; // Frequency of the current ans int freq_ans = 0; for (auto x : points) { // x.first denotes the current // point and x.second denotes // points[x.first] cur_freq += x.second; // If frequency of x.first is // greater that freq_ans if (cur_freq > freq_ans) { freq_ans = cur_freq; ans = x.first; } } // Print Answer cout << ans;}// Driver codeint main(){ int range[][2] = { { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } }; int n = sizeof(range) / sizeof(range[0]); // Function call maxOccurring(range, n); return 0;} |
Java
// Java program of the above approachimport java.util.*;class GFG{// Function to print the most// occurred element in given rangesstatic void maxOccurring(int range[][], int n){ // STL map for storing start // and end points HashMap<Integer,Integer> points = new HashMap<Integer,Integer>(); for (int i = 0; i < n; i++) { int l = range[i][0]; int r = range[i][1]; // Increment at starting point if(points.containsKey(l)){ points.put(l, points.get(l)+1); } else{ points.put(l, 1); // Decrement at ending point if(points.containsKey(r + 1)){ points.put(r + 1, points.get(r + 1)-1); } } } // Stores current frequency int cur_freq = 0; // Store element with maximum frequency int ans = 0; // Frequency of the current ans int freq_ans = 0; for (Map.Entry<Integer,Integer> entry :points.entrySet()) { // x.first denotes the current // point and x.second denotes // points[x.first] cur_freq += entry.getValue(); // If frequency of x.first is // greater that freq_ans if (cur_freq > freq_ans) { freq_ans = cur_freq; ans = entry.getKey(); } } // Print Answer System.out.print(ans);}// Driver codepublic static void main(String[] args){ int range[][] = { { 1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } }; int n = range.length; // Function call maxOccurring(range, n);}}// This code is contributed by Princi Singh |
Python3
# Python 3 program of the above approach# Function to print the most# occurred element in given rangesdef maxOccurring(range1, n): # STL map for storing start # and end points points = {} for i in range(n): l = range1[i][0] r = range1[i][1] # Increment at starting point if l in points: points[l] += 1 else: points[l] = 1 # Decrement at ending point if r+1 in points: points[r + 1] -= 1 else: points[r+1] = 0 # Stores current frequency cur_freq = 0 # Store element with maximum frequency ans = 0 # Frequency of the current ans freq_ans = 0 for key,value in points.items(): # x.first denotes the current # point and x.second denotes # points[x.first] cur_freq += value # If frequency of x.first is # greater that freq_ans if (cur_freq > freq_ans): freq_ans = cur_freq ans = key # Print Answer print(ans)# Driver codeif __name__ == '__main__': range1 = [[1, 6],[2, 3],[2, 5],[3, 8]] n = len(range1) # Function call maxOccurring(range1, n) # This code is contributed by ipg2016107. |
C#
// C# program of the above approachusing System;using System.Collections.Generic;class GFG{// Function to print the most// occurred element in given rangesstatic void maxOccurring(int [,]range, int n){ // STL map for storing start // and end points Dictionary<int, int> points = new Dictionary<int,int>(); for (int i = 0; i < n; i++) { int l = range[i,0]; int r = range[i,1]; // Increment at starting point if(points.ContainsKey(l)) points[l]++; else points.Add(l,1); // Decrement at ending point if(points.ContainsKey(r+1)) points[r + 1]--; else points.Add(r+1,0); } // Stores current frequency int cur_freq = 0; // Store element with maximum frequency int ans = 0; // Frequency of the current ans int freq_ans = 0; foreach(KeyValuePair<int,int> entry in points) { // x.first denotes the current // point and x.second denotes // points[x.first] cur_freq += entry.Value; // If frequency of x.first is // greater that freq_ans if (cur_freq > freq_ans) { freq_ans = cur_freq; ans = entry.Key; } } // Print Answer Console.Write(ans);}// Driver codepublic static void Main(){ int [,]range = {{1, 6 }, { 2, 3 }, { 2, 5 }, { 3, 8 } }; int n = 4; // Function call maxOccurring(range, n);}}// This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to print the most // occurred element in given ranges function maxOccurring(range, n) { // STL map for storing start // and end points let points = new Map(); for (let i = 0; i < n; i++) { let l = range[i][0]; let r = range[i][1]; // Increment at starting point if (points.has(l)) points.set(points.get(l), points.get(l) + 1); else points.set(l, 1); // Decrement at ending point if (points.has(r + 1)) { points.set(points.get(r + 1), points.get(r + 1) - 1); } } // Stores current frequency let cur_freq = 0; // Store element with maximum frequency let ans = 0; // Frequency of the current ans let freq_ans = 0; for (let [key, value] of points) { // x.first denotes the current // point and x.second denotes // points[x.first] cur_freq = cur_freq + value; // If frequency of x.first is // greater that freq_ans if (cur_freq > freq_ans) { freq_ans = cur_freq; ans = key; } } // Print Answer document.write(ans); } // Driver code let range = [[1, 6], [2, 3], [2, 5], [3, 8]]; let n = range.length; // Function call maxOccurring(range, n);// This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(n Logn)
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!
