Array.diff

A JavaScript solution to Array.diff, a 6 kyu Codewars problem

Photo by Andrew Neel on Unsplash

Implement a difference function, which subtracts one list from another and returns the result.

It should remove all values from list a, which are present in list b keeping their order.

arrayDiff([1,2],[1]) == [2]

If a value is present in b, all of its occurrences must be removed from the other

arrayDiff([1,2,2,2,3],[2]) == [1,3]

Before reading the solution below, try to solve Array.diff, a 6 kyu problem, yourself on Codewars.

Understand the Problem

While the name of the problem and prompt suggest that elements of argument 2 array ought to be removed from argument 1 array, an alternative yet equivalent way to think about the problem is in terms of inclusion. The return array should include the elements of argument 1 array and not include the elements of argument 2 array.

The second part of the prompt specifies that all occurrences of elements in argument 1 array should not be returned if it is an element in argument 2 array. It is simpler to pose the prompt in terms of inclusion instead of posing in terms of difference, subtraction, or removal.

In terms of inclusion, the prompt becomes: return an array that includes elements of argument 1 array and does not include any element of argument 2 array.

Inputs and Edge Cases

There are two inputs given in the prompt itself. The solution should at least handle these:

1. arrayDiff([1, 2], [1]) == [2]
2. arrayDiff([1, 2, 2, 2, 3], [2]) == [1, 3]

Some edge cases to consider are empty arrays. Argument 1 array, argument 2 array, or both can be empty:

1. arrayDiff([], [1, 2]) == []
2. arrayDiff([1, 2], []) == [1, 2]
3. arrayDiff([], []) == []

Pseudocode the Solution

Overall, what I want to do is to start from an empty array, add elements that meet certain conditions, and return that array. For each element in argument 1 array, I want to check if it is included in argument 2 array. If it is not included, I want to push that element into my return array. This should handle the inputs above.

The edge cases should be handled before looping through argument 1 array. Edge case 1 and 3 return an empty array if argument 1 array is empty, and edge case 2 returns argument 1 array if argument 2 array is empty. Handling this before any loops saves on computation, since they can be returned without any loops.

Putting this overall strategy in pseudocode:

1. Create function called “arrayDiff” that takes two arrays as arguments, “array1” and “array2.”
2. Handle edge cases:
   a. If the length of “array1” is 0, return an empty array
   b. If the length of “array2” is 0, return “array1”
3. Create the array to return called “returnArray”
4. Loop through “array1”
5. If the element is not included in “array2”, push the element to “returnArray”
6. Return “returnArray”

Write the Solution

Implementation of pseudocode using JavaScript in the Codewars web editor

// Create function called “arrayDiff” that takes two arrays as arguments, “array1” and “array2.”
function arrayDiff(array1, array2) {
// Handle edge cases: (a) If the length of “array1” is 0, return an empty array
if(array1.length === 0){return []}
// Handle edge cases: (b) If the length of “array2” is 0, return “array1”
if(array2.length === 0){return array1}


// Create the array to return called “returnArray”
let returnArray = [];
// Loop through “array1”
array1.forEach(function included(element){
// If the element is not included in “array2”, push it to “returnArray”
if(!array2.includes(element)){returnArray.push(element)}
})

// Return “returnArray”
return returnArray;
}

Test the Solution

Console logging the inputs and edge cases returned the expected arrays. The solution works as expected.

Input 1: array1 has one element that needs to excluded

Input 2: array1 has multiple occurrences that need to be excluded

Edge case 1: array1 is empty

Edge case 2: array2 is empty

Edge case 3: both array1 and array2 are empty

Evaluate the Solution

In terms of legibility, the solution is easy for engineers to evaluate and maintain in the future.

In terms of time complexity, there is room for improvement. The forEach method, which is a simple loop, has a time complexity is O(n). The includes method too is simple loop, so its time complexity is also O(n). Since the includes method is nested inside of the forEach method, the time complexity of the solution is O(n*n) = O(n²). Therefore, in terms of time complexity, there is room for improvement. This would be a slow solution if the length of inputted arrays are high.

Some other edge cases to consider are if inputs are not arrays. This can be accounted for by including an additional condition before the forEach method. If either arguments are not arrays, it can return a message stating that the function expects arrays as inputs.

Your Solution

How did you approach this problem? Did you use different JavaScript methods? Were you able to implement a solution with better time complexity? Did you use a different programming language altogether?

I’d love to hear from you! Please share how you solved this problem in the comments below, so others and I can learn.