Given a sorted array A[] of N distinct integers from 0 to 99999. Find all the integer intervals missing from the given list.
Note: There is always atleast 1 number missing.
Example 1:
Input:
N = 4
A = {1,5,67,88}
Output:
0,2-4,6-66,68-87,89-99999
Explanation:
All the missing Intervals are printed.
Example 2: 
Input:
N = 6
A = {4,55,77,89,91,99} 
Output:
0-3,5-54,56-76,78-88,90,92-98, 100-99999
Your Task:  
You don't need to read input or print anything. Your task is to complete the function printMissingIntervals() which takes Integer N and an Array A[] as input and returns a array of elements with 2*x elements where x is the number of missing intervals and each pair in the array is the range missing. arr={1,3,97,100} would mean the intervals missing are 1-3 and 97-100. Suppose only the number 1 is missing ,then arr={1,1}.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ A_{i} < 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def printMissingIntervals(self, a , n):
        # code here 

Solutions:
class Solution:

	def printMissingIntervals(self, a, n):
		m = [0] * 100000
		for i in range(n):
			m[a[i]] = 1
		ans = []
		curr = 0
		start = -1
		while curr < 100000:
			if m[curr] == 0:
				ans.append(curr)
				while curr < 100000 and m[curr] == 0:
					curr += 1
				ans.append(curr - 1)
				curr += 1
			else:
				start = -1
				curr += 1
		return ans


class Solution:

	def printMissingIntervals(self, a, n):
		ans = []
		if a[0] != 0:
			ans.append(0)
			ans.append(a[0] - 1)
		for i in range(n - 1):
			if a[i] + 1 != a[i + 1]:
				ans.append(a[i] + 1)
				ans.append(a[i + 1] - 1)
		if a[n - 1] != 99999:
			ans.append(a[n - 1] + 1)
			ans.append(99999)
		return ans


class Solution:
	max_val = 99999

	def printMissingIntervals(self, a, n):
		s = 0
		res = []
		for num in a:
			if num == s:
				s += 1
			else:
				res.append(s)
				res.append(num - 1)
				s = num + 1
		if s <= self.max_val:
			res.append(s)
			res.append(self.max_val)
		return res


class Solution:

	def printMissingIntervals(self, a, n):
		r = []
		if a[0] != 0:
			r.append(0)
			if a[0] != 1:
				r.append(a[0] - 1)
			else:
				r.append(0)
		i = 1
		while i < n:
			p = abs(a[i] - a[i - 1])
			if p > 1:
				r.append(a[i - 1] + 1)
				r.append(a[i] - 1)
			i += 1
		if a[-1] != 99999:
			if a[-1] == 99998:
				r.append(99999)
			else:
				r.append(a[-1] + 1)
			r.append(99999)
		return r


class Solution:

	def printMissingIntervals(self, arr, n):
		present = [False] * (99999 + 1)
		for i in arr:
			present[i] = True
		res = []
		i = 0
		while i <= 99999:
			if not present[i]:
				l = r = i
				while i <= 99999 and (not present[i]):
					r = i
					i += 1
				res.append(l)
				res.append(r)
			i += 1
		return res


class Solution:

	def printMissingIntervals(self, a, n):
		lis = []
		for i in range(n):
			if i == 0:
				if a[i] != 0:
					lis.append(0)
					lis.append(a[i] - 1)
					continue
			elif a[i - 1] + 1 != a[i]:
				lis.append(a[i - 1] + 1)
				lis.append(a[i] - 1)
		if a[-1] != 99999:
			lis.append(a[-1] + 1)
			lis.append(99999)
		return lis


class Solution:

	def printMissingIntervals(self, a, n):
		m = -1
		l = []
		for i in a:
			t = m + 1
			w = i - 1
			if t <= w:
				l.append(t)
				l.append(w)
			m = i
		if m + 1 <= 99999:
			l.append(m + 1)
			l.append(99999)
		return l


class Solution:

	def printMissingIntervals(self, a, n):
		output = []
		start = 0
		end = 99999
		for item in a:
			if item == start:
				start += 1
			else:
				output.append(start)
				output.append(item - 1)
				start = item + 1
		if start <= end:
			output.append(start)
			output.append(end)
		return output


class Solution:

	def printMissingIntervals(self, a, n):
		mis_interval = []
		for i in range(n - 1):
			if i == 0 and a[i] != 0:
				if a[i] == 1:
					mis_interval.append(str(i))
					mis_interval.append(str(i))
				else:
					mis_interval.append('0')
					mis_interval.append(str(a[i] - 1))
			if a[i] + 1 == a[i + 1]:
				continue
			if i < n - 1:
				mis_interval.append(str(a[i] + 1))
				mis_interval.append(str(a[i + 1] - 1))
		if a[n - 1] != 99999:
			mis_interval.append(str(a[n - 1] + 1))
			mis_interval.append(str(99999))
		return mis_interval


