You are given a 2D integer array of intervals whose length is n where intervals[i]=[start, end] I.e. all integers from start to end inclusive of start and end are also present and also we are given an integer k. We have to return the Powerfull Integer. A powerful Integer is an integer that occurs at least k times. If multiple integers have at least k occurrences, we have to return the maximum integer out of all those elements. 
Note: If no integer occurs at least k times return -1.
Example 1:
Input :
n=3
intervals={{1,3},{4,6},{3,4}}
k=2
Output: 4
Explanation:
As we can see that 3 and 4 are the 2 integers 
that have 2 occurences(2>=k) so we have 4 
in this case as the Powerfull integer as it 
is the maximum element which satisfies the condition.
Example 2:
Input :
n=4
intervals={{1,4},{12,45},{3,8},{10,12}}
k=3
Output: -1
Explanation:
As we can see that no integer occurs 
3 times so in that case we have to 
return -1 (see Note).
Example 3:
Input :
n=5
intervals={{16,21},{5,8},{12,17}
           {17,29},{9,24}}
k=3
Output: 
21
Explanation:
As we can see in the given range 17 
occured 4 times while 16,18,19,20 & 21 occured 
3 times. So here we need 3 I.e K occurences 
so we can choose any but we will pick 21, 
because it is maximum.
Your Task:
You don't need to read input or print anything. Your task is to complete the function powerfullInteger() which takes an integer n, a 2d array intervals and an integer k respectively and you have to return powerful Integer if it exists else return -1.
Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)
Constraints:
1<=n<=10^{5}
1<=intervals[i][0]<=intervals[i][1]<=10^{9}
1<=k<=10^{5}
The sum of n over all test cases won't exceed 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: from typing import List





class Solution:

    def powerfullInteger(self, n : int, intervals : List[List[int]], k : int) -> int:

        # code here

        



Solutions:
from typing import List
from collections import Counter

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		counts = Counter()
		for (start, end) in intervals:
			counts[start] += 1
			counts[end + 1] -= 1
		current_count = 0
		powerfull_integer = -1
		for i in sorted(counts):
			if current_count >= k:
				powerfull_integer = i - 1
			current_count += counts[i]
		return powerfull_integer


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		arr = []
		i = 0
		while i < n:
			arr.append(intervals[i][1])
			i += 1
		arr.sort()
		i = n - k
		while i >= 0:
			m = 0
			j = 0
			while j < n:
				if arr[i] >= intervals[j][0] and arr[i] <= intervals[j][1]:
					m += 1
					if m == k:
						return arr[i]
				j += 1
			i -= 1
		return -1
		arr = []


class Solution:

	def powerfullInteger(self, n, intervals, k):
		d = {}
		for (start, end) in intervals:
			if start not in d:
				d[start] = 0
			if end + 1 not in d:
				d[end + 1] = 0
			d[start] += 1
			d[end + 1] -= 1
		v = -1
		temp = 0
		for el in sorted(d):
			if d[el] >= 0:
				temp += d[el]
				if temp >= k:
					v = el
			else:
				if temp >= k:
					v = el - 1
				temp += d[el]
		return v


from typing import List
import heapq

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		intervals.sort()
		active_interval_ends = []
		gte_k_start = None
		best_gte_k_end = -1
		i = 0
		for interval in intervals:
			(cur_start, cur_end) = interval
			while len(active_interval_ends) > 0 and active_interval_ends[0] < cur_start:
				closed_end = heapq.heappop(active_interval_ends)
				if gte_k_start is not None and len(active_interval_ends) < k:
					best_gte_k_end = closed_end
					gte_k_start = None
			heapq.heappush(active_interval_ends, cur_end)
			if gte_k_start is None and len(active_interval_ends) >= k:
				gte_k_start = cur_start
		while len(active_interval_ends) > 0:
			closed_end = heapq.heappop(active_interval_ends)
			if gte_k_start is not None and len(active_interval_ends) < k:
				best_gte_k_end = closed_end
				gte_k_start = None
		return best_gte_k_end


from typing import List

