jeudi 14 mai 2020

How to find triplets { x , y , z } from three sorted A, B, C such that x < y < z in O(n)?

Suppose I have three sorted arrays

A : { 4, 9 }

B : { 2, 11}

C : { 12, 14}

Then the no of triplets { x, y, z } such that x belongs to A, y belongs to B and z belongs to C such that x < y < z is -> 4

I know O( n ^3 ) algo but how to do it in O(n). Where n is the length of the array.

Aucun commentaire:

Enregistrer un commentaire