Given n integer ranges, the task is to find the maximum occurring integer in these ranges. If more than one such integer exists, find the smallest one. The ranges are given as two arrays L[] and R[].  L[i] consists of starting point of range and R[i] consists of corresponding end point of the range. 
For example consider the following ranges.
L[] = {2, 1, 3}, R[] = {5, 3, 9)
Ranges represented by above arrays are.
[2, 5] = {2, 3, 4, 5}
[1, 3] = {1, 2, 3}
[3, 9] = {3, 4, 5, 6, 7, 8, 9}
The maximum occurred integer in these ranges is 3.
Example 1:
Input:
n = 4
L[] = {1,4,3,1}
R[] = {15,8,5,4}
Output: 4
Explanation: The given ranges are [1,15]
 [4, 8] [3, 5] [1, 4]. The number that 
is most common or appears most times in 
the ranges is 4.
Example 2:
Input:
n = 5
L[] = {1,5,9,13,21}
R[] = {15,8,12,20,30}
Output: 5
Explanation: The given ranges are 
[1,15] [5, 8] [9, 12] [13, 20] 
[21, 30]. The number that is most 
common or appears most times in 
the ranges is 5.
Your Task:
The task is to complete the function maxOccured() which returns the maximum occured integer in all ranges.
Expected Time Complexity: O(n+maxx).
Expected Auxiliary Space: O(maxx).
-maxx is maximum element in R[]
Constraints:
1 ≤ n ≤ 10^{6}
0 ≤ L[i], R[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    #Complete this function

    #Function to find the maximum occurred integer in all ranges.

    def maxOccured(self,L,R,N,maxx):

        ##Your code here

Solutions:
class Solution:

	def maxOccured(self, L, R, N, maxx):
		maxx = maxx + 10
		result = [0] * maxx
		for i in range(N):
			l = L[i]
			u = R[i] + 1
			result[u] += -1
			result[l] += 1
		for i in range(1, maxx):
			result[i] = result[i] + result[i - 1]
		high = max(result)
		val = result.index(high)
		return val


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0] * (maxx + 2)
		i = 0
		while i < N:
			freq[L[i]] += 1
			freq[R[i] + 1] -= 1
			i += 1
		res = 0
		i = 1
		while i < maxx + 1:
			freq[i] += freq[i - 1]
			if freq[res] < freq[i]:
				res = i
			i += 1
		return res


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0] * (maxx + 2)
		for i in range(N):
			freq[L[i]] += 1
			freq[R[i] + 1] += -1
		pre = [0] * (maxx + 1)
		pre[0] = freq[0]
		for i in range(1, maxx + 1):
			pre[i] = pre[i - 1] + freq[i]
		return pre.index(max(pre))


class Solution:

	def maxOccured(self, L, R, n, maxx):
		max_ele = 0
		arr = [0] * (maxx + 2)
		for i in range(n):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		cnt = arr[0]
		for i in range(1, maxx + 2):
			arr[i] += arr[i - 1]
			if arr[i] > cnt:
				max_ele = i
				cnt = arr[i]
		return max_ele


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0] * (maxx + 2)
		res = 0
		for i in range(0, N):
			freq[L[i]] += 1
			freq[R[i] + 1] -= 1
		for i in range(1, maxx + 2):
			freq[i] = freq[i - 1] + freq[i]
			if freq[i] > freq[res]:
				res = i
		return res


class Solution:

	def maxOccured(self, l, r, n, maxx):
		arr = [0] * (maxx + 2)
		for i in range(n):
			arr[l[i]] += 1
			arr[r[i] + 1] -= 1
		ele = -1000000000.0
		maxcount = 0
		count = 0
		for i in range(maxx + 1):
			count += arr[i]
			if count > maxcount:
				maxcount = count
				ele = i
		return ele


class Solution:

	def maxOccured(self, L, R, N, maxx):
		prefix_sum_arr = [0] * (maxx + 2)
		for (_, num) in enumerate(zip(L, R)):
			prefix_sum_arr[num[0]] += 1
			prefix_sum_arr[num[1] + 1] -= 1
		max_value = prefix_sum_arr[0]
		max_value_index = 0
		for i in range(1, maxx + 2):
			prefix_sum_arr[i] += prefix_sum_arr[i - 1]
			if max_value < prefix_sum_arr[i]:
				max_value = prefix_sum_arr[i]
				max_value_index = i
		return max_value_index


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * (maxx + 2)
		for i in range(N):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		max1 = arr[0]
		presum = 0
		for i in range(1, maxx + 2):
			arr[i] = arr[i] + arr[i - 1]
			if max1 < arr[i]:
				max1 = arr[i]
				presum = i
		return presum


