Finding the maximum number from two arrays preserving relative order

Problem

You are given two arrays of length M and N having elements in the range 0-9.
Your task is to create the maximum number of length K from elements of these two arrays such that the relative order of elements is the same in the final number as in the array, they are taken from

i.e. If two elements a, and b are taken from array1 and a comes before b in array1 so in the final number a should come before b (Relative order kept same).

 Example: N=4 and M =6
 Array1 = { 3 , 4, 6,5}
Array2 ={9,1,2,5,8,3}

Suppose K = 5, then the number will be {9,8,6,5,3}
You can see {9,8,3} are taken from Array2 in the same order as they are in Array2.
Similarly {6,5} are taken from Array1 in the same order and number 98653 is the maximum possible number.


[UPDATE 02-24-23]: Solved again. Got stuck with a possible exploration of using dynamic programming initially. The second solution was using the MaxHeap instead of the sorted list. It was awfully inefficient since I had to put each already seen item back into the heap, which takes $O(log (N+M)$.

A better way by far is to use a greedy algorithm with tracking of the positions from which elements from the list M, N were taken to ensure the relative order is preserved. Even then, it took 1 hr to fix the bug.

This is one of the Google interview questions. To be honest, it took me 3 days (although the actual time spent was around 7 hours), to find the solution.

I assigned "Difficult" to this problem even though some people find this problem easier than other one.

My initial algorithm was based on the DFS with backtracking, which takes $O(K (N+M)!)$.
My second attempt took longer than the initial attempt since I forgot how I solved it before and wanted to find after than polynomial time, which I failed.

Given, Array1 with the size of N and Array 2 with the size of M, the new algorithm took the idea of merging the two arrays and sorting the merged array. It iterated over the merged array K times to find the maximum value with the size of K.

Here is brought algorithm:

- In the list O, sort all numbers in descending order with their position and the name of the array to they belong.

for k = 0; k  <K; k++:

 iterate the numbers from O

  for number, C from O:

  - take the largest unused numbers

  - check if the position of the number is later than lastly taken number's position in the array M or N.

  - check if the remaining numbers in M, N are still larger or equal to the remaining numbers to choose (K - (k +1)) 

     - if so, add number C to the result set, R, and exit the for inner for loop.

 return the result set R.

The algorithm itself is quite simple but the process of coming up with the algorithm was quite painful.
Running time of this algorithm is $$O( K * (M+N))$$
Code from 02-24-23:

	'''
	You are given two arrays of length M and N having elements in range 0-9.
	Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from
	i.e. If two elements a,b are taken from array1 and a comes before b in array1 so in the final number a should come before b (Relative order kept same) .
	Example: N=4 and M =6
	Array1 = { 3 , 4 , 6,5}
	Array2 ={9,1,2,5,8,3}
	Suppose K = 5, then number will be {9,8,6,5,3}
	You can see {9,8,3} are taken from Array2 in the same order as they are in Array2.
	Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.
	'''
	class Node:
	def __init__(self, value, array_number, pos):
	self.value = value
	self.array_number = array_number
	self.pos = pos
	self.used = False
	def __str__(self):
	return "[{}, {}, {}, {}]".format(self.value, self.array_number, self.pos, self.used)
	def choose_max_sequence(target_length, array1, array2):
	result = []
	ordered_numbers = []
	last_pos = [0, 0]
	for i in range(len(array1)):
	ordered_numbers.append(Node(array1[i], 0, i))
	for j in range(len(array2)):
	ordered_numbers.append(Node(array2[j], 1, j))
	# O(log(N+M))
	ordered_numbers.sort(key=lambda e: e.value, reverse=True)
	for k in range(target_length):
	for p in range(len(ordered_numbers)):
	next = ordered_numbers[p]
	if next.used == True or last_pos[next.array_number] > next.pos:
	continue
	m_left = len(array1) - last_pos[0] if next.array_number == 1 else len(array1) - (next.pos + 1)
	n_left = len(array2) - last_pos[1] if next.array_number == 0 else len(array2) - (next.pos + 1)
	if (m_left + n_left) >= (target_length -(k + 1)):
	result.append("{}".format(next.value))
	next.used = True
	last_pos[next.array_number] = next.pos + 1
	break
	return "".join(result)
	# Example: N=4 and M =6
	# Array1 = { 3 , 4 , 6,5}
	# Array2 ={9,1,2,5,8,3}
	N = [3, 4, 6, 5]
	M = [9,1,2,5,8,3]
	K = 5
	result = choose_max_sequence(K, N, M)
	print(result)
	assert result == "98653"
	K = 6
	result = choose_max_sequence(K, N, M)
	print(result)
	assert result == "984653"
	K = 7
	result = choose_max_sequence(K, N, M)
	print(result)
	assert result == "9834653"

view raw google_maximum_number_sequence.py hosted with ❤ by GitHub

UPDATE(2019-07-20): solved the problem again but could not come up with a correct solution.

I was stuck with the idea of using dynamic programming not able able to figure up what to do with two arrays, M, N, and the position of lastly taken number from them.

I also found that the original code had some inefficient code around the while loop. Fix that problem in a python solution.

Rewrite the code with the algorithm above in python.

	'''
	23:10: to write up the code. (with bug)
	14:58: to debug the code. (there was bug in the code.)
	Total: 38.09 --> still took too long with typos after knowing the algorithm. Need more practice !! You can do it.
	'''
	class Node:
	def __init__(self, value, position, source):
	self.value = value
	self.pos = position
	self.source = source
	def compare(left, right):
	#condition to put left first.
	if left.value > right.value:
	return -1
	return 1
	class FindMaxNumber:
	def find(self, M, N, K):
	#get all the methods and sort by value
	merged = []
	#0 for M
	for i, m in enumerate(M):
	merged.append(Node(m, i, 0))
	# 1 for N
	for j, n in enumerate(N):
	merged.append(Node(n, j, 1))
	sorted_list = sorted(merged, cmp=compare)
	result = []
	last_n = -1
	last_m = -1
	left_n = None
	left_m = None
	for node in sorted_list:
	#current node belongs to M and later than lastly seen number.
	if node.source == 0 and last_m < node.pos:
	left_m = (len(M) -1) - node.pos
	left_n = (len(N) - 1) - last_n if last_n >=0 else len(N)
	elif node.source == 1 and last_n < node.pos:
	left_n = (len(N) - 1) - node.pos
	left_m = (len(M) - 1) - last_m if last_m >= 0 else len(M)
	else:
	continue
	#check there will be enough numbers left after taking the current node.
	if (left_n + left_m) >= K - len(result) - 1:
	result.append(node.value)
	if node.source == 0:
	last_m = node.pos
	else:
	last_n = node.pos
	if len(result) == K:
	break
	return result
	f = FindMaxNumber()
	M = [3 , 4 , 6,5]
	N = [9,1,2,5,8,3]
	K = 5
	print("M = {}, N = {}, K = {}, result = {}".format(M, N, K, f.find(M, N, K)))

view raw find_max_number_with_relative_order_from_two_arrays.py hosted with ❤ by GitHub

Practice statistics:

23:10: write up the code. (with a bug)
14:58: debug the code. (there was a bug in the code.)

Total: 38.09

The original solution from 2016

	#include<vector>
	#include<algorithm>
	#include<iostream>
	#include<string>
	using namespace std;
	struct node {
	int source;
	bool used;
	int value;
	int pos;
	node(int v, int p, int s): used(false), value(v), pos(p), source(s){}
	};
	bool compare(node * prev, node * next)
	{
	return prev->value > next->value;
	}
	string find_max(int *m, int *n, int M, int N, int K)
	{
	vector<node*> ordered;
	string result;
	int i;
	if (M+N < K)
	return "Invaild Input";
	int k_left = K;
	int last_n = INT_MIN, last_m = INT_MIN;
	for(i = 0; i < M; i++)
	ordered.push_back(new node(m[i], i, 1));
	for(i = 0; i < N; i++)
	ordered.push_back(new node(n[i], i, 2));
	sort(ordered.begin(), ordered.end(), compare);
	while(result.length() < K)
	{
	for (i = 0; i < ordered.size(); i++)
	{
	nt m_left, n_left;
	bool Is_m = false;
	if (ordered[i]->used)
	continue;
	if (ordered[i]->source == 1 && ordered[i]->pos > last_m)
	{
	m_left = M - ordered[i]->pos;
	n_left = (last_n == INT_MIN)? N: N - last_n -1;
	Is_m = true;
	} else if (ordered[i]->source == 2 && ordered[i]->pos > last_n)
	{
	m_left = (last_m == INT_MIN)? M: M - last_m -1;
	n_left = N - ordered[i]->pos;
	} else {
	continue;
	}
	if (m_left + n_left >= K-result.length())
	{
	result.push_back(ordered[i]->value + '0');
	if (Is_m)
	last_m = ordered[i]->pos;
	else
	last_n = ordered[i]->pos;
	break;
	}
	}
	}
	return result;
	}
	int main()
	{
	int N[4] = { 3 , 4 , 6,5};
	int M[6] = {9,1,2,5,8,3};
	int K = 5;
	cout<<" max number = " << find_max(M, N, 6, 4, K)<<endl;
	int N2[4] = { 3, 4, 6, 5};
	int M2[6] = {2,1,5,3,8,9};
	cout<<" max number = " << find_max(M2, N2, 6, 4, 6)<<endl;
	return 1;
	}

view raw Finding max number with relative ordering hosted with ❤ by GitHub

Practice statistics

3 days: to finally come up with the algorithm running in $O( K(M+N) )$