class Solution:

	def printMissingIntervals(self, arr, n):
		if not arr:
			return ['0-99999']
		ret = []
		if arr[0] != 0:
			arr = [-1] + arr
		if arr[-1] != 99999:
			arr = arr + [100000]
		for i in range(len(arr) - 1):
			if arr[i] != arr[i + 1] - 1:
				first = arr[i] + 1
				last = arr[i + 1] - 1
				ret += [first, last]
		return ret


class Solution:

	def printMissingIntervals(self, a, n):
		res = []
		if a[0] != 0:
			if a[0] == 1:
				res.extend([0, 0])
			else:
				res.extend([0, a[0] - 1])
		for i in range(0, n - 1):
			if a[i] + 1 == a[i + 1] - 1:
				res.extend([a[i] + 1, a[i] + 1])
			elif a[i] == a[i + 1] - 1:
				continue
			else:
				res.extend([a[i] + 1, a[i + 1] - 1])
		if a[-1] != 99999:
			res.extend([a[-1] + 1, 99999])
		return res


class Solution:

	def printMissingIntervals(self, a, n):
		out = []
		if a[0] != 0:
			out.append((0, a[0] - 1))
		for i in range(0, n - 1):
			curr_elem = a[i]
			next_elem = a[i + 1]
			if curr_elem + 1 == next_elem:
				continue
			elif curr_elem + 1 == next_elem - 1:
				out.append((curr_elem + 1, curr_elem + 1))
			else:
				out.append((curr_elem + 1, next_elem - 1))
		if a[-1] != 99999:
			if a[-1] == 99998:
				out.append((99999, 99999))
			else:
				out.append((a[-1] + 1, 99999))
		out_ = []
		for c in out:
			for cc in c:
				out_.append(cc)
		return out_


class Solution:

	def printMissingIntervals(self, a, n):
		i = 0
		ans = []
		index = 0
		while index < n:
			if a[index] > i:
				ans.append(i)
				ans.append(a[index] - 1)
			i = a[index] + 1
			index += 1
		if a[-1] != 99999:
			ans.append(a[-1] + 1)
			ans.append(99999)
		return ans


class Solution:

	def printMissingIntervals(self, arr, n):
		arr.append(100000)
		l = []
		if arr[0] != 0:
			l.append(0)
			l.append(arr[0] - 1)
		for i in range(n):
			a = arr[i] + 1
			b = arr[i + 1] - 1
			if a <= b:
				l.append(a)
				l.append(b)
		return l


class Solution:

	def printMissingIntervals(self, a, n):
		lis = []
		for i in range(n):
			if i == 0:
				if a[i] != 0:
					lis.append(0)
					lis.append(a[i] - 1)
					continue
			elif a[i - 1] + 1 != a[i]:
				lis.append(a[i - 1] + 1)
				lis.append(a[i] - 1)
		if a[-1] != 99999:
			lis.append(a[-1] + 1)
			lis.append(99999)
		return lis
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		l = ob.printMissingIntervals(a, n)
		for i in range(0, len(l), 2):
			if l[i] == l[i + 1]:
				print(l[i], end='')
			else:
				print(l[i], end='')
				print('-', end='')
				print(l[i + 1], end='')
			if i != len(l) - 2:
				print(',', end='')
		print()


class Solution:

	def printMissingIntervals(self, a, n):
		ans = []
		if n == 0:
			return ans
		if a[0] != 0:
			ans.append(0)
			ans.append(a[0] - 1)
		for i in range(1, n):
			prev = a[i - 1]
			curr = a[i]
			if prev != curr - 1:
				ans.append(prev + 1)
				ans.append(curr - 1)
		if a[n - 1] != 99999:
			ans.append(a[n - 1] + 1)
			ans.append(99999)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		ob = Solution()
		l = ob.printMissingIntervals(a, n)
		for i in range(0, len(l), 2):
			if l[i] == l[i + 1]:
				print(l[i], end='')
			else:
				print(l[i], end='')
				print('-', end='')
				print(l[i + 1], end='')
			if i != len(l) - 2:
				print(',', end='')
		print()


from collections import deque

class Solution:

	def printMissingIntervals(self, a, n):
		q = deque()
		ub = 99999
		lb = None
		for i in range(len(a) - 1, -1, -1):
			if a[i] < ub:
				q.appendleft(ub)
				lb = a[i] + 1
				q.appendleft(lb)
				ub = a[i] - 1
			else:
				ub -= 1
		if a[0] != 0:
			q.appendleft(a[0] - 1)
			q.appendleft(0)
		return q


START_RANGE = 0
END_RANGE = 99999

