Given two sorted arrays arr1 and arr2 of size N and M respectively and an element K. The task is to find the element that would be at the kth position of the final sorted array.
 
Example 1:
Input:
arr1[] = {2, 3, 6, 7, 9}
arr2[] = {1, 4, 8, 10}
k = 5
Output:
6
Explanation:
The final sorted array would be -
1, 2, 3, 4, 6, 7, 8, 9, 10
The 5th element of this array is 6.
Example 2:
Input:
arr1[] = {100, 112, 256, 349, 770}
arr2[] = {72, 86, 113, 119, 265, 445, 892}
k = 7
Output:
256
Explanation:
Final sorted array is - 72, 86, 100, 112,
113, 119, 256, 265, 349, 445, 770, 892
7th element of this array is 256.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function kthElement() which takes the arrays arr1[], arr2[], its size N and M respectively and an integer K as inputs and returns the element at the Kth position.
Expected Time Complexity: O(Log(N) + Log(M))
Expected Auxiliary Space: O(Log (N))
Constraints:
1 <= N, M <= 10^{6}
0 <= arr1_{i}, arr2_{i} < INT_MAX
1 <= K <= N+M

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Divide and conquer

Starter code: #User function Template for python3



class Solution:

    def kthElement(self,  arr1, arr2, n, m, k):

        

        

        

