Check if three arrays contains the same element

Question

Do 3 arrays contain a common element, if they contain output it. For example: [1,2,3], [2,3], [2,4] -> answer = 2

let arr1 = [1, 3, 11, 32, 44, 99];
let arr2 = [4, 12, 15, 99];
let arr3 = [4, 11, 13, 15, 23, 43];

function searchThreeSameNum(arr1, arr2, arr3) {
    let i = 0;
    let j = 0;

    while (1) {
        if (i == arr1.length || j == arr2.length) {
            return 'No equal numbers';
        }

        if (arr1[i] < arr2[j]) {
            i++;
            continue;
        } else if (arr1[i] > arr2[j]) {
            j++;
            continue;
        } else if (arr1[i] == arr2[j]) 
            for (let k = 0; k < arr3.length; k++) {
                if (arr1[i] == arr3[k]) 
                    return arr1[i];
            }   

        return 'No equal numbers';
    }
}

I will be glad if you give me any tips to improve my code. Thanks in advance. Sorry, I'm not an English speaker.

Answer 1

Your code assumes that each of the 3 arrays is sorted. Otherwise the < operator would not work. It's ok to assume this. You should have mentioned this in your question.

You use the == operator for comparing the numbers and the lengths. You should better use the === since the == operator considers 0 and "0" equal, which is not good in most cases.

It does not matter which of the 3 arrays comes first. The result will always be the same. Therefore it would be nice if the code looked the same for each of the 3 arrays. Your current code looks different for arr3.

I would write the code differently:

function smallestCommonElement(a, b, c) {
    let i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length && k < c.length) {
        const max = Math.max(a[i], b[j], c[k]);

        let same = true;
        while (i < a.length && a[i] < max) i++, same = false;
        while (j < b.length && b[j] < max) j++, same = false;
        while (k < c.length && c[k] < max) k++, same = false;

        if (same)
            return a[i];
    }
    return null;
}

The idea is to start at the beginning of the arrays. In each step, look at the current values and find the maximum number. Advance each array to this maximum number. If none of the 3 arrays has been advanced, this means that the current values from all the arrays must be the same. In that case, return this value. Otherwise the values must be different, so try again. Do all this until one of the arrays is at the end, in which case there is no common element.

---

Looking again at your code, there is a bug. Given the arrays [2, 3], [2, 3], [3], your code will return 'No equal number' even though the 3 appears in each array. Using a debugger (or pen and paper), you should step through your code to see where the bug is.

It's an edge case, and it happens in the part of the code that differs from the other parts. That's why I suggested that the code for all 3 arrays should look the same. It's one less chance of introducing bugs.

Answer 2

Although your code seems to work, it is difficult to read. Loops inside loops and many if, else if blocks and continue or return. Let's start with some big issues:

You use an endless while loop when it is clear you don't have to. The code below would perform the same function:

function searchThreeSameNum(arr1, arr2, arr3) {
    let i = 0, j = 0;
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            i++;
            continue;
        } else if (arr1[i] > arr2[j]) {
            j++;
            continue;
        } else if (arr1[i] == arr2[j]) {
            for (let k = 0; k < arr3.length; k++) {
                if (arr1[i] == arr3[k]) return arr1[i];
            }   
        } 
    }
    return 'No equal numbers';
}

This has one less return 'No equal numbers'; (code repetition) and only one return from within the while loop.

Now let's look at what the loop is actually doing. It runs through array 1 and 2 and tries to find equal pairs of values in them. If a pair is found it searches in the third array for the same value and returns it when it is found.

There is a handy array method called includes(). It could replace the whole looping of the third array, like this:

function searchThreeSameNum(arr1, arr2, arr3) {
    let i = 0, j = 0;
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            i++;
            continue;
        } else if (arr1[i] > arr2[j]) {
            j++;
            continue;
        } else if (arr1[i] == arr2[j]) {
            if (arr3.includes(arr1[i])) return arr1[i];
        } 
    }
    return 'No equal numbers';
}

