Maximum occurring integer in given ranges

Given two arrays l[] and r[] of size n where l[i] and r[i] denotes a range of numbers, the task is to find the maximum occurring integer in all the ranges. If more than one such integer exists, print the smallest one.

Examples:

Input: l[] = [1, 2, 4, 3], r[] = [6, 4, 8, 5]
Output: 4
Explanation: The ranges are [1, 6], [2, 4], [4, 8], and [3, 5]. The maximum occurring integer is 4.
Input: l[] = [1, 5, 9, 13, 21], r[] = [15, 8, 12, 20, 30]
Output: 5
Explanation: Numbers having maximum occurrence i.e., 2 are
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. The smallest number among all are 5.

Try it on GfG Practice

Table of Content

[Naive Approach] Using Hash Map
[Efficient Approach] Using Difference Array

[Naive Approach] Using Hash Map

The idea is to count the frequency of each integer within all the given ranges. For each range [l[i], r[i]], we increment the count of every integer in that range. After processing all ranges, we find the integer with the highest frequency. If multiple integers have the same maximum frequency, we choose the smallest one.

C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int maxOccured(vector<int> &l, vector<int> &r) {
    int n = l.size();
    unordered_map<int, int> freq;
    
    // Count frequency of each integer in all ranges
    for (int i = 0; i < n; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            freq[j]++;
        }
    }
    
    // Find maximum frequency and smallest number
    int maxFreq = 0;
    int result = -1;
    
    for (auto& pair : freq) {
        
        // Update result if current frequency is higher or
        // if frequency is same but value is smaller
        if (pair.second > maxFreq || 
            (pair.second == maxFreq && pair.first < result)) {
            maxFreq = pair.second;
            result = pair.first;
        }
    }
    
    return result;
}

int main() {
    vector<int> l = {1, 2, 4, 3};
    vector<int> r = {6, 4, 8, 5};
    cout << maxOccured(l, r);
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;

class GfG {
    static int maxOccured(int[] l, int[] r) {
        int n = l.length;
        Map<Integer, Integer> freq = new HashMap<>();
        
        // Count frequency of each integer in all ranges
        for (int i = 0; i < n; i++) {
            for (int j = l[i]; j <= r[i]; j++) {
                freq.put(j, freq.getOrDefault(j, 0) + 1);
            }
        }
        
        // Find maximum frequency and smallest number
        int maxFreq = 0;
        int result = -1;
        
        for (Map.Entry<Integer, Integer> pair : freq.entrySet()) {
            // Update result if current frequency is higher or
            // if frequency is same but value is smaller
            if (pair.getValue() > maxFreq || 
                (pair.getValue() == maxFreq && pair.getKey() < result)) {
                maxFreq = pair.getValue();
                result = pair.getKey();
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] l = {1, 2, 4, 3};
        int[] r = {6, 4, 8, 5};
        System.out.println(maxOccured(l, r));
    }
}

Python

def maxOccured(l, r):
    n = len(l)
    freq = {}
    
    # Count frequency of each integer in all ranges
    for i in range(n):
        for j in range(l[i], r[i] + 1):
            freq[j] = freq.get(j, 0) + 1
    
    # Find maximum frequency and smallest number
    maxFreq = 0
    result = -1
    
    for num, count in freq.items():
        
        # Update result if current frequency is higher or
        # if frequency is same but value is smaller
        if count > maxFreq or (count == maxFreq and num < result):
            maxFreq = count
            result = num
    
    return result

if __name__ == "__main__":
    l = [1, 2, 4, 3]
    r = [6, 4, 8, 5]
    print(maxOccured(l, r))

using System;
using System.Collections.Generic;

class GfG {
    static int maxOccured(int[] l, int[] r) {
        int n = l.Length;
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        // Count frequency of each integer in all ranges
        for (int i = 0; i < n; i++) {
            for (int j = l[i]; j <= r[i]; j++) {
                if (freq.ContainsKey(j)) {
                    freq[j]++;
                } else {
                    freq[j] = 1;
                }
            }
        }
        
        // Find maximum frequency and smallest number
        int maxFreq = 0;
        int result = -1;
        
        foreach (KeyValuePair<int, int> pair in freq) {
            
            // Update result if current frequency is higher or
            // if frequency is same but value is smaller
            if (pair.Value > maxFreq || 
                (pair.Value == maxFreq && pair.Key < result)) {
                maxFreq = pair.Value;
                result = pair.Key;
            }
        }
        
        return result;
    }

    static void Main() {
        int[] l = {1, 2, 4, 3};
        int[] r = {6, 4, 8, 5};
        Console.WriteLine(maxOccured(l, r));
    }
}

JavaScript

function maxOccured(l, r) {
    let n = l.length;
    let freq = new Map();
    
    // Count frequency of each integer in all ranges
    for (let i = 0; i < n; i++) {
        for (let j = l[i]; j <= r[i]; j++) {
            freq.set(j, (freq.get(j) || 0) + 1);
        }
    }
    
    // Find maximum frequency and smallest number
    let maxFreq = 0;
    let result = -1;
    
    for (let [num, count] of freq) {
        // Update result if current frequency is higher or
        // if frequency is same but value is smaller
        if (count > maxFreq || 
            (count === maxFreq && num < result)) {
            maxFreq = count;
            result = num;
        }
    }
    
    return result;
}

// Driver Code
let l = [1, 2, 4, 3];
let r = [6, 4, 8, 5];
console.log(maxOccured(l, r));

Output

Time Complexity: O(n * m). Here n is the number of ranges and m is the maximum number of elements in any of the ranges.
Auxiliary Space: O(m), due to hash map.

[Efficient Approach] Using Difference Array

The idea is to use a difference array technique to efficiently handle range updates. Instead of individually incrementing each number in a range, we mark the start and end of ranges. For each range [l[i], r[i]], we increment the value at index l[i] and decrement the value at index r[i]+1. By calculating the prefix sum, we can determine the frequency of each number across all ranges.

Step by step approach:

Find the maximum value (maxi) in all ranges.
Create a difference array of size maxi+2.
For each range, increment diff[l[i]] and decrement diff[r[i]+1].
Calculate prefix sum while tracking maximum frequency.
Return the index with maximum frequency.

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxOccured(vector<int> &l, vector<int> &r) {
    int n = l.size();
    
    // Find maximum value in ranges
    int maxi = INT_MIN;
    for (int i=0; i<n; i++) maxi = max(maxi, r[i]);
    
    vector<int> diff(maxi + 2, 0);
    
    // Mark the starting and ending of ranges
    for (int i = 0; i < n; i++) {
        
        // Increment at start of range
        diff[l[i]]++;   
        
        // Decrement at end+1 of range
        diff[r[i] + 1]--;   
    }
    
    // Calculate the prefix sum and find maximum frequency
    int maxFreq = diff[0];
    int result = 0;
    
    for (int i = 1; i <= maxi; i++) {
        
        // Calculate prefix sum
        diff[i] += diff[i - 1];
        
        // Update result if current frequency is higher
        if (diff[i] > maxFreq) {
            maxFreq = diff[i];
            result = i;
        }
    }
    
    return result;
}

int main() {
    vector<int> l = {1, 2, 4, 3};
    vector<int> r = {6, 4, 8, 5};
    cout << maxOccured(l, r);
    return 0;
}