1
$\begingroup$

Question: Given two sorted arrays A1 and A2, check if A2 is a subset of A1. Also, assume there might be duplicates.
Example:
A1 = [0,0,0,0,1], A2 = [0,1] // should return true
A1 = [-1,0,1,2,3,4,5], A2 = [1,2,3] // should return true

Answer: My answer is below and works, but I believe my running time is slow. Not sure if there is another algorithm I can leverage.

FYI: this is not for school or project, just curious with solving problems.

function isSubArrayOfAnother(a1, a2) {
        if (!a1 || !a2 || a1.length === 0 || a2.length === 0) { 
            return false;
        }

    let loc = a1.indexOf(a2[0]);
    let allIndexes = [];

    while(loc > -1) {
        allIndexes.push(loc);
        loc = a1.indexOf(a2[0], loc + 1);
    }

    for(var i=0; i<allIndexes.length; i++) {
        let isMatch = true;
        let tempIndex = allIndexes[i];
        for (var j = 0; j< a2.length; j++) {
            if (a2[j] !== a1[tempIndex++]) {
                isMatch = false;
                break;
            }
        }
        if (isMatch)
            return isMatch
    }
    return false;

}
$\endgroup$
2
  • $\begingroup$ You should be able to solve this in linear time. $\endgroup$ – Yuval Filmus Aug 30 '18 at 4:58
  • $\begingroup$ it's a variation of sorted array merge algo $\endgroup$ – Bulat Aug 30 '18 at 10:54
1
$\begingroup$

There is a O(n) solution to this.

Finding all possible start index of the subset can be eliminated

while(loc > -1) {
    allIndexes.push(loc);
    loc = a1.indexOf(a2[0], loc + 1);
}

And, there seems to be an edge case where it will attempt to access element out of the array's bounds. I mean, the input like the one below

A1 = [-1, 0, 1, 3, 1, 2], A2 = [1, 2, 3]

The below pseudocode-like is a starting point, there is still optimisations left in this algorithm.

Given array A, find the presence of sub array B,

matchPointer = 1
for i = 1 to A.length
  if A[i] == B[matchPointer]
    if matchPointer == B.length
      "Subset Found"
    matchPointer = matchPointer + 1
  else
    matchPointer = 1;
$\endgroup$
0
$\begingroup$

The algorithm given by @bnu is optimal in time in the general case when you know nothing about the input.

However if you know that one of the arrays is much smaller than the other, you can do a binary search for each value of the small array to check if it is present in the larger array.
In this way (if k is size of smaller and n of bigger array) , the time complexity is$ O(k * \log n)$ which can be orders of magnitude faster if $k<<n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.