Search code examples
algorithmbinary-tree

Find all possible pairs (combinations) starting from the middle like in a binary search

Given ['RENE','ADRIANA','ANDRES'], I should find all possible pairs.

The test gives me the correct output as ['ADRIANA-RENE', 'ADRIANA-ANDRES', 'RENE-ANDRES'].

I already wrote a code using backtrack recursion, but most of the examples I've seen start from the beginning of the array (as obvious), and so does my solution. ['RENE-ADRIANA','RENE-ANDRES','ADRIANA-ANDRES']

I know they are the same, however, I am afraid my solution would not pass automated tests because it is not exact.

I believe they are using some sort of "binary search" starting from the middle and then continuing left before going right, although, I've been unable to write this code myself. I am not aware if there is an algorithm to find the possible combinations from a given array starting from the middle.

Solution

  • It looks like the main trick here is iterating over all pairs of indices your array, in some sort of alternating way. I've reformulated your problem to something more generic/simpler to outline. Basically, given a length N array, generate all pairs of indices where the first index should start from the middle and the next indices should alternate from the left, then right to it. I'll assume that the next first index should be chosen in an alternating way, from left to right.

    Here are a few cases

    N = 3 (your example)
[
  (1, 0)
  (1, 2)
  (0, 2)
]

N = 4
[
  (2, 1)
  (2, 3)
  (2, 0)
  (1, 0)
  (1, 3)
  (3, 0)
]

N = 5
[
  (2, 1)
  (2, 3)
  (2, 0)
  (1, 0)
  (1, 3)
  (1, 4)
  (3, 0)
  (3, 4)
  (0, 4)
]

    We can model this iteration iteratively via breadth first search:

    1. Initialize a queue Q, a middle value mid equal to N/2. Let left, right be equal to mid-1 and mid+1 respectively.

    2. Insert mid into Q

    3. Pop Q and assign it to mid

    4. Generate alternating pairs starting from mid, using left and right as the immediate left/right starting points

    5. If you're on an odd cycle of 3., insert left into Q and decrement it by 1. Otherwise insert right into Q and increment it by 1. Don't perform insertion if the value to be inserted is out of bounds.

    6. Loop back to 3, until Q is empty.

    This should give the desired traversal and does indeed cover all pairs of indices exactly once (my implementation worked until N = 1000; after that it started taking quite a bit of time).

    To apply this to your problem, just take each index pair and combine the strings at those indices.