1. Introduction
In this tutorial, we’ll explore how to check if two 2d arrays are equal in Java. First, we’re going to go over the problem and explore it to better understand it. This way, we’ll also understand the common pitfalls and what to look for when dealing with similar problems.
Then, we’ll go over a naive approach to better understand the concepts. Afterwards, we’ll develop a different algorithm. Further, we’ll understand how to solve this problem without using too many resources. Therefore, knowing how to properly compare 2D arrays is not only about solving programming problems.
2. Problem Definition
Comparing 2D arrays is very important in various domains of software development. Here are some domains that use 2D arrays:
- image processing (computer vision and image manipulation)
- game development (represent game boards, maps, or tile-based worlds)
- artificial intelligence (machine learning algorithms – neural networks)
- security and cryptography (some encryption algorithms use 2d arrays of bytes or integers)
Comparing 2D arrays is more challenging than comparing 1D arrays. Unlike 1D arrays, 2D arrays need us to match both rows and columns. Consequently, this adds another layer of complexity.
Furthermore, we need to consider performance – naive methods are usually resource-intensive, especially with larger arrays.
Finally, 2D arrays being nested data structures means the code is more complex and the chances of errors are increased.
First, let’s assume we have two 2d arrays with m number of rows and n number of columns. As a side note, in algorithmics, we usually use m and n to refer to rows and columns, respectively. Now, to consider these two arrays equal, multiple conditions need to be met:
- they must have the same number of rows m
- they must have the same number of columns n
- corresponding elements (arr1[i][j], arr2[i][j]) need to be equal for each i and j
- special considerations: treating null values and objects
3. Naive Approach
Normally, we’d use the Arrays.deepEquals() method. This solution is great when we need an out of the box solution. In our case, its complexity is the same as the below approach, O(m*n).
Another way to approach this problem is, naturally, the first we can think of. Consequently, we’re going to go through each array and compare each element to its correspondent.
First, let’s see what this solution looks like and then, we’ll explore it in more detail:
public static boolean areArraysEqual(int[][] arr1, int[][] arr2) {
if (arr1 == null || arr2 == null || arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
// check if rows have different lengths
if (arr1[i] == null || arr2[i] == null || arr1[i].length != arr2[i].length) {
return false;
}
for (int j = 0; j < arr1[i].length; j++) {
if (arr1[i][j] != arr2[i][j]) {
return false;
}
}
}
return true;
}
As we can see, we’re using a loop within a loop. This means the time complexity (big O notation) will be O(m*n) where m and n represent the number of rows and columns, respectively. Additionally, the space complexity will be O(1) because the memory needed to solve this problem doesn’t increase with the input size.
The advantages of this approach are:
- easy to understand and implement
- works for various-sized arrays (jagged arrays)
- stops immediately once the first discrepancy is identified
The disadvantages are:
- poor time complexity
- not optimized
One important aspect is that we need to change our approach when dealing with objects. First, the != comparison won’t work for objects. Second, we’ll need to use the equals() method and make sure the objects we’re comparing have overwritten this method. Finally, we’ll also need to take into consideration null values.
4. Efficient Solution
Now, let’s think of another solution. This solution is useful for large arrays where we can accept some differences between the two arrays.
First, we’ll need two double parameters, let’s name them similarityThreshold and samplingWeight. Setting the similarityThreshold with a higher value allows for fewer different elements, while a smaller value allows for more different elements. On the other hand, the samplingWeight gives us control over the number of comparisons to perform.
This solution has the same time complexity of O(m*n) as the naive one in its worst case when the samplingWeight is set to its maximum. The maximum is 1, representing 100%, and all elements are compared.
Now, let’s look at our algorithm. First, we do some basic checks to see if the references point to the same object, are null, or have different lengths:
public static boolean areArraysEqual(int[][] arr1, int[][] arr2, double similarityThreshold, double samplingWeight) {
if (arr1 == null || arr2 == null || arr1.length != arr2.length ||
arr1[0].length != arr2[0].length || samplingWeight <= 0 || samplingWeight > 1) {
return false;
}
int similarElements = 0;
int checkedElements = 0;
Next, we’ll calculate the sampling step based on the sampling weight:
int step = Math.max(1, (int)(1 / samplingWeight));
// Iterate through the arrays using the calculated step
for (int i = 0; i < arr1.length; i += step) {
for (int j = 0; j < arr1[0].length; j += step) {
if (Math.abs(arr1[i][j] - arr2[i][j]) <= 1) {
similarElements++;
}
checkedElements++;
}
}
Using this, the algorithm knows how many elements to step over before performing the next comparison. This means that the smaller the samplingWeight, the faster the algorithm will be. However, the drawback here is the smaller the samplingWeight, the bigger the chance to skip over different elements.
Finally, we divide the similar elements identified by the checked elements to calculate the similarity ratio and compare it with the previously set threshold:
return (double) similarElements / checkedElements >= similarityThreshold;
}
5. Conclusion
In this article, we looked at how to compare two 2d arrays in Java. Moreover, we learned the importance of this comparison and its use in various fields.
We saw that the simplest and safest way is to compare each element at each position or use the Arrays.deepEquals() method. These solutions have the highest accuracy but also perform the most steps when the arrays are identical.
Next, we’ve seen a different solution, suitable for larger data sets. This solution can be much faster but with poorer accuracy. It’s up to us to determine which solution fits our needs.
As always, the code is available over on GitHub.