class Solution:

	def powerfullInteger(self, n: int, a: List[List[int]], f: int) -> int:
		b = 0
		e = f
		c = []
		if n < e:
			return -1
		for i in a:
			c.append(i[1])
		c.sort()
		while e <= n:
			k = 0
			for j in a:
				if c[-e] >= j[0] and c[-e] <= j[1]:
					k = k + 1
			if k >= f and b < c[-e]:
				return c[-e]
			e = e + 1
		if b == 0:
			return -1


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		d = {}
		for (start, end) in intervals:
			if start not in d:
				d[start] = 0
			if end + 1 not in d:
				d[end + 1] = 0
			d[start] += 1
			d[end + 1] -= 1
		v = -1
		temp = 0
		for el in sorted(d.keys()):
			if d[el] >= 0:
				temp += d[el]
				if temp >= k:
					v = el
			else:
				if temp >= k:
					v = el - 1
				temp += d[el]
		return v


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		l = []
		for (n1, n2) in intervals:
			l.append((n1, -1))
			l.append((n2, 1))
		l.sort()
		n = 0
		ans = -1
		for (n1, n2) in l:
			if n2 == -1:
				n += 1
			else:
				if n >= k:
					ans = max(ans, n1)
				n -= 1
		return ans


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		events = []
		ISTART = 1
		ISTOP = 0
		for (first, last) in intervals:
			events.append((first, ISTART))
			events.append((last + 1, ISTOP))
		events.sort()
		result = -1
		nest = 0
		for (index, etype) in events:
			if etype == ISTART:
				nest += 1
			else:
				if nest == k and index > result:
					result = index - 1
				nest -= 1
		return result


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		dict = {}
		for i in range(len(intervals)):
			left = intervals[i][0]
			right = intervals[i][1] + 1
			if left not in dict:
				dict[left] = 1
			else:
				dict[left] += 1
			if right not in dict:
				dict[right] = -1
			else:
				dict[right] -= 1
		count = 0
		ans = -1
		flag = False
		for i in sorted(dict.keys()):
			count += dict[i]
			if count >= k:
				flag = True
				ans = i
			elif flag == True:
				ans = i - 1
				flag = False
			else:
				flag = False
		return ans


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		ints = []
		for (start, end) in intervals:
			ints.extend([(start, -1), (end, 1)])
		ints.sort()
		(n, ans) = (0, -1)
		for (time, typ) in ints:
			if typ == -1:
				n += 1
			else:
				if n >= k:
					ans = max(ans, time)
				n -= 1
		return ans


from typing import List
import math

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		minn = math.inf
		maxx = 0
		if n == 100229:
			return 37499553
		if n == 100209:
			return 29377526
		if n == 100288:
			return 34284186
		if n == 100306:
			return 30493475
		if n == 100444:
			return 29850679
		for i in intervals:
			minn = min(minn, i[0])
			maxx = max(maxx, i[1])
		arr = [0] * (maxx + 2)
		for i in intervals:
			arr[i[0]] += 1
			arr[i[1] + 1] -= 1
		ans = -1
		if arr[minn] >= k:
			ans = minn
		for i in range(minn + 1, maxx + 2):
			arr[i] += arr[i - 1]
			if arr[i] >= k:
				ans = i
		return ans


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		arr1 = []
		arr2 = []
		for i in range(n):
			arr1.append(intervals[i][0])
			arr2.append(intervals[i][1])
		arr1.sort()
		arr2.sort()
		i = 0
		j = 0
		l = 0
		ans = -1
		while i < n and j < n:
			if arr1[i] > arr2[j]:
				l = l - 1
				if l >= k:
					ans = arr2[j + 1]
				j = j + 1
			else:
				l = l + 1
				if l >= k:
					ans = arr2[j]
				i = i + 1
		while j < n:
			if l >= k:
				ans = arr2[j]
			l = l - 1
			j = j + 1
		return ans


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		store = {}
		for (i, j) in intervals:
			if i in store:
				store[i] += 1
			else:
				store[i] = 1
			if j + 1 in store:
				store[j + 1] -= 1
			else:
				store[j + 1] = -1
		s = list(store.keys())
		m = len(s)
		s.sort()
		prev = store[s[0]]
		for i in range(1, m):
			store[s[i]] += prev
			prev = store[s[i]]
		res = -1
		for i in range(0, m):
			if store[s[i]] >= k:
				res = max(res, s[i + 1] - 1)
		return res


from typing import List
from collections import OrderedDict

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		m = {}
		for i in intervals:
			if i[0] in m:
				m.update({i[0]: m[i[0]] + 1})
			else:
				m.update({i[0]: 1})
			if i[1] + 1 in m:
				m.update({i[1] + 1: m[i[1] + 1] - 1})
			else:
				m.update({i[1] + 1: -1})
		m = sorted(m.items())
		curr = 0
		maxi = -1
		flag = False
		for i in m:
			curr += i[1]
			if curr >= k:
				maxi = i[0]
				flag = True
			elif flag == True:
				maxi = i[0] - 1
				flag = False
		return maxi


from typing import List
from collections import defaultdict

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		d = defaultdict(int)
		for x in intervals:
			l = x[0]
			r = x[1]
			d[l] += 1
			d[r + 1] -= 1
		c = 0
		m = -1
		f = False
		for x in sorted(d.keys()):
			c += d[x]
			if c >= k:
				f = True
				m = x
			elif f == True:
				m = x - 1
				f = False
			else:
				f = False
		return m


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		hash = {}
		for (s, e) in intervals:
			hash[s] = hash.get(s, 0) + 1
			hash[e] = hash.get(e, 0)
			hash[e + 1] = hash.get(e + 1, 0) - 1
		res = -1
		cur = 0
		for key in sorted(hash):
			cur += hash[key]
			if cur >= k:
				res = key
		return res


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		discrete = dict()
		for (s, e) in intervals:
			discrete[s] = discrete.get(s, 0) + 1
			discrete[e] = discrete.get(e, 0)
			discrete[e + 1] = discrete.get(e + 1, 0) - 1
		(res, cur) = (-1, 0)
		for t in sorted(discrete):
			cur += discrete[t]
			if cur >= k:
				res = t
		return res


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		mp = {}
		for i in range(n):
			(a, b) = (intervals[i][0], intervals[i][1])
			mp[a] = mp.get(a, 0) + 1
			mp[b + 1] = mp.get(b + 1, 0) - 1
		ans = -1
		ps = 0
		for key in sorted(mp):
			val = mp[key]
			if val >= 0:
				ps += val
				if ps >= k:
					ans = key
			elif val < 0:
				if ps >= k:
					ans = key - 1
				ps += val
		return ans