class Solution:

	def maxOccured(self, L, R, N, maxx):
		l = min(L)
		r = max(R)
		ran = [0] * (r + 2)
		for i in range(N):
			ran[L[i]] += 1
			ran[R[i] + 1] += -1
		m = 0
		mi = 0
		for i in range(l, r + 2):
			if i > 0:
				ran[i] = ran[i] + ran[i - 1]
			if ran[i] > m:
				m = ran[i]
				mi = i
		return mi


class Solution:

	def maxOccured(self, L, R, n, maxx):
		occured = [0] * (maxx + 2)
		for i in range(n):
			occured[L[i]] += 1
			occured[R[i] + 1] -= 1
		index = 0
		for i in range(1, maxx + 2):
			occured[i] = occured[i - 1] + occured[i]
			if occured[index] < occured[i]:
				index = i
		return index


class Solution:

	def maxOccured(self, L, R, n, maxx):
		arr = [0 for i in range(maxx + 2)]
		for i in range(0, n, 1):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		msum = arr[0]
		ind = 0
		for i in range(1, maxx + 1):
			arr[i] += arr[i - 1]
			if msum < arr[i]:
				msum = arr[i]
				ind = i
		return ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		last = [0 for i in range(maxx + 2)]
		for i in range(N):
			last[L[i]] += 1
			last[R[i] + 1] -= 1
		maxi = last[0]
		ind = 0
		for i in range(1, maxx + 2):
			last[i] += last[i - 1]
			if last[i] > maxi:
				maxi = last[i]
				ind = i
		return ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * (maxx + 2)
		for i in range(N):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		mx = arr[0]
		ans = 0
		for i in range(1, maxx + 1):
			arr[i] += arr[i - 1]
			if mx < arr[i]:
				mx = arr[i]
				ans = i
		return ans


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0] * (maxx + 2)
		for (i, j) in zip(L, R):
			freq[i] += 1
			freq[j + 1] -= 1
		for x in range(1, len(freq)):
			freq[x] = freq[x] + freq[x - 1]
		return freq.index(max(freq))


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0 for _ in range(maxx + 2)]
		for i in range(N):
			freq[L[i]] += 1
			freq[R[i] + 1] -= 1
		max_freq = freq[0]
		ans = 0
		for i in range(1, len(freq)):
			freq[i] += freq[i - 1]
			if freq[i] > max_freq:
				ans = i
				max_freq = freq[i]
		return ans


class Solution:

	def maxOccured(self, L, R, N, maxx):
		l = [0 for i in range(maxx + 2)]
		for i in range(N):
			l[L[i]] += 1
			l[R[i] + 1] -= 1
		for i in range(1, maxx + 1):
			l[i] = l[i] + l[i - 1]
		a = max(l)
		return l.index(a)


class Solution:

	def maxOccured(self, L, R, N, maxx):
		prefixSumArr = [0 for i in range(maxx + 2)]
		for i in range(0, N):
			prefixSumArr[L[i]] += 1
			prefixSumArr[R[i] + 1] -= 1
		preSum = 0
		for i in range(1, maxx + 2):
			prefixSumArr[i] = prefixSumArr[i - 1] + prefixSumArr[i]
		maxVal = max(prefixSumArr)
		return prefixSumArr.index(maxVal)


from itertools import accumulate

class Solution:

	def maxOccured(self, L, R, N, maxx):
		pr = [0] * (maxx + 2)
		for (i, j) in zip(L, R):
			pr[i] += 1
			pr[j + 1] -= 1
		a = list(accumulate(pr))
		return a.index(max(a))


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * 100000
		for i in range(N):
			arr[L[i]] = arr[L[i]] + 1
			arr[R[i] + 1] = arr[R[i] + 1] - 1
		imax = arr[0]
		res = 0
		for i in range(1, 100000):
			arr[i] = arr[i] + arr[i - 1]
			if arr[i] > imax:
				imax = arr[i]
				res = i
		return res


class Solution:

	def maxOccured(self, L, R, N, maxx):
		i = 0
		while i < N:
			A[L[i]] += 1
			A[R[i] + 1] -= 1
			i += 1
		msum = A[0]
		ind = 0
		i = 1
		while i <= maxx:
			A[i] += A[i - 1]
			if msum < A[i]:
				msum = A[i]
				ind = i
			i += 1
		return ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		ar = [0] * (maxx + 2)
		for i in range(N):
			ar[L[i]] += 1
			ar[R[i] + 1] -= 1
		mx = cr = ar[0]
		t = 0
		for i in range(1, maxx + 1):
			cr += ar[i]
			if cr > mx:
				mx = cr
				t = i
		return t


class Solution:

	def maxOccured(self, L, R, N, maxx):
		a = [0] * (maxx + 2)
		pre_sum = 0
		for i in range(N):
			a[L[i]] += 1
			a[R[i] + 1] -= 1
		pre_sum += a[0]
		for i in range(1, len(a)):
			if a[i] == 0:
				a[i] = pre_sum
			else:
				pre_sum += a[i]
				a[i] = pre_sum
		return a.index(max(a))


