11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Need more clarification. You could start by giving several cases, or at least the answer to this one. And when you say "common element", are you expecting just one answer? What happens if there's more than one? Can there be more than one? \$\endgroup\$ – Joseph Jun 5 at 15:12
  • \$\begingroup\$ What do you mean by "first" common element? The lowest value? Or some metric involving the three indices? \$\endgroup\$ – Toby Speight Jun 5 at 15:32
  • 1
    \$\begingroup\$ The lowest value \$\endgroup\$ – Gervenel Jun 5 at 15:40
  • \$\begingroup\$ I would rather compare two arrays, then compare that result to the third. I believe such code would be more reusable and easy to adapt to find the same value in 4 arrays. But it would be MUCH less efficient if you generally expect to find the first match of all 3 arrays fairly early. \$\endgroup\$ – Zizy Archer Jun 6 at 12:38
  • 1
    \$\begingroup\$ I just noticed how freakishly anemic the Set API in ECMAScript is. \$\endgroup\$ – Jörg W Mittag Jun 6 at 19:46
15
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ I would change let n = 0; to let same=1; and instead of n++; do same=0;. Then if (n === 0) becomes if (same). This clearly tells what the variable does. \$\endgroup\$ – Zizy Archer Jun 6 at 12:56
  • \$\begingroup\$ @Zizy thanks for the remark, I improved the code. \$\endgroup\$ – Roland Illig Jun 6 at 16:09
  • 2
    \$\begingroup\$ Math.max can take more than 2 numbers :) \$\endgroup\$ – hjpotter92 Jun 6 at 19:06
  • \$\begingroup\$ @hjpotter92 Thanks for the remark, the code is getting better with each revision :) \$\endgroup\$ – Roland Illig Jun 6 at 23:16
10
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ Searching the whole of arr2 and arr3 for each number in arr1 gives you O(N^2) complexity if they all have equal length. Or O(A * B) complexity if they're different. (Assuming worst-case where no hit is found). Reducing this to O(A + B +C) or so is the point of writing an algorithm instead of just using brute force library functions. The OP's code only searches arr3 for matches in arr1[i] == arr2[j]. It still has a bad N^2 worst-case, unlike Roland's answer, but only when arr1 and arr2 have a lot of matching elements vs. your always. \$\endgroup\$ – Peter Cordes Jun 6 at 1:49
  • 1
    \$\begingroup\$ For small problem sizes simplifying to a brute-force algorithm can be appropriate for simplicity readability, and I agree with your comments about it being hard to follow the logic. But your claim "we don't need the complex while loop at all" is an oversimplification that ignores the point of the algorithm the OP was attempting. And BTW, your final version only needs arr1 sorted if you care about finding the smallest same element, rather than a same element. \$\endgroup\$ – Peter Cordes Jun 6 at 1:54
  • \$\begingroup\$ @PeterCordes You're right that, at larger array sizes, the proposed algorithm is less efficient than an algorithm that walks all three arrays. I might indeed have gone a step too far. In this case there is clearly a trade-off between readability and efficiency. I stressed the former because it was lacking in the question, but if the latter is important, a slightly more complex algorithm is probably the beter choice. \$\endgroup\$ – KIKO Software Jun 6 at 8:54
  • \$\begingroup\$ Sure, it's useful to present the last most-readable option. My suggestion is just that you should introduce it accurately, as a less efficient algorithm that's simpler to write and read. For very small arrays it might be more efficient in practice (smaller / simpler code with less overhead). But Roland's algorithm looks very good for even small-ish arrays. \$\endgroup\$ – Peter Cordes Jun 6 at 9:32
  • \$\begingroup\$ I agree, I'll add that into my answer. \$\endgroup\$ – KIKO Software Jun 6 at 9:52
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ This is probably the simplest possible answer. I'd write it as const searchThreeSameNum = (arr1, arr2, arr3) => arr1.find(number => arr2.includes(number) && arr3.includes(number)) though \$\endgroup\$ – JollyJoker Jun 7 at 7:51
2
\$\begingroup\$

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;
}

\$\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.