Solutions:
class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr = arr1 + arr2
		arr.sort()
		return arr[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		l = []
		arr = sorted(arr1 + arr2)
		for i in range(k):
			l.append(arr[i])
		return l[-1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		count = 0
		(i, j) = (0, 0)
		r = []
		while i < n and j < m:
			if arr1[i] <= arr2[j]:
				r.append(arr1[i])
				temp = arr1[i]
				count += 1
				i = i + 1
			else:
				r.append(arr2[j])
				temp = arr2[j]
				count += 1
				j = j + 1
			if count == k:
				return temp
		r = r + arr1[i:] + arr2[j:]
		return r[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		a = 0
		b = 0
		arr = [-1] * (n + m)
		i = 0
		while a < n and b < m:
			if arr1[a] < arr2[b]:
				arr[i] = arr1[a]
				i += 1
				a += 1
			elif arr1[a] > arr2[b]:
				arr[i] = arr2[b]
				i += 1
				b += 1
			else:
				arr[i] = arr1[a]
				i += 1
				a += 1
				arr[i] = arr2[b]
				i += 1
				b += 1
		while a < n:
			arr[i] = arr1[a]
			a += 1
			i += 1
		while b < m:
			arr[i] = arr2[b]
			b += 1
			i += 1
		return arr[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		new_arr = sorted(arr1 + arr2)
		if len(new_arr) >= k:
			return new_arr[k - 1]
		return -1


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		f = 0
		s = 0
		final_arr = []
		while f < n and s < m:
			if arr1[f] <= arr2[s]:
				final_arr.append(arr1[f])
				f += 1
			else:
				final_arr.append(arr2[s])
				s += 1
		if f == n:
			final_arr.extend(arr2[s:])
		elif s == m:
			final_arr.extend(arr1[f:])
		return final_arr[k - 1]


import bisect

class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr3 = []
		for i in range(n):
			bisect.insort(arr3, arr1[i])
		for i in range(m):
			bisect.insort(arr3, arr2[i])
		return arr3[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr3 = [] * (n + m)
		for x in arr1 + arr2:
			arr3.append(x)
		arr3.sort()
		return arr3[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		(i, j, count) = (0, 0, 0)
		for length in range(k):
			if arr1[i] < arr2[j]:
				count += 1
				if count != k:
					if i < n - 1:
						i += 1
					else:
						arr1[i] = arr2[m - 1]
				else:
					return arr1[i]
			else:
				count += 1
				if count != k:
					if j < m - 1:
						j += 1
					else:
						arr2[j] = arr1[n - 1]
				else:
					return arr2[j]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		return sorted(arr1 + arr2)[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		temp = []
		for i in range(n):
			temp.append(arr1[i])
		for i in range(m):
			temp.append(arr2[i])
		temp.sort()
		return temp[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		(l, r) = (0, 0)
		a = []
		o = k
		while k > 0:
			if l < n and r < m:
				if arr1[l] < arr2[r]:
					a.append(arr1[l])
					l += 1
				elif arr1[l] > arr2[r]:
					a.append(arr2[r])
					r += 1
				else:
					a.append(arr1[l])
					a.append(arr1[l])
					r += 1
					l += 1
			elif l >= n and r < m:
				a.append(arr2[r])
				r += 1
			elif r >= m and l < n:
				a.append(arr1[l])
				l += 1
			k -= 1
		return a[o - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		(p1, p2) = (0, 0)
		c = 0
		while p1 < n and p2 < m:
			c += 1
			if arr1[p1] < arr2[p2]:
				if c == k:
					return arr1[p1]
				p1 += 1
			else:
				if c == k:
					return arr2[p2]
				p2 += 1
		while p1 < n:
			c += 1
			if c == k:
				return arr1[p1]
			p1 += 1
		while p2 < m:
			c += 1
			if c == k:
				return arr2[p2]
			p2 += 1


class Solution:

	def kthElement(self, arr1, arr2, n1, n2, k):
		if n2 < n1:
			return self.kthElement(arr2, arr1, n2, n1, k)
		low = max(0, k - n2)
		high = min(n1, k)
		while low <= high:
			cut1 = (low + high) // 2
			cut2 = k - cut1
			l1 = float('-inf') if cut1 == 0 else arr1[cut1 - 1]
			l2 = float('-inf') if cut2 == 0 else arr2[cut2 - 1]
			r1 = float('inf') if cut1 == n1 else arr1[cut1]
			r2 = float('inf') if cut2 == n2 else arr2[cut2]
			if l1 <= r2 and l2 <= r1:
				return max(l1, l2)
			elif l1 > r2:
				high = cut1 - 1
			elif l2 > r1:
				low = cut1 + 1


def countLessThanEqualTo(l, n, k):
	(lo, hi) = (0, n - 1)
	while lo <= hi:
		mid = lo + hi >> 1
		if l[mid] <= k:
			lo = mid + 1
		else:
			hi = mid - 1
	return lo

class Solution:

	def kthElement(self, l1, l2, n, m, k):
		(lo, hi) = (0, 10 ** 12)
		while lo <= hi:
			mid = lo + hi >> 1
			le1 = countLessThanEqualTo(l1, n, mid)
			le2 = countLessThanEqualTo(l2, m, mid)
			if le1 + le2 <= k - 1:
				lo = mid + 1
			else:
				hi = mid - 1
		return lo


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		if arr1[-1] > arr2[0]:
			(i, j) = (len(arr1) - 1, 0)
			while i >= 0 and j < len(arr2):
				if arr1[i] > arr2[j]:
					(arr1[i], arr2[j]) = (arr2[j], arr1[i])
				i = i - 1
				j = j + 1
		arr1 = sorted(arr1)
		arr2 = sorted(arr2)
		if k <= len(arr1):
			return arr1[k - 1]
		else:
			return arr2[k - len(arr1) - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		l = list(arr1)
		m = list(arr2)
		a = [*l, *m]
		a.sort()
		return a[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		i = 0
		j = 0
		x = 0
		while k > 0:
			if i < len(arr1) and j < len(arr2):
				if arr1[i] > arr2[j]:
					x = arr2[j]
					j += 1
				else:
					x = arr1[i]
					i += 1
				k -= 1
			elif i >= len(arr1):
				x = arr2[j + k - 1]
				break
			else:
				x = arr1[i + k - 1]
				break
		return x


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		c = []
		c.extend(arr1)
		c.extend(arr2)
		c.sort()
		return c[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		if n > m:
			return self.kthElement(arr2, arr1, m, n, k)
		left = max(0, k - m)
		right = min(n, k)
		while left < right:
			i = (left + right) // 2
			j = k - i
			if arr1[i] < arr2[j - 1]:
				left = i + 1
			else:
				right = i
		i = left
		j = k - i
		if i == 0:
			return arr2[j - 1]
		elif j == 0:
			return arr1[i - 1]
		else:
			return max(arr1[i - 1], arr2[j - 1])


class Solution:

	def kthElement(self, arr1, arr2, N, M, k):
		(i, j) = (max(0, k - M), min(k, N))
		while i <= j:
			m = i + j >> 1
			(c1, c2) = (m, k - m)
			l1 = arr1[c1 - 1] if c1 > 0 else float('-inf')
			l2 = arr2[c2 - 1] if c2 > 0 else float('-inf')
			r1 = arr1[c1] if c1 < N else float('inf')
			r2 = arr2[c2] if c2 < M else float('inf')
			if l1 <= r2 and l2 <= r1:
				return max(l1, l2)
			if l1 > r2:
				j = m - 1
			else:
				i = m + 1
		return -1


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		s = []
		x = 0
		y = 0
		while x < n and y < m:
			if arr1[x] < arr2[y]:
				s.append(arr1[x])
				x = x + 1
			else:
				s.append(arr2[y])
				y += 1
		while x < n:
			s.append(arr1[x])
			x += 1
		while y < m:
			s.append(arr2[y])
			y = y + 1
		return s[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		new_arr = []
		for each in arr1:
			new_arr.append(each)
		for each in arr2:
			new_arr.append(each)
		new_arr.sort()
		return new_arr[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		p = 0
		q = 0
		while p < n and q < m:
			if p + q == k - 1:
				return min(arr1[p], arr2[q])
			a = arr1[p]
			b = arr2[q]
			if a <= b:
				p += 1
			else:
				q += 1
		if p < n:
			return arr1[p + (k - q - p) - 1]
		elif q < m:
			return arr2[q + (k - q - p) - 1]
		else:
			return -1


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		if len(arr2) < len(arr1):
			return self.kthElement(arr2, arr1, m, n, k)
		l = max(0, k - m)
		h = min(k, n)
		while l <= h:
			c1 = (l + h) // 2
			c2 = k - c1
			l1 = float('-inf') if c1 == 0 else arr1[c1 - 1]
			l2 = float('-inf') if c2 == 0 else arr2[c2 - 1]
			r1 = float('+inf') if c1 == n else arr1[c1]
			r2 = float('+inf') if c2 == m else arr2[c2]
			if l1 <= r2 and l2 <= r1:
				return max(l1, l2)
			elif l1 < r2:
				l = c1 + 1
			else:
				h = c1 - 1
		return -1


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr = arr1 + arr2
		x = list(arr)
		y = sorted(x)
		return y[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		if len(arr1) > len(arr2):
			return self.kthElement(arr2, arr1, m, n, k)
		lo = max(0, k - m)
		hi = min(k, n)
		while lo <= hi:
			cut1 = lo + (hi - lo) // 2
			cut2 = k - cut1
			l1 = arr1[cut1 - 1] if cut1 > 0 else float('-inf')
			l2 = arr2[cut2 - 1] if cut2 > 0 else float('-inf')
			r1 = arr1[cut1] if cut1 < n else float('inf')
			r2 = arr2[cut2] if cut2 < m else float('inf')
			if l1 <= r2 and l2 <= r1:
				return max(l1, l2)
			elif l1 > r2:
				hi = cut1 - 1
			else:
				lo = cut1 + 1


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		i = 0
		ans = []
		j = 0
		count = 0
		while i < len(arr1) and j < len(arr2):
			if arr1[i] > arr2[j]:
				ans.append(arr2[j])
				count += 1
				j += 1
			else:
				ans.append(arr1[i])
				count += 1
				i += 1
			if count == k:
				return ans[-1]
		while i < n:
			ans.append(arr1[i])
			count += 1
			i += 1
			if count == k:
				return ans[-1]
		while j < m:
			ans.append(arr2[j])
			count += 1
			j += 1
			if count == k:
				return ans[-1]
		return ans[k - 1]


class Solution(object):

	def kthElement(self, nums1, nums2, n, m, k):
		if n > m:
			return self.kthElement(nums2, nums1, m, n, k)
		left = max(0, k - m)
		right = min(k, n)
		while left <= right:
			cut1 = (left + right) // 2
			cut2 = k - cut1
			l1 = float('-inf') if cut1 == 0 else nums1[cut1 - 1]
			l2 = float('-inf') if cut2 == 0 else nums2[cut2 - 1]
			r1 = float('inf') if cut1 == n else nums1[cut1]
			r2 = float('inf') if cut2 == m else nums2[cut2]
			if l1 <= r2 and l2 <= r1:
				return max(l1, l2)
			elif l1 > r2:
				right = cut1 - 1
			else:
				left = cut1 + 1
		return -1


def kth(arr1, arr2, s1, e1, s2, e2, k):
	if s1 == e1:
		return arr2[s2 + k]
	if s2 == e2:
		return arr1[s1 + k]
	m1 = (e1 - s1) // 2
	m2 = (e2 - s2) // 2
	if m1 + m2 < k:
		if arr1[s1 + m1] > arr2[s2 + m2]:
			return kth(arr1, arr2, s1, e1, s2 + m2 + 1, e2, k - m2 - 1)
		else:
			return kth(arr1, arr2, s1 + m1 + 1, e1, s2, e2, k - m1 - 1)
	elif arr1[s1 + m1] > arr2[s2 + m2]:
		return kth(arr1, arr2, s1, s1 + m1, s2, e2, k)
	else:
		return kth(arr1, arr2, s1, e1, s2, s2 + m2, k)

class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		return kth(arr1, arr2, 0, n, 0, m, k - 1)


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr = arr1 + arr2
		arr.sort()
		try:
			arr[k - 1]
			return arr[k - 1]
		except:
			return 0


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr = sorted(arr1 + arr2)
		if k > n + m:
			return -1
		else:
			return arr[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr = []
		i = 0
		j = 0
		count = 0
		while i < len(arr1) and j < len(arr2):
			if arr1[i] < arr2[j]:
				arr.append(arr1[i])
				count = count + 1
				i = i + 1
			elif arr2[j] < arr1[i]:
				arr.append(arr2[j])
				count = count + 1
				j = j + 1
			else:
				arr.append(arr1[i])
				arr.append(arr2[j])
				i = i + 1
				j = j + 1
				count = count + 2
		while i < len(arr1):
			arr.append(arr1[i])
			i = i + 1
		while j < len(arr2):
			arr.append(arr2[j])
			j = j + 1
		return arr[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, target):
		(i, j) = (0, 0)
		k = n - 1
		while i <= k and j < m:
			if arr1[i] < arr2[j]:
				i += 1
			else:
				(arr1[k], arr2[j]) = (arr2[j], arr1[k])
				j += 1
				k -= 1
		arr1.sort()
		arr2.sort()
		arr1 = list(arr1)
		arr2 = list(arr2)
		arr = arr1 + arr2
		return arr[target - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		if n <= m:
			a = arr1
			b = arr2
			low = 0
			high = n - 1
		else:
			a = arr2
			b = arr1
			low = 0
			high = m - 1
		while low <= high:
			cut1 = (low + high) // 2
			cut2 = k - (cut1 + 1) - 1
			if cut1 <= k - 1 and cut2 <= len(b) - 1:
				if cut1 < 0:
					l1 = -100
				else:
					l1 = a[cut1]
				if cut2 < 0:
					l2 = -100
				else:
					l2 = b[cut2]
				if cut1 == len(a) - 1:
					r1 = max(b) + 1
				else:
					r1 = a[cut1 + 1]
				if cut2 == len(b) - 1:
					r2 = max(a) + 1
				else:
					r2 = b[cut2 + 1]
				if l1 <= r2 and l2 <= r1:
					return max(l1, l2)
				elif l1 > r2:
					high = cut1 - 1
				elif l2 > r1:
					low = cut1 + 1
			elif cut1 <= k - 1 and cut2 > len(b) - 1:
				low = cut1 + 1
			elif cut1 > k - 1:
				high = cut1 - 1
		cut2 = k - (high + 1) - 1
		return b[cut2]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		i = 0
		j = 0
		p = 0
		ans = [0] * (m + n)
		while i < n and j < m:
			if arr1[i] <= arr2[j]:
				ans[p] = arr1[i]
				i += 1
			else:
				ans[p] = arr2[j]
				j += 1
			p += 1
		while i < n:
			ans[p] = arr1[i]
			p += 1
			i += 1
		while j < m:
			ans[p] = arr2[j]
			p += 1
			j += 1
		return ans[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		arr1.extend(arr2)
		arr1.sort()
		for i in range(len(arr1)):
			if i == k:
				return arr1[i - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		a = []
		for i in range(n):
			a.append(arr1[i])
		j = 0
		for i in range(n, n + m):
			a.append(arr2[j])
			j += 1
		a.sort()
		return a[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		temp = [-1] * (n + m)
		i = j = a = 0
		while i < n and j < m:
			if arr1[i] < arr2[j]:
				temp[a] = arr1[i]
				i += 1
			else:
				temp[a] = arr2[j]
				j += 1
			a += 1
		while i < n:
			temp[a] = arr1[i]
			i += 1
			a += 1
		while j < m:
			temp[a] = arr2[j]
			j += 1
			a += 1
		return temp[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		for i in arr2:
			arr1 += [i]
		arr1.sort()
		return arr1[k - 1]


class Solution:

	def kthElement(self, arr1, arr2, n, m, k):
		i = 0
		j = 0
		l = []
		while i < n and j < m:
			if arr1[i] >= arr2[j]:
				l.append(arr2[j])
				j += 1
			else:
				l.append(arr1[i])
				i += 1
		while i < n:
			l.append(arr1[i])
			i += 1
		while j < m:
			l.append(arr2[j])
			j += 1
		return l[k - 1]