class Solution:

	def maxOccured(self, l, r, n, maxx):
		preS = [0] * (maxx + 2)
		for i in range(n):
			preS[l[i]] += 1
			preS[r[i] + 1] -= 1
		ans = 0
		for i in range(1, maxx + 1):
			preS[i] = preS[i] + preS[i - 1]
			if preS[i] > preS[ans]:
				ans = i
		return ans


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0] * 10 ** 6
		for i in range(0, N):
			freq[L[i]] = freq[L[i]] + 1
			freq[R[i] + 1] = freq[R[i] + 1] - 1
		for i in range(1, maxx):
			freq[i] = freq[i] + freq[i - 1]
		l = 0
		for i in range(1, maxx):
			if freq[l] < freq[i]:
				l = i
		return l


class Solution:

	def maxOccured(self, L, R, N, maxx):
		maxl = max(L)
		maxr = max(R)
		max_tot = max(maxl, maxr)
		A = [0] * (max_tot + 2)
		for i in L:
			A[i] += 1
		for i in R:
			A[i + 1] -= 1
		for i in range(1, max_tot + 2, 1):
			A[i] += A[i - 1]
		index = A.index(max(A))
		return index


class Solution:

	def maxOccured(self, L, R, N, maxx):
		max_ = 100000
		arr = [0 for i in range(max_)]
		for i in range(0, N, 1):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		msum = arr[0]
		ind = 0
		for i in range(1, maxx, 1):
			arr[i] += arr[i - 1]
			if msum < arr[i]:
				msum = arr[i]
				ind = i
		return ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		for i in range(N):
			A[L[i]] += 1
			A[R[i] + 1] -= 1
		res = A[0]
		su = 0
		for i in range(1, maxx + 1):
			A[i] += A[i - 1]
			if res < A[i]:
				res = A[i]
				su = i
		return su


class Solution:

	def maxOccured(self, L, R, N, maxx):
		diff = [0] * (maxx + 2)
		for i in range(N):
			left = L[i]
			right = R[i]
			diff[left] += 1
			diff[right + 1] -= 1
		occurrences = []
		occurrences.append(diff[0])
		for j in range(1, maxx + 1):
			occurrences.append(diff[j] + occurrences[j - 1])
		max_occur = 0
		max_idx = -1
		for k in range(maxx + 1):
			if occurrences[k] > max_occur:
				max_occur = occurrences[k]
				max_idx = k
		return max_idx


class Solution:

	def maxOccured(self, L, R, N, maxx):
		elems = [0] * (maxx + 1)
		for i in range(N):
			elems[L[i]] += 1
			if R[i] < maxx:
				elems[R[i] + 1] -= 1
		max_ele = elems[0]
		max_ind = 0
		for j in range(1, len(elems)):
			elems[j] += elems[j - 1]
			if elems[j] > max_ele:
				max_ele = max(max_ele, elems[j])
				max_ind = j
		return max_ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * (maxx + 10)
		for i in range(N):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		for i in range(1, len(arr)):
			arr[i] = arr[i] + arr[i - 1]
		index = 0
		maxi = float('-inf')
		for i in range(len(arr)):
			if arr[i] > maxi:
				maxi = arr[i]
				index = i
		return index


class Solution:

	def maxOccured(self, L, R, N, maxx):
		freq = [0] * (maxx + 2)
		for i in range(N):
			left = L[i]
			right = R[i]
			freq[left] += 1
			freq[right + 1] -= 1
		count = 0
		maxfreq = -1
		res = 0
		for i in range(len(freq)):
			count += freq[i]
			if count > maxfreq:
				maxfreq = count
				res = i
		return res


class Solution:

	def maxOccured(self, L, R, N, maxx):
		m = max(R)
		hashh = [0] * (m + 5)
		for ek in L:
			hashh[ek] += 1
		for el in R:
			hashh[el + 1] -= 1
		my = 0
		ind = 0
		u = hashh[0]
		for i in range(1, m + 5):
			hashh[i] = hashh[i - 1] + hashh[i]
			if hashh[i] > my:
				my = hashh[i]
				ind = i
		if hashh[0] == hashh[ind]:
			return 0
		return ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		pref = [0] * (maxx + 2)
		for i in range(N):
			pref[L[i]] += 1
			pref[R[i] + 1] -= 1
		currMax = float('-infinity')
		result = float('infinity')
		for i in range(1, maxx + 2):
			pref[i] += pref[i - 1]
		for i in range(maxx + 2):
			if pref[i] > currMax:
				currMax = pref[i]
				result = i
			elif pref[i] == currMax:
				result = min(result, i)
		return result


