### Maximum occurred integer in n ranges

Given n ranges in the form of Start Number and End Number in Two Array L and R such that

L[i]-R[i] is one range given. Our task is to find the maximum occurred smallest (first) integer in all the ranges. Means If more than one integer occurs max times, print the smallest one.

In other you can find similar code in

**Time Complexity**: O(n + MAX) and **Space Complexity : **O(Max)

We have tried to reduce complexity to O(n+m), space complexity : O(m) where m is largest integer in L or R

means m is largest range number.

Simple Solution :

To find Maximum occurred integer in N ranges, we can think of One Hash where we can store all range values

example if L[0]=4,R[0]=6, HMap[4] = 1, HMap[5] = 1, HMap[6] = 1

Traverse or iterate full hashmap and find smallest such number in N range.

To create hashMap, u’ll iterate through all numbers so Time complexity increases to n*m.

**Time Complexity : O(n*m) , Space Complexity : O(m)**

where m is largest number in Ranges given.

But We can find Maximum occurred integer in N rage ( same answer) with Different Logic Where Space Complexity remains same : O(m).

**Logic is Explained for Maximum occurred integer** : We create an array arr[] of size m ( m is maximum value of all intervals given ) . The idea is to add +1 to each L_{i} index and -1 to corresponding R_{i} index in arr[].

After this, find the prefix sum of the array. (prefix sum is adding all previous value to prefix array, which shows the occurance of any index in n ranges)

Adding +1 at L_{i} shows the starting point of ith Range and adding -1 shows the ending point of ith range. Finally we return the array index that has maximum prefix sum

Algorithm to solve the problem:

- Initialize an array prefix [] to 0.
- For each range i, add +1 at L
_{i}index and -1 at R_{i}of the array. - Find the prefix sum of the array and find the smallest index having maximum prefix sum.

// code owner www.gohired.in //C++ program to find maximum occured element in given N ranges. #include <iostream> #include <algorithm> #include <cstring> using namespace std; // Return the maximum occurred element in all ranges. int maximumOccuredSmallestElement(int L[], int R[], int n,int largest) { // Initalising all element of array to 0. int prefixArray[largest]; memset(prefixArray, 0, sizeof arr); for (int i = 0; i < n; i++) { prefixArray[L[i]] += 1; prefixArray[R[i] + 1] -= 1; } int msum = prefixArray[0], ind; for (int i = 1; i < largest; i++) { prefixArray[i] += prefixArray[i-1]; //SEE this Array and understand how this code and Logic of prefix works cout <<"prefix ["<<i<<"] = "<<prefixArray[i]<<endl; if (msum < prefixArray[i]) { msum = prefixArray[i]; ind = i; } } return ind; } // Driven Program int main() { int L[] = { 1, 4, 9, 13, 21 }; int R[] = { 15, 8, 12, 20, 30 }; int largest=0; int n = sizeof(L)/sizeof(L[0]); for(int i=0;i<n;i++){ largest = max(largest,max(L[i],R[i])); } cout << maximumOccuredSmallestElement(L, R, n, largest+1) << endl; return 0; }