What is the efficient way to find an array inside an array?

Question

Find an Array of Values Inside an Array

Lets say I have an array [1,2,3,8,2,3,4,5,6,7,8] and I want to find the first occurrence of the values [3,4,5,6] together, how might I do that? I can use Array.prototype.findIndex, but when I am looking for a large amount of values in a large array, it doesn't feel like the proper way to do it.

What fails:

let largeArray = [1,2,3,8,2,3,4,5,6,7,8];
let smallArray = [3,4,5,6];

//Problem: an array isn't a function
largeArray.findIndex(smallArray);

/*
Problem: always returns -1 because it checks each element
rather than looking for a group of elements.
*/
largeArray.indexOf(smallArray);

//Problem: same as using indexOf
largeArray.findIndex(item=>smallArray);

What works:

let largeArray = [1,2,3,8,2,3,4,5,6,7,8];
let smallArray = [3,4,5,6];

//Here is what works, but isn't ideal
largeArray.findIndex((item, index, arr) => {
    let isTheOne = item == smallArray[0] &&
        arr[index + 1] == smallArray[1] &&
        arr[index + 2] == smallArray[2] &&
        arr[index + 3] == smallArray[3];
    return isTheOne;
});
//It returns 5, which is correct.

To Be Continued

I am currently using what works, but what if largeArray had the length of a million and smallArray had the length of 300. That would be 1 line of item == smallArray[0] &&, 298 lines of arr[index + x] == smallArray[x] &&, and 1 line of arr[index + x] == smallArray[x];. I don't want to use Array.prototype.map, Array.prototype.filter, Array.prototype.forEach, a for loop, or a while loop. This is because Array.prototype.map, Array.prototype.forEach, and the loops take a very long time to complete. I don't want to use Array.prototype.filter because that doesn't give me the index.

You want to use every() inside your findINdex

epascarello
– epascarello

2021-02-25 17:24:41 +00:00
Commented Feb 25, 2021 at 17:24 — epascarello
– epascarello, Commented Feb 25, 2021 at 17:24

epascarello · Accepted Answer · 2021-02-25 17:38:41Z

You were on the right track, you just want to use every() to look over the small index to check that each index matches

const largeArray = [1, 2, 3, 8, 2, 3, 4, 5, 6, 7, 8];
let smallArray = [3, 4, 5, 6];

const index = largeArray.findIndex(
  (item, index, arr) =>
    smallArray.every(
      (n, sIndex) => n === arr[index + sIndex]
    )
);

console.log(index);

You could add a check beforehand to not have to go in every... not sure what that would improve.

const index = largeArray.findIndex(
  (item, index, arr) =>
    item === smallArray[0] && 
    smallArray.every(
      (n, sIndex) => n === arr[index + sIndex]
    )
);

Other approach is using strings

const largeArray = [1, 2, 3, 8, 2, 3, 4, 5, 6, 7, 8];
const smallArray = [3, 4, 5, 6];

const largeStr =  largeArray.join(",");
const smallStr =  smallArray.join(",");
const strIndex = largeStr.indexOf(smallStr);
const index = strIndex > -1 ? largeStr.substr(0,strIndex-1).split(",").length : -1;
console.log(index)

To figure out what is better is really based on your use case.

Majed Badawi · Accepted Answer · 2021-02-25 17:51:25Z

1

You can use .join to convert the arrays to strings, and use .indexOf to get the index given that you will remove the additional commas:

const getIndexOfSubArray = (arr=[], sub=[]) => {
  const str = arr.join();
  const subStr = sub.join();
  const index = str.indexOf(subStr);
  return index < 0 ? -1 : str.substr(0, index-1).split(',').length;
}

console.log( getIndexOfSubArray([1,2,3,8,2,3,4,5,6,7,8], [3,4,5,6]) );

edited Feb 25, 2021 at 17:51

answered Feb 25, 2021 at 17:31

Majed Badawi

28.5k4 gold badges30 silver badges56 bronze badges

Comments

Nina Scholz · Accepted Answer · 2021-02-25 17:57:13Z

1

You could iterate by hand and check the items with indexOf.

function getIndex(array, subarray) {
    let p = -1,
        first = subarray[0];

    while ((p = array.indexOf(first, p + 1)) !== -1) {
        let i = p,
            complete = true;

        for (const s of subarray) {
            if (s !== array[i++]) {
                complete = false;
                break;
            }
        }
        if (complete) return p;
    }
    return -1;
}

console.log(getIndex([1, 2, 3, 8, 2, 3, 4, 5, 6, 7, 8], [3, 4, 5, 6])); // 5

answered Feb 25, 2021 at 17:57

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Comments

Djaouad · Accepted Answer · 2021-02-25 18:13:50Z

1

Here is a simple approach to this problem:

let largeArray = [1, 2, 3, 8, 2, 3, 4, 5, 6, 7, 8];
let smallArray = [3, 4, 5, 6];

let s = 0,
  i = 0,
  j = 0;

let SLen = smallArray.length,
    LLen = largeArray.length;

while (i < LLen && j < SLen && SLen - j <= LLen - i) {
  if (j == 0) {
    s = i;
  }
  if (largeArray[i] == smallArray[j]) {
    j++;
  } else {
    j = 0;
    i = s;
  }
  i++;
}

let index = i - j;

if (j == SLen) {
  console.log(`found at index ${index}`);
} else {
  console.log('not found');
}

edited Feb 25, 2021 at 18:13

answered Feb 25, 2021 at 17:33

Djaouad

22.8k4 gold badges37 silver badges57 bronze badges

2 Comments

quicVO Over a year ago

Ah, using break would solve the problem of looping through every item in the array.

Nick Over a year ago

Above code has a bug. To understand it look at this input instances: let largeArray = [1, 2, 3, 8, 2, 3, 4,3,4, 5, 6, 7, 8]; let smallArray = [3, 4, 5, 6]; When you slide the window you have to store the first position and in the missing case you have to resume the search from that point

Collectives™ on Stack Overflow

What is the efficient way to find an array inside an array?

Find an Array of Values Inside an Array

What fails:

What works:

To Be Continued

4 Answers 4

Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Find an Array of Values Inside an Array

What fails:

What works:

To Be Continued

4 Answers 4

Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related