-1

Say I have the following sorted array:

int[] numbers = {0, 0, 1, 2, 2, 2}.

How can I check if any sub-array of length 3 of numbers exists in the following 2-dimensional array:

int[][] sets = { {0, 0, 0}, {1, 1, 1}, {2, 2, 2} }

In this simple example, the last 3 elements of numbers are clearly contained as an array in sets, but in my actual program, sets will have far more 3 digit permutations of more numbers, but they will all remain length 3, and numbers will always be sorted.

KOB
  • 4,084
  • 9
  • 44
  • 88
  • What's the max number allowed in the three-item sets? – Sergey Kalinichenko Apr 26 '16 at 11:10
  • I'm not entirely sure yet. It won't be high at all, probably < 10. Just take it that only numbers 0-3 inclusive are allowed for now – KOB Apr 26 '16 at 11:16
  • `Arrays.asList(outer).containsAll(Arrays.asList(inner))` http://stackoverflow.com/questions/16524709/finding-if-an-array-contains-all-elements-in-another-array – tak3shi Apr 26 '16 at 11:50
  • @tak3shi I tried using this solution, but I came across a problem when duplicate numbers appear in the inner array. In other words, take my example above. `sets[0][0] = {0, 0, 0}`. For `Arrays.asList(numbers).containsAll(Arrays.asList(inner))` to be evaluated to true, `numbers` only needs to contain one 0, whereas my algorithm would need it to contain three different 0s. – KOB Apr 26 '16 at 17:51

1 Answers1

0

If only the numbers less than ten are allowed, you have up to 1000 possible sequences of three numbers. Encode them as 100*ai+10*ai+1+ai+2, and store the index of the first such sequence in a 1001-element array.

In your case numbers would be translated into

0, 0, 1, 2, 2, 2

  1 - 0
 12 - 1
122 - 2
222 - 3

The first column is the index into 1001-element array; the second column is the value that gets placed at that index. The remaining positions of the 1001-element array are set to -1.

To see if numbers contain a three-element sequence construct 100*s0+10*s1+s2 number from them, and look it up in the 1001-element array. If you get -1, the sequence is not there; otherwise, you would get the starting index of the desired subsequence.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523