1
$\begingroup$

I have two lists l1 and l2 of possibly unequal sizes (say, m and n). I wrote an algorithm to find out all ways l1 and l2 can be merged while preserving their order.

l1 = ["NYC", "LA"]
l2 = ["A", "B"]

output:
[['NYC', 'LA', 'A', 'B'],
 ['NYC', 'A', 'LA', 'B'],
 ['NYC', 'A', 'B', 'LA'],
 ['A', 'NYC', 'LA', 'B'],
 ['A', 'NYC', 'B', 'LA'],
 ['A', 'B', 'NYC', 'LA']]

NYC always comes before LA. A always comes before B.

Basic idea of algorithm: Append one item from l1 to temp, recurse on remaining part of the lists. Do the same for l2.

Code (python3):

def merge(l1, l2):    
    temp = [] # temporary buffer 
    res = [] # final result
    mergeHelper(l1, 0, l2, 0, temp, res)
    return res

def mergeHelper(l1, start1, l2, start2, temp, res):
    if start1 >= len(l1) and start2 >= len(l2):
        res.append(temp.copy())
        return

    if start1 < len(l1):
        temp.append(l1[start1])
        mergeHelper(l1, start1+1, l2, start2, temp, res)
        temp.pop()

    if start2 < len(l2):
        temp.append(l2[start2])
        mergeHelper(l1, start1, l2, start2+1, temp, res)
        temp.pop()

Question: What's the time/space complexity? I suspect it might be $O(2^{n+m})$ as we have two choices for every iteration.

I figured out the recurrence relation is: T(m,n) = 1 + T(n-1, m) + 1 + T(n, m-1) but unable to reduce it further.

$\endgroup$
4
  • $\begingroup$ What are the complexities of append and pop ? $\endgroup$ Mar 3 at 8:46
  • $\begingroup$ Notice how this is equivalent to the counting the number of north-east lattice paths from $(0,0)$ to $(m,n)$. Or $(n,m)$ $\endgroup$
    – droptop
    Mar 3 at 10:01
  • $\begingroup$ @YvesDaoust append and pop are both O(1) $\endgroup$
    – sam
    Mar 4 at 0:33
  • $\begingroup$ pop can be O(n). And what about the cost of implied memory allocation/deallocations ? $\endgroup$ Mar 4 at 8:37

1 Answer 1

0
$\begingroup$

The number of ways to combine an ordered list of size $n$ and an ordered list of size $m$ into one ordered list of size $n+m$ in a way which keeps the order of both lists is given by the binomial coefficient $$\binom{n+m}{n}$$ The time complexity of your procedure depends on various implementation details.

$\endgroup$
2
  • $\begingroup$ Could you please give a little bit more details on how you arrived at this? $\endgroup$
    – sam
    Mar 4 at 0:32
  • $\begingroup$ It’s basic combinatorics. Once you chose the positions of the elements of the first list inside the combined list, everything else is determined (including which element of each list goes to with position). $\endgroup$ Mar 4 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.