In this post, we will see how to resolve Find all possible pairs (combinations) starting from the middle like in a binary search
['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.
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.
Best Answer: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
Narray, 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
Initialize a queue
Q, a middle value
rightbe equal to
Qand assign it to
Generate alternating pairs starting from
rightas the immediate left/right starting points
If you’re on an odd cycle of 3., insert
Qand decrement it by 1. Otherwise insert
Qand increment it by 1. Don’t perform insertion if the value to be inserted is out of bounds.
Loop back to 3, until
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.
If you have better answer, please add a comment about this, thank you!