703178. Max and Min Product from 2 Arrays
Max and Min Product from 2 Arrays Slug: product-of-maximum-in-first-array-and-minimum-in-second3943 Difficulty: Basic Id: 703178 Topic Tags: Arrays, Data Structures Company Tags: Adobe
Summary
Given two arrays of integers arr1 and arr2, find the maximum product that can be obtained by multiplying one element from arr1 with one element from arr2. This problem involves finding the maximum and minimum elements in an array.
Detailed Explanation
To solve this problem, we need to first find the maximum and minimum elements in both arrays. Then, we can calculate the product of the maximum element from the first array and the minimum element from the second array, which will be the maximum possible product. The time complexity for finding the maximum and minimum elements is O(n), where n is the size of the array.
Here's a step-by-step breakdown of the solution:
- Initialize variables
max1,min1to store the maximum and minimum elements inarr1. - Initialize variables
max2,min2to store the maximum and minimum elements inarr2. - Iterate through
arr1and updatemax1andmin1as you find larger or smaller elements. - Iterate through
arr2and updatemax2andmin2as you find larger or smaller elements. - Calculate the product of
max1andmin2, which will be the maximum possible product.
Time complexity: O(n + m), where n and m are the sizes of the two arrays. Space complexity: O(1), as we only need a constant amount of space to store the variables.
Here's a diagram representing the algorithm:
+---------------+
| arr1 |
+---------------+
|
|
v
+---------------+
| max1, min1 |
+---------------+
|
|
v
+---------------+
| arr2 |
+---------------+
|
|
v
+---------------+
| max2, min2 |
+---------------+
|
|
v
+---------------+
| max1 \* min2 |
+---------------+
Optimized Solutions
Java
public class Main {
public static int findMaxProduct(int[] arr1, int[] arr2) {
int max1 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE;
for (int num : arr1) {
if (num > max1) {
max1 = num;
}
if (num < min1) {
min1 = num;
}
}
int max2 = Integer.MIN_VALUE;
int min2 = Integer.MAX_VALUE;
for (int num : arr2) {
if (num > max2) {
max2 = num;
}
if (num < min2) {
min2 = num;
}
}
return max1 * min2;
}
}