I could even go a step further and get rid of the while loop altogether by looping through array 1 and see if its values are contained in array 2 and 3, like this:

function searchThreeSameNum2(arr1, arr2, arr3) {
    for (number of arr1) {
        if (arr2.includes(number) && arr3.includes(number)) return number;
    }
    return 'No equal numbers';
}

Note that this simplification makes this function easy to read, but also less efficient. It has to checks array 2 and 3 completely, for every element of array 1, until a match is found.

The assumption, in the function above, is that array 1 is properly sorted. If it isn't you can sort it.

function searchThreeSameNum2(arr1, arr2, arr3) {
    let sorted = arr1.sort((a, b) => a - b);
    for (number of sorted) {
        if (arr2.includes(number) && arr3.includes(number)) return number;
    }
    return 'No equal numbers';
}

Arrays 2 and 3 don't need to be sorted.

In summary

1. If you use a while loop, always break the loop with a proper condition in the right place. Do not use endless loops.
2. Try not to use complex execution flow constructions, with lot of else, continue and return. They are difficult to read and to debug.
3. Use the build in array methods, they are very handy, but don't overdo it.

Answer 3

An easier way is to use JavaScript's Array.includes, Array.some and/or Array.find methods

let arr1 = [1, 3, 11, 32, 44, 99]
let arr2 = [4, 12, 15, 99]
let arr3 = [4, 11, 13, 15, 23, 43]

function searchThreeSameNum (arr1, arr2, arr3) {
  return arr1.find(number => {
    return arr2.includes(number) && arr3.includes(number)
  })
}

const result = searchThreeSameNum(arr1, arr2, arr3)
console.log(result)

Answer 4

Well, you have one huge bug in the code. You have return … as the last line of the while(1) loop. This return will be hit the moment first arr1 and arr2 elements match but arr3 does not contain that element. I suggest you to use Roland's approach as it works and keeps your general algorithm the same.

Answer 5

Sometimes it is worth generalizing an algorithm to handle an arbitrary number of inputs. Not always, of course, but at least the exercise of thinking about how you would generalize an algorithm can force you to consider whether there is any unnecessary code duplication---this might be the algorithmic analogue of looking for magic constants.

It turns out that, with the exact same number of lines of code, you can make a smallestCommonElement function that takes any number of arrays as arguments.

This has a time complexity at least as good as the original. Without having done a careful analysis, if there are \$k\$ arrays of lengths \$n_1,\dots,n_k\$, then it seems to run in \$O(n_1 + \dots + n_k)\$ time. (The index into a given array is guaranteed to increase at least once every two iterations of the main loop.) The original seems to have time complexity \$O((n_1 + n_2)n_3)\$.

This code uses Roland's idea of using while loops to step indices forward for each array and Kiko Software's suggestion to avoid the while(1).

/* Takes sorted numerical arrays as arguments, returns the smallest
   common element between them or null. */
function smallestCommonElement(/*arguments*/) {
  // Indices into the given arrays
  let indices = Array(arguments.length).fill(0);
  // The current possible smallest common element
  let cur_val = -Infinity;

  do {
    var same = true;
    for (let i = 0; i < arguments.length; i++) {
      // Step an array forward to cur_val (or beyond if the array
      // doesn't have cur_val)
      while (indices[i] < arguments[i].length && arguments[i][indices[i]] < cur_val) {
        indices[i]++;
      }
      if (indices[i] < arguments[i].length) {
        if (arguments[i][indices[i]] > cur_val) {
          // We went past cur_val, so record in 'same' that cur_val does
          // not represent the smallest common element this time through.
          same = false;
          cur_val = arguments[i][indices[i]];
        }
      } else {
        // We got to the end of this array, so there is no smallest common element.
        return null;
      }
    }
  } while (!same);

  return cur_val;
}