Given a sorted array having N elements, find the indices of the first and last occurrences of an element X in the given array.
Note: If the number X is not found in the array, return '-1' as an array.
Example 1:
Input:
N = 4 , X = 3
arr[] = { 1, 3, 3, 4 }
Output:
1 2
Explanation:
For the above array, first occurence
of X = 3 is at index = 1 and last
occurence is at index = 2.
Example 2:
Input:
N = 4, X = 5
arr[] = { 1, 2, 3, 4 }
Output:
-1
Explanation: 
As 5 is not present in the array,
so the answer is -1.
Your Task:
You don't need to read input or print anything. Complete the function firstAndLast() that takes the array arr, its size N and the value X as input parameters and returns a list of integers containing the indices of first and last occurence of X.
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
Constraints: 
1 <= N <= 10^5 
0 <= arr[i], X <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3

class Solution: 

    def firstAndLast(self, arr, n, x): 

        # Code here

Solutions:
class Solution:

	def firstAndLast(self, arr, n, x):
		k = '-1'
		if x not in arr:
			return [-1]
		c = arr.count(x)
		q = arr.index(x)
		return (q, q + c - 1)


class Solution:

	def firstAndLast(self, arr, n, x):
		index = [-1, -1]
		if x in arr:
			index[0] = arr.index(x)
			for (i, num) in enumerate(reversed(arr)):
				if num == x:
					index[1] = n - i - 1
					return index
		return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		if n == 0:
			return [-1]
		list = []
		for i in range(n):
			if arr[i] == x:
				list.append(i)
		if len(list) == 0:
			return [-1]
		return [list[0], list[-1]]


class Solution:

	def lb(self, x):
		left = -1
		right = len(arr)
		while right > left + 1:
			mid = left + (right - left) // 2
			if arr[mid] >= x:
				right = mid
			else:
				left = mid
		return -1 if right == len(arr) or arr[right] != x else right

	def ub(self, x):
		left = -1
		right = len(arr)
		while right > left + 1:
			mid = left + (right - left) // 2
			if arr[mid] <= x:
				left = mid
			else:
				right = mid
		return -1 if left == -1 or arr[left] != x else left

	def firstAndLast(self, arr, n, x):
		a = self.lb(x)
		b = self.ub(x)
		return [-1] if a == -1 else [a, b]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		first = -1
		last = -1
		for i in range(n):
			if arr[i] == x and first == -1:
				first = i
				last = i
			if arr[i] == x and last != -1:
				last = i
		return [first, last]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x in arr:
			m = arr.index(x)
			r = arr[::-1].index(x)
			return [m, n - (r + 1)]
		return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		return (arr.index(x), n - arr[::-1].index(x) - 1)


class Solution:

	def firstAndLast(self, arr, n, x):
		l = []
		i = 0
		while i < n:
			if arr[i] == x:
				l.append(i)
			i += 1
		if len(l) == 0:
			return [-1]
		return [l[0], l[-1]]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		i = 0
		while i < n:
			if arr[i] == x:
				a = i
				break
			else:
				a = -1
			i += 1
		j = n - 1
		while j >= 0:
			if arr[j] == x:
				b = j
				break
			else:
				b = -1
			j -= 1
		return (a, b)


class Solution:

	def firstAndLast(self, arr, n, x):
		l1 = []
		for i in range(n):
			if arr[i] == x:
				l1.append(i)
		if l1 != []:
			return (min(l1), max(l1))
		else:
			return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		if arr.count(x) == 0:
			return (-1, ' ')
		f = arr.index(x)
		arr = arr[::-1]
		l = arr.index(x)
		lf = n - 1 - l
		return (f, lf)


class Solution:

	def firstAndLast(self, arr, n, x):
		if x in arr:
			res = []
			res.append(arr.index(x))
			arr.reverse()
			res.append(n - arr.index(x) - 1)
			return res
		return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		z = []
		if x not in arr:
			return [-1]
		for i in range(len(arr) - 1):
			if arr[i] == x:
				a = i
				z.append(a)
			if arr[i] == x and arr[i + 1] != x:
				b = i
				z.append(b)
		if x in arr and arr[n - 1] == x:
			b = n - 1
			z.append(b)
		return (min(z), b)


