Return to Answer

@Tushar has posted a slightly more performant version. However, if I'm not mistaken, the asymptotic time complexity of his improved version is the same as – or very similar to – the complexity of your original version.

@Tushar has posted a more performant version. However, if I'm not mistaken, the asymptotic time complexity of his improved version is the same as – or very similar to – the complexity of your original version.

• there is some code duplicity and it surely could be written more nicely,
• I have not tested it very thoroughly – only on the samples you provided in your question,
• I have not measured performance, so it's still possible that this version is actually slower than either of the other versions.

• there is some code duplicity and it surely could be written more nicely,
• I have not tested it very thoroughly – only on the samples you provided in your question,
• EDIT: performance benchmark.

But first, a few remarks about the current code (some of these were already covered by @Tushar while I was writing this answer):

• there is some code duplicity and it surely could be written more nicely,
• I have not tested it very thoroughly – only on the samples you provided in your question,
• I have not measured performance, to it's still possible that this version is actually slower than either of the other versions.

But first, a few remarks about the code (some of these were already covered by @Tushar while I was writing this answer):

• there is some code duplicity and it surely could be written more nicely,
• I have not tested it very thoroughly – only on the samples you provided in your question,
• I have not measured performance, so it's still possible that this version is actually slower than either of the other versions.