# Python solution, 172ms, beats 100%

• ``````import math

class RMQ(object):
def __init__(self, nums):
self.nums = nums
n = len(nums)
if n:
d = int(math.log(n, 2)) + 1;
self.table = [[-1 for _ in range(n)] for _ in range(d)]
for j in range(n):
self.table[0][j] = j;
for i in range(1, d):
for j in range(n - (1 << i) + 1):
i1 = self.table[i-1][j]
i2 = self.table[i-1][j+(1<<(i-1))]
if nums[i1] >= nums[i2]:
self.table[i][j] = i1
else:
self.table[i][j] = i2

def get(self, left, right):
if right < left:
return -1
l = right - left + 1
d = int(math.log(l, 2))
i1 = self.table[d][left]
i2 = self.table[d][right+1-(1<<d)]
if self.nums[i1] >= self.nums[i2]:
return i1
return i2

class Solution(object):
def maxNumber(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""

n, m = len(nums1), len(nums2)
rmq1, rmq2 = RMQ(nums1), RMQ(nums2)

start_positions = {0: 0}

res = []
while k:
max_digit = 0
new_start_positions = {}
for s1, s2 in start_positions.items():
e1 = n - max(1, k - (m - s2))
e2 = m - max(1, k - (n - s1))

if s1 < n and s2 < m:
i1 = rmq1.get(s1, e1)
i2 = rmq2.get(s2, e2)
if nums1[i1] > nums2[i2]:
if nums1[i1] >= max_digit:
if nums1[i1] > max_digit:
max_digit = nums1[i1]
new_start_positions = {}
new_start_positions[i1 + 1] = s2
elif nums1[i1] < nums2[i2]:
if nums2[i2] >= max_digit:
if nums2[i2] > max_digit:
max_digit = nums2[i2]
new_start_positions = {}
new_start_positions[s1] = i2 + 1
else:
if nums1[i1] >= max_digit:
if nums1[i1] > max_digit:
max_digit = nums1[i1]
new_start_positions = {}
new_start_positions[i1 + 1] = s2
new_start_positions[s1] = i2 + 1
elif s1 < n:
i = rmq1.get(s1, e1)
if nums1[i] >= max_digit:
if nums1[i] > max_digit:
max_digit = nums1[i]
new_start_positions = {}
new_start_positions[i + 1] = s2
else:
i = rmq2.get(s2, e2)
if nums2[i] >= max_digit:
if nums2[i] > max_digit:
max_digit = nums2[i]
new_start_positions = {}
new_start_positions[s1] = i + 1
res.append(max_digit)
start_positions = new_start_positions
k -= 1
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.