class Solution:

	def firstAndLast(self, arr, n, x):
		s = 0
		e = n - 1
		f = -1
		l = -1
		while s <= e:
			mid = (s + e) // 2
			if arr[mid] == x:
				f = mid
				e = mid - 1
			if arr[mid] > x:
				e = mid - 1
			if arr[mid] < x:
				s = mid + 1
		s = 0
		e = n - 1
		while s <= e:
			mid = (s + e) // 2
			if arr[mid] == x:
				l = mid
				s = mid + 1
			if arr[mid] > x:
				e = mid - 1
			if arr[mid] < x:
				s = mid + 1
		if f == -1 and l == -1:
			return [-1]
		return [f, l]


class Solution:

	def firstAndLast(self, arr, n, x):
		l = []
		l2 = []
		l3 = [-1]
		for i in range(n):
			if arr[i] == x:
				l.append(i)
		if len(l) > 0:
			l2.append(min(l))
			l2.append(max(l))
			return l2
		else:
			return l3


class Solution:

	def firstoccurence(self, arr, n, x):
		l = 0
		r = n - 1
		ans = -1
		while l <= r:
			mid = l + (r - l) // 2
			if arr[mid] == x:
				r = mid - 1
				ans = mid
			elif arr[mid] > x:
				r = mid - 1
			else:
				l = mid + 1
		return ans

	def lastoccurence(self, arr, n, x):
		l = 0
		r = n - 1
		ans = -1
		while l <= r:
			mid = l + (r - l) // 2
			if arr[mid] == x:
				l = mid + 1
				ans = mid
			elif arr[mid] > x:
				r = mid - 1
			else:
				l = mid + 1
		return ans

	def firstAndLast(self, arr, n, x):
		lo = self.lastoccurence(arr, n, x)
		fo = self.firstoccurence(arr, n, x)
		if lo == -1 and fo == -1:
			return [-1]
		return [fo, lo]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		else:
			ln = []
			for (idx, each) in enumerate(arr):
				if each == x:
					ln.append(idx)
			return [min(ln), max(ln)]


class Solution:

	def firstAndLast(self, arr, n, x):
		p = -1
		l = []
		for i in range(n):
			if arr[i] == x:
				l += [i]
				break
		for i in range(n):
			if arr[i] == x:
				p = i
		l.append(p)
		if len(l) == 0:
			return -1
		else:
			return l


class Solution:

	def firstAndLast(self, arr, n, x):

		def first_and_last(arr, n, x, right_or_left):
			high = n - 1
			low = 0
			ans = -1
			while low <= high:
				mid = low + (high - low) // 2
				if x == arr[mid]:
					ans = mid
					if right_or_left == True:
						high = mid - 1
					else:
						low = mid + 1
				elif x > arr[mid]:
					low = mid + 1
				else:
					high = mid - 1
			return ans
		right = first_and_last(arr, n, x, True)
		if right == -1:
			return [-1]
		else:
			left = first_and_last(arr, n, x, False)
			return (right, left)


class Solution:

	def firstAndLast(self, arr, n, x):
		start = 0
		end = n - 1
		l = []
		ans = -1
		while start <= end:
			mid = int((start + end) / 2)
			if x == arr[mid]:
				ans = mid
				end = mid - 1
			elif x > arr[mid]:
				start = mid + 1
			else:
				end = mid - 1
		l.append(ans)
		start = 0
		end = n - 1
		ans = -1
		while start <= end:
			mid = int((start + end) / 2)
			if x == arr[mid]:
				ans = mid
				start = mid + 1
			elif x > arr[mid]:
				start = mid + 1
			else:
				end = mid - 1
		if ans != -1:
			l.append(ans)
		return l


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		a = []
		for i in range(n):
			if arr[i] == x:
				a.append(i)
		return [a[0], a[-1]]


class Solution:

	def firstAndLast(self, arr, n, x):

		def firstoccurance(arr, s, e):
			start = s
			end = e
			while start <= end:
				mid = (start + end) // 2
				if arr[mid] < x:
					start = mid + 1
				elif arr[mid] > x:
					end = mid - 1
				elif arr[mid] == x:
					if mid - 1 > -1 and arr[mid - 1] == x:
						end = mid - 1
					else:
						return mid
			return -1

		def secondoccurance(arr, s, e):
			start = s
			end = e
			while start <= end:
				mid = (start + end) // 2
				if arr[mid] < x:
					start = mid + 1
				elif arr[mid] > x:
					end = mid - 1
				elif arr[mid] == x:
					if mid + 1 < e + 1 and arr[mid + 1] == x:
						start = mid + 1
					else:
						return mid
			return -1
		l = []
		l.append(firstoccurance(arr, 0, n - 1))
		l.append(secondoccurance(arr, 0, n - 1))
		if l[0] == -1 and l[1] == -1:
			return [-1]
		return l


