Array Intersection Algorithms Compared

LJ Seng — Fri, 23 Jun 2023 06:37:33 +0000

Finding the intersection between two arrays is a common task in programming, and there are multiple ways to approach this problem. In this article, we will compare two algorithms implemented in JavaScript that find the intersection between two arrays. We will evaluate their space and time complexity to understand their efficiency and performance.

Algorithm 1:

const arr1 = [ 1, 2, 3, 4, 5, 6, ];
const arr2 = [ 8, 9, 4, 6, 7, 1, ];

const intercept = arr1.filter(x => arr2.includes(x));

Algorithm 2:

const arr1 = [ 1, 2, 3, 4, 5, 6, ];
const arr2 = [ 8, 9, 4, 6, 7, 1, ];

const computeIntercept = (array1, array2) => {
    const theSet = new Set(array1);
    return array2.filter(x => theSet.has(x));
};

const intercept = computeIntercept(arr2, arr1);

Space Complexity

The space complexity of an algorithm refers to the amount of memory required by the algorithm to solve a problem. In both algorithms, we are using additional data structures to store intermediate results.

Algorithm 1 uses the filter function to create a new array containing the intersecting elements. This algorithm does not require any additional space apart from the resulting array, which will have a maximum size equal to the smaller of the two input arrays. Therefore, the space complexity of Algorithm 1 is O(min(n, m)), where n and m are the sizes of the input arrays.

Algorithm 2 creates a Set from the first array, which requires additional space to store the unique elements. The space complexity of creating a Set is O(n), where n is the size of the first array. The resulting array obtained from filtering the second array will also have a maximum size equal to the smaller of the two input arrays. Hence, the overall space complexity of Algorithm 2 is O(n + min(n, m)).

Time Complexity

The time complexity of an algorithm refers to the amount of time taken by the algorithm to solve a problem. It measures the number of operations performed as the input size increases.

Algorithm 1 utilizes the includes function inside the filter function. The includes function has a time complexity of O(m), where m is the size of the second array. The filter function iterates over the elements of the first array, resulting in a time complexity of O(n). Therefore, the overall time complexity of Algorithm 1 is O(n * m).

Algorithm 2 creates a Set from the first array, which takes O(n) time, where n is the size of the first array. Filtering the second array has a time complexity of O(m), where m is the size of the second array. Thus, the time complexity of Algorithm 2 is O(n + m).

Comparison

Comparing the space and time complexities of the two algorithms, we can make the following observations:

Algorithm 1 has a better space complexity than Algorithm 2.
Algorithm 2 has a better time complexity than Algorithm 1.

Conclusion

Algorithm 1 is more space-efficient, but Algorithm 2 is more time-efficient when finding the intersection between two arrays. The choice between the algorithms depends on the specific requirements of the application, such as the available memory and the size of the input arrays.

If you have an alternative algorithm or a more efficient solution, please feel free to share it. 🙂

The elegance of bash chaining operators

LJ Seng — Sun, 22 Mar 2020 08:41:53 +0000

I am new to bash scripting.

In my quest to pick it up, I begin to heartily appreciate chaining operators. With the help of chaining operators, I may not need if conditional check in bash as often as other programming languages, i.e. Java or PHP.

Furthermore, to my surprise, lesser if does not degrade the expressiveness of the script. Instead, it is more elegant and concise once I understand the quirk of it.

Let's see what do I mean by looking at the following example.

I need to write a bash script that make sure at any instance of time there is only a maximum of 10 certain files in a directory.

My first version of the script goes like this:

#!/bin/bash
set -u

##### Variable declaration #####

MY_DIR=~/rotateLog
MAX_FILE_COUNT=10

##### Method definition #####

_delete_oldest_file() {
    ls -1tr $MY_DIR/temp.log.* | head -1 | xargs rm -f
}

##### Main #####

while true
do
    FILE_COUNT=`ls -1tr $MY_DIR/temp.log.* | wc -l`

    if [ $FILE_COUNT -gt $MAX_FILE_COUNT ]; then
        _delete_oldest_file
    fi
done

Program flow is pretty straight forward, described below:

Check current file count in the directory
Remove the oldest file from directory if there is more than what is needed

if conditional check is always the de facto approach to tackle any sort of decision making problem. This script is okay.

Then, as I learn about chaining operators, i.e. &&, ||, ;, etc, which are used to chain commands together, I think the script could be rewritten in a more concise manner. Let's focus on && for the moment being.

&& is used to chain commands together, such that the next commands is run if and only if the preceding command exited without error (exit code of 0).

Coupled with the fact that bash numeric comparison operators observe following behavior:

If numeric comparison is satisfied, exit code shall be 0. Else, exit code shall be 1. To illustrate:

$ [ 1 -gt 10 ]; echo $?
1
$ [ 11 -gt 10 ]; echo $?
0

Therefore, the original script could be revised to:

while true
do
    FILE_COUNT=`ls -1tr $MY_DIR/temp.log.* | wc -l`

    [ $FILE_COUNT -gt $MAX_FILE_COUNT ] && _delete_oldest_file
done

This is especially helpful if I have a flow involving many steps. Let's consider I have a 3 steps flow such that:

Run _do_A()
Run _do_B() if _do_A() is successfully executed
Run _do_C() if _do_B() failed to execute

Without the help of chaining operators, I likely need 3 if checking to deliver the flow. But with the help of chaining operators:

_do_A() && _do_B() || _do_C()

Elegant. Isn't it? 😎