Find matching consecutive integers in array

Question

Given two arrays containing integers, figure out whether or not three consecutive integers are present in both arrays. For example: A = [1, 4, 5, 7, 2] and B = [3, 1, 4, 5, 9] will result in "true" / 1 because [1, 4, 5] is present in both arrays.

My solution to this task is present below, but I feel like there must be a more optimized solution than this.

int consecutiveInts(int *a, int sizeA, int *b, int sizeB){
    int i, j;

    // Iterate over every integer in array b for every integer in array a.
    for (i = 0 ; i < sizeA - 2 ; i++){
        for (j = 0 ; j < sizeB - 2 ; j++){
            if (a[i] == b[j] && a[i + 1] == b[j + 1] && a[i + 2] == b[j + 2])
                return 1;
        }
    }
    return 0;
}

I would put some test before the loops so that it does not loop uselessly. Checking if A and B size are bigger than 3 for example. — Badda, May 09 '17 at 12:12
You might want to write up your samples in a more-complete fashion and ask for critique over at [codereview.se]. Be sure to read [A guide to Code Review for Stack Overflow users](//codereview.meta.stackexchange.com/a/5778) first, as some things are done differently over there! — Toby Speight, May 09 '17 at 12:15

score 0 · Answer 1 · edited May 23 '17 at 12:34

I think I cannot be wrong by sayin that declaring i and j outside of the loop is useless and not optimized.

Something like :

for (unsigned i = 0; i < sizeA - 2; i++) // i will only exist inside the loop

Would be a little better. I use unsigned type because it is a habit I have taken when using an iterating variable. I think this is a matter which, if you are interested and not already informed, you could learn from by reading this topic.

score 0 · Answer 2 · answered May 09 '17 at 14:04

Not sure it optimizes running speed, but I notice that in case there are repeated numbers you don't need to check them over and over again.

For example three sequential elements in the first array are all 1. After checking a[i] and seeing it's a mismatch you can skip directly to a[i + 3] without comparing a[i + 1] or a[i + 2] (they are also a mismatch).

The management of this condition, particularly if it's a short sequence of repeats, may not improve running time. You have to measure.

chux - Reinstate Monica · Answer 3 · 2017-05-09T17:04:08.710

With code changes that do not affect the order of complexity, any candidate improvements need profiling (tests that measure the performance) to verify.

The following is still a O(n*m), yet with reduced coefficient as it can step through b[] faster if a[] has repeated values that also exist in b[]. This speeds the inner b[] loop where the majority of time is consumed.

Look at the a[] pattern for distinct values to so j may be advanced faster.
Example:

#define x 0
bool Pattern3(const int *a, size_t size_a, const int *b, size_t size_b) {
  static const unsigned char deltas[2][2][2][2] = { //
      //                 What type of pattern is a[0], a[1], a[2]?
      { { { 1, 1 },   // X Y Z
      { 1, 1 } },     // X Y Y
      { { 1, 2 },     // X Y X
      { x, x } } },   // not possible
      { { { 2, 1 },   // X X Y
      { x, x } },     // not possible
      { { x, x },     // not possible
      { 2, 3 } } } }; // X X X
  for (unsigned i = 0; i + 2 < size_a; i++) {
    const unsigned char *delta23 = deltas[a[0] == a[1]][a[0] == a[2]][a[1] == a[2]];
    for (unsigned j = 0; j + 2 < size_b;) {
      if (a[0] != b[j]) {
        j++;
      } else if (a[0 + 1] != b[j + 1]) {
        j += delta23[0];
      } else if (a[0 + 2] != b[j + 2]) {
        j += delta23[1];
      } else {
        return true;
      }
    }
    a++;
  }
  return false;
}

Other minor changes which may help.

In the above, swap a,b when size_a > size_b.

Use const as lesser compilers can optimized on that.

// int consecutiveInts(int *a, int sizeA, int *b, int sizeB){
int consecutiveInts(const int *a, int sizeA, const int *b, int sizeB){

Iterate from 2. Adjust indexing accordingly.

for (i = 2 ; i < sizeA ; i++){
  ...

chux - Reinstate Monica · Accepted Answer · 2017-05-09T19:32:06.330

For small arrays, OP approach is OK. For array lengths m,n it has O(m*n) run time.

An alternate makes 2 value arrays, sorts them and then looks for a common element. It has O(m*log2(m) + n*log2(n)) run time. Certainly faster with large arrays than OP's code.

typedef struct {
  int i[3];
} int3;

void Init3(int3 *i3, const int *i, size_t n) {
  while (n--) {
    i3[n].i[0] = i[n];
    i3[n].i[1] = i[n + 1];
    i3[n].i[2] = i[n + 2];
  }
}

int fcmp(const void *a, const void *b) {
  return memcmp(a, b, sizeof (int3));
}

bool Pattern3(const int *a, size_t size_a, const int *b, size_t size_b) {
  if (size_a < 3 || size_b < 3) return false;

  int3 a3[size_a - 2];
  Init3(a3, a, size_a - 2);
  qsort(a3, size_a - 2, sizeof *a3, fcmp);

  int3 b3[size_b - 2];
  Init3(b3, b, size_b - 2);
  qsort(b3, size_b - 2, sizeof *b3, fcmp);

  while (size_a && size_b) {
    int cmp = fcmp(&a[size_a - 1], &b[size_b - 1]);
    if (cmp == 0) return true;
    if (cmp > 0) size_a--;
    else size_b--;
  }
  return false;
}

int main() {
  int A[] = { 1, 4, 5, 7, 2 };
  int B[] = { 3, 1, 4, 5, 9 };
  printf("%d\n", Pattern3(A, sizeof A / sizeof *A, B, sizeof B / sizeof *B));
}

An alternative would use a bsearch() rather than form the 2nd int3 b3[]/qsort().

score -1 · Answer 5 · edited May 09 '17 at 18:01

-1

try using the following loop

for(int i=0;i<A.length;i++)
{
    for(int j=0;j<A.length;j++)
    {
        if(A[i]==B[j])
        {
            count=count+1; //It checks how many times equal elements have been found
                           //ensure to declare and initialize int count=0;
        }
    }
}
if(count>=3)
    System.out.println("true");

edited May 09 '17 at 18:01

m7913d

10,244
7
28
56

answered May 09 '17 at 14:01

Noman N. Minhas

33
6

I suggest that you indent your code to make it easier to read. – nounoursnoir May 09 '17 at 17:52

Find matching consecutive integers in array

5 Answers5