class Solution:

	def firstAndLast(self, arr, n, x):
		start = 0
		end = n - 1
		res = -1
		res2 = -1
		while start <= end:
			mid = (start + end) // 2
			if x == arr[mid]:
				res = mid
				end = mid - 1
			elif x < arr[mid]:
				end = mid - 1
			elif x > arr[mid]:
				start = mid + 1
		start = 0
		end = n - 1
		while start <= end:
			mid = (start + end) // 2
			if x == arr[mid]:
				res2 = mid
				start = mid + 1
			elif x < arr[mid]:
				end = mid - 1
			elif x > arr[mid]:
				start = mid + 1
		if res == -1 and res2 == -1:
			return (res,)
		else:
			return (res, res2)


class Solution:

	def firstAndLast(self, arr, n, x):
		l = []
		m = 0
		for i in range(n):
			if arr[i] == x:
				l.append(i)
				m = 1
				break
		for i in range(n - 1, -1, -1):
			if arr[i] == x:
				l.append(i)
				break
		if m == 0:
			l.append(-1)
		return l


class Solution:

	def firstAndLast(self, arr, n, x):
		if x in arr:
			a = arr.index(x)
			arr.reverse()
			b = len(arr) - arr.index(x) - 1
			return [a, b]
		else:
			return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		l = 0
		h = n - 1
		while l <= h:
			m = l + (h - l) // 2
			if arr[m] == x:
				(f, l) = (m, m)
				while f >= 0 and arr[f] == x:
					f = f - 1
				while l <= n - 1 and arr[l] == x:
					l = l + 1
				return (f + 1, l - 1)
			elif arr[m] < x:
				l = m + 1
			elif arr[m] > x:
				h = m - 1
		return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		l = []
		for i in range(n):
			if arr[i] == x:
				l.append(i)
		try:
			return (l[0], l[-1])
		except:
			return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		i = 0
		j = n - 1
		first = 0
		last = 0
		while i <= j:
			if arr[i] == x:
				first = i
				break
			i += 1
		i = 0
		while j > i:
			if arr[j] == x:
				last = j
				break
			j -= 1
		return (first, last)


class Solution:

	def firstAndLast(self, arr, n, x):
		first_occ = -1
		start = 0
		end = len(arr) - 1
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == x:
				first_occ = mid
				end = mid - 1
			elif arr[mid] < x:
				start = mid + 1
			else:
				end = mid - 1
		last_occ = -1
		start = 0
		end = len(arr) - 1
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == x:
				last_occ = mid
				start = mid + 1
			elif arr[mid] < x:
				start = mid + 1
			else:
				end = mid - 1
		if first_occ == -1 or last_occ == -1:
			return [-1]
		return [first_occ, last_occ]