class Solution:

	def maxOccured(self, L, R, N, maxx):
		l = [0] * (maxx + 2)
		for i in L:
			l[i] += 1
		for i in R:
			l[i + 1] -= 1
		k = 0
		for i in range(1, len(l)):
			l[i] = l[i] + l[i - 1]
			if l[i] > l[k]:
				k = i
		return k


import numpy as np

class Solution:

	def maxOccured(self, L, R, N, maxx):
		minimum = min(L)
		maximum = max(R)
		arr = np.array([0] * (maximum - minimum + 1))
		x = minimum
		for i in range(N):
			arr[L[i] - x:R[i] - x + 1] += 1
		arr = list(arr)
		return arr.index(max(arr)) + x


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * (maxx + 10)
		for i in range(N):
			left = L[i]
			right = R[i] + 1
			arr[left] += 1
			arr[right] -= 1
		m = arr[0]
		index = 0
		for i in range(1, len(arr)):
			arr[i] = arr[i] + arr[i - 1]
			if arr[i] > m:
				m = arr[i]
				index = i
		return index


class Solution:

	def maxOccured(self, L, R, n, maxx):
		arr = [0 for i in range(maxx + 2)]
		for i in range(0, n, 1):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		for i in range(1, maxx):
			arr[i] += arr[i - 1]
		return arr.index(max(arr))


from collections import Counter

class Solution:

	def maxOccured(self, L, R, n, MAX):
		arr = [0 for i in range(MAX + 2)]
		for i in range(0, n, 1):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		msum = arr[0]
		ind = 0
		for i in range(1, MAX + 1, 1):
			arr[i] += arr[i - 1]
			if msum < arr[i]:
				msum = arr[i]
				ind = i
		return ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * (max(*R) + 2)
		for i in range(0, N):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		index = -1
		sum = 0
		maxsum = 0
		for i in range(len(arr)):
			sum += arr[i]
			if sum > maxsum:
				maxsum = sum
				index = i
		return index


class Solution:

	def maxOccured(self, L, R, N, maxx):
		t = [0 for i in range(maxx + 1)]
		for i in range(N):
			t[L[i]] += 1
			if R[i] + 1 <= maxx:
				t[R[i] + 1] -= 1
		max_ind = -1
		max_val = float('-inf')
		curr = 0
		for i in range(len(t)):
			curr += t[i]
			if curr > max_val:
				max_val = curr
				max_ind = i
		return max_ind


class Solution:

	def maxOccured(self, L, R, N, maxx):
		m = max(R) + 1
		arr = [0 for i in range(m + 1)]
		for i in L:
			arr[i] += 1
		for j in R:
			arr[j + 1] -= 1
		for i in range(1, m, 1):
			arr[i] = arr[i] + arr[i - 1]
		v = arr.index(max(arr))
		return v


class Solution:

	def maxOccured(self, L, R, N, maxx):
		lis = [0 for i in range(maxx + 2)]
		for i in range(N):
			lis[L[i]] += 1
			lis[R[i] + 1] -= 1
		mx = 0
		cur = 0
		for i in range(maxx):
			cur += lis[i]
			if cur > mx:
				id = i
				mx = cur
		return id


class Solution:

	def maxOccured(self, L, R, N, maxx):
		temp = [0] * (maxx + 2)
		for i in range(N):
			temp[L[i]] += 1
			temp[R[i] + 1] -= 1
		maxi = temp[0]
		res = 0
		for j in range(1, maxx):
			temp[j] += temp[j - 1]
			if temp[j] > maxi:
				maxi = temp[j]
				res = j
		return res


from collections import OrderedDict

class Solution:

	def maxOccured(self, L, R, N, maxx):
		res = [0 for i in range(maxx + 2)]
		for i in range(N):
			res[L[i]] += 1
			res[R[i] + 1] -= 1
		m = 0
		for i in range(1, maxx + 1):
			res[i] = res[i] + res[i - 1]
		m = max(res)
		for i in range(len(res)):
			if res[i] == m:
				return i


class Solution:

	def maxOccured(self, L, R, N, maxx):
		arr = [0] * 100001
		maxx = 0
		for i in range(N):
			arr[L[i]] += 1
			arr[R[i] + 1] -= 1
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
			if arr[i] > arr[maxx]:
				maxx = i
		return maxx


class Solution:

	def maxOccured(self, L, R, N, maxx):
		prefixsum = [0] * (maxx + 2)
		for i in range(0, N):
			prefixsum[L[i]] += 1
			prefixsum[R[i] + 1] -= 1
		for i in range(1, len(prefixsum)):
			prefixsum[i] = prefixsum[i - 1] + prefixsum[i]
		max = -maxx
		maxIndex = -1
		for i in range(0, len(prefixsum)):
			if prefixsum[i] > max:
				max = prefixsum[i]
				maxIndex = i
		return maxIndex