Maximum Distance in Arrays in Java
The Maximum Distance in Arrays problem requires determining the maximum absolute difference between any two integers drawn from separate arrays. Given various arrays, the goal is to find the pair of numbers (one from each) with the greatest absolute difference between them.
To help us understand the problem better, let's look at an example,
Example:
Input: int[][] arrays = {
{3,7,10,14},
{4, 8,11},
{6,12,18}
};
Output: Maximum Distance: 15
Explanation:
1. Array1: {3, 7, 10, 14}
min = 3 and max = 14.
The first array does not require an update.
2. Array 2: {4, 8, 11}
Determine the distances: distance1 = abs(4 - 14) = 10 and distance2 = abs(11 - 3) = 8
Update the variables: max = 11 and maxDistance = max(maxDistance, distance1, distance2) = 10.
3. Array 3: {6, 12, 18}
Determine the distances using the formulas distance1 = abs(6 - 11) = 5 and distance2 = abs(18 - 3) = 15.
Update the variables: max = 18 and maxDistance = max(maxDistance, distance1, distance2) = 15.
After iterating through all arrays, the maximum distance is determined to be 15. The greatest difference between the highest and lowest numbers seen throughout the iteration, which are 18 and 3, respectively.
Brute Force Approach
The Java code defines a class MaxDistance and a method findMaxDistance() to compute the maximum distance between pairs of integers from various arrays. The application populates a 2D array named arrays with three integer arrays. The findMaxDistance() method uses nested loops to traverse over all array and integer pairings, computing the absolute difference and updating the maximum distance.
FileName: MaxDistance.java
public class MaxDistance {
public static void main(String[] args) {
int[][] arrays = {
{3, 7, 10, 14},
{4, 8, 11},
{6, 12, 18}
};
int maxDistance = findMaxDistance(arrays);
System.out.println("Maximum Distance: " + maxDistance);
}
private static int findMaxDistance(int[][] arrays) {
int maxDistance = 0;
// Iterate through all pairs of integers from different arrays
for (int i = 0; i < arrays.length; i++) {
for (int j = i + 1; j < arrays.length; j++) {
// Calculate distance between each pair and update maxDistance
for (int num1 : arrays[i]) {
for (int num2 : arrays[j]) {
maxDistance = Math.max(maxDistance, Math.abs(num1 - num2));
}
}
}
}
return maxDistance;
}
}
Output:
Maximum Distance: 15
Complexity Analysis: The code has a time complexity of O(N^3), where N is the maximum size of the arrays. This is due to nested loops iterating over all pairs of arrays and integers and the space complexity of the provided code is O(1).
Dynamic Programming Approach
The provided Java code's findMaxDistance() method computes the maximum distance between pairs of numbers from separate arrays. It uses nested loops to run through each array, determining the min and max values. These extremal values are kept in distinct arrays (minArray and maxArray). The method then uses another loop to compare the current array to previously processed ones, changing the total maximum distance based on the difference between the max and min values.
FileName: MaxDistance1.java
public class MaxDistance1 {
public static void main(String[] args) {
int[][] arrays = {
{3, 7, 10, 14},
{4, 8, 11},
{6, 12, 18}
};
int maxDistance = findMaxDistance(arrays);
System.out.println("Maximum Distance: " + maxDistance);
}
private static int findMaxDistance(int[][] arrays) {
int maxDistance = 0;
int[] minArray = new int[arrays.length];
int[] maxArray = new int[arrays.length];
// Iterate through each array
for (int i = 0; i < arrays.length; i++) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// Update min and max values for the current array
for (int num : arrays[i]) {
min = Math.min(min, num);
max = Math.max(max, num);
}
minArray[i] = min;
maxArray[i] = max;
// Update maxDistance based on the current and previous arrays
for (int j = 0; j < i; j++) {
maxDistance = Math.max(maxDistance, Math.max(maxArray[i] - minArray[j], maxArray[j] - minArray[i]));
}
}
return maxDistance;
}
}
Output:
Maximum Distance: 15
Complexity Analysis: The provided code has a time complexity of O(N^2 * M), where N is the number of arrays and M is their average size and the space complexity is O(N).
Two Pointers Approach
The Java code creates a class MaxDistance2 and a method findMaxDistance() that efficiently computes the maximum distance between integer pairs from distinct arrays. The program creates variables min and max to capture the min and max values in each array. It iterates through each array, updating the min and max values as needed, then calculates the distance for the current array. The method updates the overall maximum distance and then returns the result.
FileName: MaxDistance2.java
public class MaxDistance2 {
public static void main(String[] args) {
int[][] arrays = {
{3, 7, 10, 14},
{4, 8, 11},
{6, 12, 18}
};
int maxDistance = findMaxDistance(arrays);
System.out.println("Maximum Distance: " + maxDistance);
}
private static int findMaxDistance(int[][] arrays) {
int maxDistance = 0;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// Iterate through each array
for (int[] array : arrays) {
// Update min and max values for the current array
for (int num : array) {
min = Math.min(min, num);
max = Math.max(max, num);
}
// Update maxDistance based on the current array
maxDistance = Math.max(maxDistance, max - min);
}
return maxDistance;
}
}
Output:
Maximum Distance: 15
Complexity Analysis: The provided code has a time complexity of O(N * M), where N is the number of arrays and M is the average array size, as a result of linearly iterating through each array's items, and space complexity is O(1).