class Solution:

	def firstAndLast(self, arr, n, x):
		ans = []
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == x:
				if mid + 1 < n and arr[mid + 1] == x:
					low = mid + 1
				else:
					ans.append(mid)
					break
			elif arr[mid] > x:
				high = mid - 1
			else:
				low = mid + 1
		high = n - 1
		low = 0
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == x:
				if mid > 0 and arr[mid - 1] == x:
					high = mid - 1
				else:
					ans.append(mid)
					break
			elif arr[mid] > x:
				high = mid - 1
			else:
				low = mid + 1
		if len(ans) == 0:
			return [-1]
		else:
			return ans[::-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		i = 0
		j = len(arr) - 1
		l = -1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] == x:
				l = mid
				j = mid - 1
			elif arr[mid] > x:
				j = mid - 1
			else:
				i = mid + 1
		i = 0
		j = len(arr) - 1
		r = -1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] == x:
				r = mid
				i = mid + 1
			elif arr[mid] > x:
				j = mid - 1
			else:
				i = mid + 1
		if r != -1 and l != -1:
			return [l, r]
		return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x in arr:
			r = [-1, -1]
			for i in range(n):
				if arr[i] == x:
					r[0] = i
					break
			for i in range(n - 1, -1, -1):
				if arr[i] == x:
					r[1] = i
					break
			return r
		else:
			return [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		if n <= 0:
			return -1
		first = last = -1
		for i in range(0, n):
			if x == arr[i]:
				if first == -1:
					last = first = i
				else:
					last = i
		if first == -1:
			return [-1]
		return [first, last]


class Solution:

	def firstAndLast(self, arr, n, x):
		a = []
		b = [-1]
		for i in range(n):
			if arr[i] == x:
				a.append(i)
				break
		for j in range(n - 1, -1, -1):
			if arr[j] == x:
				a.append(j)
				break
		if x in arr:
			return a
		else:
			return b


class Solution:

	def firstAndLast(self, arr, n, x):
		return [arr.index(x), n - arr[::-1].index(x) - 1] if arr.count(x) > 0 else [-1]


class Solution:

	def firstAndLast(self, arr, n, x):
		lst = []
		if x not in arr:
			lst.append(-1)
			return lst
		lst.append(arr.index(x))
		arr.reverse()
		lst.append(n - 1 - arr.index(x))
		return lst


class Solution:

	def firstAndLast(self, arr, n, x):

		def sf(a, t, m):
			if a[m] == t:
				if a[m - 1] == t and m - 1 >= 0:
					return 'left'
				else:
					return 'found'
			elif a[m] < t:
				return 'right'
			else:
				return 'left'

		def sl(a, t, m):
			if a[m] == t:
				if m + 1 <= len(a) - 1 and a[m + 1] == t and (m + 1 >= 0):
					return 'right'
				else:
					return 'found'
			elif a[m] < t:
				return 'right'
			else:
				return 'left'

		def si(a, t, k):
			(l, h) = (0, len(a) - 1)
			while l <= h:
				m = (l + h) // 2
				if k == 'first':
					res = sf(a, t, m)
				else:
					res = sl(a, t, m)
				if res == 'found':
					return m
				elif res == 'left':
					h = m - 1
				else:
					l = m + 1
			return -1
		if [si(arr, x, 'first'), si(arr, x, 'last')] == [-1, -1]:
			return [-1]
		else:
			return [si(arr, x, 'first'), si(arr, x, 'last')]


from bisect import bisect_right, bisect_left

class Solution:

	def firstAndLast(self, arr, n, x):
		(i, j) = (bisect_left(arr, x), bisect_right(arr, x) - 1)
		try:
			if arr[i] == arr[j] == x:
				return (i, j)
			return ['-1']
		except:
			return ['-1']


class Solution:

	def firstAndLast(self, arr, n, x):
		import bisect
		if x not in arr:
			return [-1]
		li = bisect.bisect_left(arr, x)
		ri = bisect.bisect_right(arr, x) - 1
		return (li, ri)


class Solution:

	def firstAndLast(self, arr, n, x):
		a = []
		b = []
		for i in range(len(arr)):
			if arr[i] == x:
				a.append(i)
		if len(a) >= 1:
			b.append(a[0])
			b.append(a[-1])
			return b
		else:
			b.append(-1)
			return b


class Solution:

	def firstAndLast(self, arr, n, x):
		arr1 = []
		count_x = arr.count(x)
		if count_x == 1:
			arr1.append(arr.index(x))
			arr1.append(arr.index(x))
		elif count_x >= 2:
			arr1.append(arr.index(x))
			arr1.append(arr.index(x) + (count_x - 1))
		else:
			arr1.append(-1)
		return arr1


class Solution:

	def firstAndLast(self, arr, n, x):
		res = [-1, -1]
		for i in range(n):
			if arr[i] == x:
				if res[0] == -1:
					res[0] = i
				res[1] = i
		if res[0] == -1 and res[1] == -1:
			return [-1]
		return res


class Solution:

	def firstAndLast(self, arr, n, x):
		r = [arr.count(x)]
		if r == [0]:
			return [-1]
		else:
			l = []
			l.append(arr.index(x))
			arr = arr[::-1]
			l.append(abs(arr.index(x) - n + 1))
			return l


class Solution:

	def firstAndLast(self, arr, n, x):
		first = -1
		last = -1
		for index in range(n):
			if arr[index] == x and first == -1:
				first = index
				last = index
			elif arr[index] == x:
				last = index
		return [-1] if first == -1 else [first, last]


class Solution:

	def firstAndLast(self, arr, n, x):
		if x not in arr:
			return [-1]
		res = []
		for i in range(n):
			if arr[i] == x:
				res.append(i)
		return [res[0], res[0]] if len(res) == 1 else [res[0], res[-1]]


class Solution:

	def firstAndLast(self, arr, n, x):
		li = []
		for i in range(n):
			if arr[i] == x:
				li.append(i)
				break
		for i in reversed(range(n)):
			if arr[i] == x:
				li.append(i)
				break
		if x not in arr:
			li.append(-1)
			return li
		return li


class Solution:

	def firstAndLast(self, arr, n, x):
		f = first(self, arr, n, x)
		l = Last(self, arr, n, x)
		if f == -1 and l == -1:
			return (-1,)
		else:
			return (f, l)

def first(self, arr, n, x):
	s = 0
	e = n - 1
	p = 1
	q = 0
	o = 1
	r = 0
	while s <= e:
		m = (s + e) // 2
		if arr[m] == x:
			if m == 0 or arr[m - 1] != x:
				return m
			else:
				e = m - 1
		elif arr[m] < x:
			s = m + 1
		else:
			e = m - 1
	return -1

def Last(self, arr, n, x):
	s = 0
	e = n - 1
	p = 1
	q = 0
	o = 1
	r = 0
	while s <= e:
		m = (s + e) // 2
		if arr[m] == x:
			if m == n - 1 or arr[m + 1] != x:
				return m
			else:
				s = m + 1
		elif arr[m] < x:
			s = m + 1
		else:
			e = m - 1
	return -1


class Solution:

	def firstAndLast(self, arr, n, x):
		l = 0
		h = n - 1
		left = -1
		right = -1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] == x:
				left = mid
				h = mid - 1
			elif arr[mid] < x:
				l = mid + 1
			else:
				h = mid - 1
		l = 0
		h = n - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] == x:
				right = mid
				l = mid + 1
			elif arr[mid] < x:
				l = mid + 1
			else:
				h = mid - 1
		if left == -1:
			return [-1]
		return (left, right)


