CODEWITHSUNDEEP
algorithmoptimizationsetsubset
WillEnsaba
WillEnsaba

Reputation: 777

Define overlap elements or elements not contained in subsets

I would like to check which strategy would be the most efficient to compute the problem described below

I have one set Q and two subsets L and R. I have three cases.

1) L ∩ R != 0. In this case, I want to get the array of overlapped elements. In the example below, the resultant set would be R = {4, 5}.

  Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  L = {0, 1, 2, 3, 4, 5, *, *, *, *}
  R = {*, *, *, *, 4, 5, 6, 7, 8, 9}

2) L ∩ R = 0. In this case, I want to get Q \ (L ∪ R). In the example below, the resultant set would be R = {4, 5, 6}.

  Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  L = {0, 1, 2, 3, *, *, *, *, *, *}
  R = {*, *, *, *, *, *, *, 7, 8, 9}

3) Q \ (L ∪ R) = 0. In this case, I want to get the index where they find each other. In the example below, the index would be 4.

  Q = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  L = {0, 1, 2, 3, 4, *, *, *, *, *}
  R = {*, *, *, *, *, 5, 6, 7, 8, 9}

Upvotes: 1

Views: 44

Answers (1)

gsamaras
gsamaras

Reputation: 73424

If L ∩ R != 0, then I would:

Choose the two smallest arrays, and compare them to find the common elements.

This will save you a loop, and it will result in O(n2), instead of the naive O(n3).

In the other case, I don't see how you would avoid visiting every element of every array.

Note: If you would use a data structure, sush a hash map, then both cases would be soled in linear time.

Upvotes: 1

Related Questions