class Solution:

	def printMissingIntervals(self, a, n):
		intervals = []
		start = START_RANGE
		for elem in a:
			if start == elem:
				start += 1
			else:
				intervals.extend([start, elem - 1])
				start = elem + 1
		if start <= END_RANGE:
			intervals.extend([start, END_RANGE])
		return intervals


class Solution:

	def printMissingIntervals(self, arr, n):
		ans = []
		for i in range(n):
			if i == 0:
				if arr[i] == 0:
					continue
				elif arr[i] == 1:
					ans.append(0)
					ans.append(0)
				else:
					ans.append(0)
					ans.append(arr[i] - 1)
			elif arr[i] - arr[i - 1] == 1:
				continue
			elif arr[i] - arr[i - 1] == 2:
				ans.append(arr[i] - 1)
				ans.append(arr[i] - 1)
			else:
				ans.append(arr[i - 1] + 1)
				ans.append(arr[i] - 1)
		if arr[-1] == 99998:
			ans.append(99999)
			ans.append(99999)
		elif arr[-1] < 99998:
			ans.append(arr[-1] + 1)
			ans.append(99999)
		return ans


class Solution:

	def printMissingIntervals(self, a, n):
		ans = []
		for i in range(n - 1):
			if a[i] + 1 == a[i + 1]:
				continue
			else:
				start = a[i] + 1
				end = a[i + 1] - 1
				ans.append(start)
				ans.append(end)
		if a[0] != 0:
			start = 0
			end = a[0] - 1
			ans.insert(0, start)
			ans.insert(1, end)
		if a[-1] != 99999:
			start = a[-1] + 1
			end = 99999
			ans.append(start)
			ans.append(end)
		return ans


class Solution:

	def printMissingIntervals(self, a, n):
		cnt = 0
		res = []
		for i in range(n):
			if a[i] != cnt:
				res.append(cnt)
				res.append(a[i] - 1)
				cnt = a[i] + 1
			else:
				cnt += 1
		if a[n - 1] != 99999:
			res.append(cnt)
			res.append(99999)
		return res


class Solution:

	def printMissingIntervals(self, a, n):
		missing = []
		curr_val = 0
		for val in a:
			dif = val - curr_val
			if dif:
				if dif == 1:
					missing += [curr_val, curr_val]
				else:
					missing += [curr_val, val - 1]
			curr_val = val + 1
		if curr_val != 100000:
			missing += [curr_val, 99999]
		return missing


class Solution:

	def printMissingIntervals(self, a, n):
		missing = []
		cur = 0
		for i in a:
			if i != cur:
				missing.append(cur)
				missing.append(i - 1)
				cur = i + 1
			else:
				cur += 1
		if a[-1] != 99999:
			missing.append(cur)
			missing.append(99999)
		return missing


class Solution:

	def printMissingIntervals(self, a, n):
		a = [-1] + a + [100000]
		i = 1
		ans = []
		while i < len(a):
			if a[i] != a[i - 1] + 1:
				ans.append(a[i - 1] + 1)
				ans.append(a[i] - 1)
			i += 1
		return ans


class Solution:

	def printMissingIntervals(self, a, n):
		a.sort()
		lo = 0
		hi = 99999
		missing = []
		if a[0] != lo:
			self.missing_range(lo, a[0] - 1, missing)
		for i in range(n - 1):
			self.missing_range(a[i] + 1, a[i + 1] - 1, missing)
		if a[-1] != hi:
			self.missing_range(a[-1] + 1, hi, missing)
		return missing

	def missing_range(self, i, j, missing):
		if i > j:
			return
		if i == j:
			missing.append(i)
			missing.append(j)
		else:
			missing.append(i)
			missing.append(j)
		return


class Solution:

	def printMissingIntervals(self, a, n):
		stack = []
		count = 0
		for num in a:
			if num == count:
				count += 1
			else:
				stack.append(count)
				stack.append(num - 1)
				count = num + 1
		if a[-1] != 99999:
			stack.append(count)
			stack.append(99999)
		return stack


class Solution:

	def printMissingIntervals(self, a, n):
		ranges = []
		if a[0] != 0:
			ranges.append([0, a[0] - 1])
		for i in range(n - 1):
			if a[i] != a[i + 1] - 1:
				ranges.append([a[i] + 1, a[i + 1] - 1])
		if a[-1] != 99999:
			ranges.append([a[-1] + 1, 99999])
		for (k, rng) in enumerate(ranges):
			if k != 0:
				print(',', end='')
			print(rng[0] if rng[0] == rng[1] else '{}-{}'.format(rng[0], rng[1]), end='')
		return []