class Solution:

	def firstAndLast(self, arr, n, x):
		l = []
		s = 0
		for i in range(n):
			if arr[i] == x:
				s = 1
				l.append(i)
		if s == 0:
			return [-1]
		else:
			return (l[0], l[-1])


class Solution:

	def firstAndLast(self, arr, n, x):
		l = []
		i = 0
		if x not in arr:
			return [-1]
		for a in arr:
			if a == x:
				l.append(i)
			i += 1
		return [min(l), max(l)]


class Solution:

	def firstAndLast(self, arr, n, x):
		first = self.first_occurance(arr, n, x)
		last = self.last_occurance(arr, n, x)
		if first != -1 and last != -1:
			return [first, last]
		else:
			return [-1]

	def first_occurance(self, arr, n, x):
		l = 0
		h = n - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] > x:
				h = mid - 1
			elif arr[mid] < x:
				l = mid + 1
			elif mid == 0 or arr[mid - 1] != arr[mid]:
				return mid
			else:
				h = mid - 1
		return -1

	def last_occurance(self, arr, n, x):
		l = 0
		h = n - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] > x:
				h = mid - 1
			elif arr[mid] < x:
				l = mid + 1
			elif mid == n - 1 or arr[mid + 1] != arr[mid]:
				return mid
			else:
				l = mid + 1
		return -1


class Solution:

	def firstAndLast(self, arr, n, x):
		c = arr.count(x)
		if c == 0:
			return [-1]
		else:
			a = arr.index(x)
			l = [a]
			for i in range(c - 1):
				a = arr.index(x, a + 1)
			l.append(a)
			return l


class Solution:

	def firstAndLast(self, arr, n, x):
		l = 0
		r = n - 1
		an = -1
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] < x:
				l = mid + 1
			elif arr[mid] > x:
				r = mid - 1
			else:
				an = mid
				break
		if an == -1:
			return [-1]
		else:
			l = mid
			r = mid
			while l >= 0 and arr[l] == x:
				l -= 1
			while r < n and arr[r] == x:
				r += 1
			return [l + 1, r - 1]