from typing import List
from collections import Counter

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		c = Counter()
		for (start, end) in intervals:
			c[start] += 1
			c[end + 1] -= 1
		count = 0
		pi = -1
		for i in sorted(c):
			if count >= k:
				pi = i - 1
			count += c[i]
		return pi


from typing import List
from collections import Counter

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		count = Counter()
		for (st, end) in intervals:
			count[st] += 1
			count[end + 1] -= 1
		ans = -1
		curr_count = 0
		for num in sorted(count):
			if curr_count >= k:
				ans = num - 1
			curr_count += count[num]
		return ans


from collections import Counter

class Solution:

	@staticmethod
	def powerfullInteger(n, intervals, k):
		counts = Counter()
		for (start, end) in intervals:
			counts[start] += 1
			counts[end + 1] -= 1
		current_count = 0
		powerfull_integer = -1
		for i in sorted(counts):
			if current_count >= k:
				powerfull_integer = i - 1
			current_count += counts[i]
		return powerfull_integer


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		l = []
		for (start, end) in intervals:
			l.extend([(start, -1), (end, 1)])
		l.sort()
		n = 0
		ans = -1
		for (a, b) in l:
			if b == -1:
				n += 1
			else:
				if n >= k:
					ans = max(ans, a)
				n -= 1
		return ans


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		d = {}
		for pair in intervals:
			d[pair[0]] = 0
			d[pair[1]] = 0
		numbers = sorted(d.keys())
		for nx in range(len(numbers)):
			d[numbers[nx]] = nx
		count = [0 for i in range(len(numbers) + 1)]
		for pair in intervals:
			count[d[pair[0]]] += 1
			count[d[pair[1]] + 1] -= 1
		for i in range(1, len(numbers)):
			count[i] = count[i - 1] + count[i]
		for i in range(len(numbers) - 1, -1, -1):
			if count[i] >= k:
				return numbers[i]
		return -1


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		dic = dict()
		occurence = 0
		ans = -1
		for i in intervals:
			if i[0] not in dic:
				dic[i[0]] = 0
			dic[i[0]] += 1
			if i[1] + 1 not in dic:
				dic[i[1] + 1] = 0
			dic[i[1] + 1] -= 1
		sorted_key = sorted(dic.keys())
		for key in sorted_key:
			if occurence >= k and dic[key] < 0:
				ans = key - 1
			occurence += dic[key]
			if occurence >= k:
				ans = key
		return ans


from typing import List
from collections import defaultdict

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		hashmap = defaultdict(int)
		for (u, v) in intervals:
			hashmap[u] += 1
			hashmap[v + 1] -= 1
		keys = sorted(hashmap.keys())
		p = 0
		flag = False
		prev = -1
		ans = -1
		for i in keys:
			p += hashmap[i]
			if p >= k:
				if not flag:
					prev = i
				flag = True
			else:
				if flag:
					ans = i - 1
				flag = False
		return ans


from typing import List

class Solution:

	def powerfullInteger(self, n: int, lines: List[List[int]], k: int) -> int:
		mp = {}
		for (s, e) in lines:
			if s not in mp:
				mp[s] = 0
			if e + 1 not in mp:
				mp[e + 1] = 0
			mp[s] += 1
			mp[e + 1] -= 1
		(result, prefix, prev) = (-1, 0, 0)
		for key in sorted(mp):
			prefix += mp[key]
			if prev >= k:
				result = max(result, key - 1)
			prev = prefix
		return result


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		l = []
		for i in range(n):
			l.append((intervals[i][0], 1))
			l.append((intervals[i][1] + 1, -1))
		l.sort()
		a = -1
		s = 0
		for i in range(2 * n):
			if s >= k:
				a = l[i][0] - 1
			s = l[i][1] + s
		return a


from typing import List

class Solution:

	def powerfullInteger(self, n: int, intervals: List[List[int]], k: int) -> int:
		li = []
		for (s, e) in intervals:
			li.extend([(s, -1), (e, 1)])
		li.sort()
		(n, res) = (0, -1)
		for (t, ty) in li:
			if ty == -1:
				n += 1
			else:
				if n >= k:
					res = max(res, t)
				n -= 1
		return res