class Solution:

	def printMissingIntervals(self, a, n):
		result = [0]
		for num in a:
			if result[-1] == num:
				result.pop()
			else:
				result.append(num - 1)
			if num < 99999:
				result.append(num + 1)
		if a[-1] < 99999:
			result.append(99999)
		return result


class Solution:

	def printMissingIntervals(self, a, n):
		a = set(a)
		missing = set()
		for i in range(0, max(a) + 1):
			if i not in a:
				missing.add(i)
		pairs = []
		for i in missing:
			if i - 1 not in missing:
				pairs.append(i)
			if i + 1 not in missing:
				pairs.append(i)
		if max(a) != 99999:
			pairs.append(max(a) + 1)
			pairs.append(99999)
		return pairs


class Solution:

	def printMissingIntervals(self, a, n):
		missing = []
		ans = []
		i = 0
		for j in range(100000):
			if i >= n or a[i] != j:
				if missing:
					missing[1] = j
				else:
					missing = [j, j]
			elif missing:
				ans.extend(missing)
				missing = []
				i += 1
			else:
				i += 1
		if missing:
			ans.extend(missing)
		return ans


class Solution:

	def printMissingIntervals(self, a, n):
		s = 0
		res = []
		for x in a:
			if x > s:
				res += [s, x - 1]
			s = x + 1
		if s <= 99999:
			res += [s, 99999]
		return res


class Solution:

	def printMissingIntervals(self, a, n):
		(next, end) = (0, 99999)
		result = []
		for i in range(n):
			if next != a[i]:
				result.append(next)
				result.append(a[i] - 1)
			next = a[i] + 1
		if next != end + 1:
			result.append(next)
			result.append(end)
		return result


class Solution:

	def printMissingIntervals(self, a, n):
		l = []
		if a[0] != 0:
			l.append(0)
			l.append(a[0] - 1)
		for i in range(0, n - 1):
			if a[i + 1] == a[i] + 1:
				pass
			else:
				l.append(a[i] + 1)
				l.append(a[i + 1] - 1)
		if a[n - 1] != 99999:
			l.append(a[n - 1] + 1)
			l.append(99999)
		return l


class Solution:

	def printMissingIntervals(self, arr, n):
		LIMIT = 100000
		seen = [False] * LIMIT
		for i in range(n):
			if arr[i] < LIMIT:
				seen[arr[i]] = True
		missing = []
		i = 0
		while i < LIMIT:
			if seen[i] == False:
				j = i + 1
				while j < LIMIT and seen[j] == False:
					j += 1
				p = j - 1
				missing.append(i)
				missing.append(p)
				i = j
			else:
				i += 1
		return missing


class Solution:

	def printMissingIntervals(self, nums, n):
		lower = 0
		upper = 99999
		res = []
		low = lower - 1
		nums.append(upper + 1)
		for num in nums:
			dif = num - low
			if dif == 2:
				res.extend([low + 1, low + 1])
			elif dif > 2:
				res.extend([low + 1, num - 1])
			low = num
		return res


class Solution:

	def printMissingIntervals(self, a, n):
		out = []
		last_seen = -1
		for i in range(n - 1):
			if a[i + 1] - a[i] > 1:
				out.append(a[i] + 1)
				out.append(a[i + 1] - 1)
		if a[0] != 0:
			out.insert(0, a[0] - 1)
			out.insert(0, 0)
		if a[-1] != 99999:
			out.append(a[-1] + 1)
			out.append(99999)
		return out


class Solution:

	def printMissingIntervals(self, a, n):
		hs = set(a)
		missing = set()
		for i in range(100000):
			if i not in hs:
				missing.add(i)
		pairs = []
		for m in missing:
			if m - 1 not in missing:
				pairs.append(m)
			if m + 1 not in missing:
				pairs.append(m)
		return pairs


class Solution:

	def printMissingIntervals(self, a, n):
		l = []
		for i in range(n + 1):
			if i == 0:
				if a[i] != 0:
					l.append(0)
					l.append(a[i] - 1)
			elif i > 0 and i < n:
				if a[i - 1] < a[i] - 1:
					l.append(a[i - 1] + 1)
					l.append(a[i] - 1)
			elif a[i - 1] != 99999:
				l.append(a[i - 1] + 1)
				l.append(99999)
		return l


class Solution:

	def produce_interval(self, lower, upper):
		if lower == upper - 1:
			return [str(lower), str(lower)]
		return [str(lower), str(upper - 1)]

	def printMissingIntervals(self, arr, n):
		missing_intervals = []
		lower = -1
		upper = 99999
		for i in range(n):
			a = arr[i]
			if a > lower + 1:
				interval = self.produce_interval(lower + 1, a)
				missing_intervals.extend(interval)
			lower = a
		if lower != upper:
			interval = self.produce_interval(lower + 1, upper + 1)
			missing_intervals.extend(interval)
		return missing_intervals