Given arrays arr1[] of size M and arr2[] of size N having length at least 2, the task is for every element in arr1[], maximize the product of two elements in arr2[] which are closest to the element in arr1[]. The closest elements must be present on distinct indices.
Example:
Input: arr1 = [5, 10, 17, 22, -1], arr2 = [-1, 26, 5, 20, 14, 17, -7]
Output: -5 70 340 520 7
Explanation:
The closest elements to 5 are 5 and -1, therefore the maximum product is -5
The closest elements to 10 are 5 and 14, therefore the maximum product is 70
The closest elements to 17 are 20, 17, and 14, therefore the maximum product of 20 and 17 is 340
The closest elements to 22 are 20 and 26, therefore the maximum product is 520
The closest elements to -1 are -1, 5, and -7, therefore the maximum product of -1 and -7 is 7Input: arr1 = [3, 9, 4, -1, 22], arr2 = [-1, 1, 21, 8, -3, 20, 25]
Output: -1 8 8 3 420
Approach: The given problem can be solved using a greedy approach. The idea is to sort the array arr2 in ascending order, then for every element in arr1, find the closest element to it in arr2, using binary search. Below steps can be followed to solve the problem:
- Sort the array arr2 in ascending order
- Iterate the array arr1 and at every iteration, apply binary search on arr2 to find an index of element closest to arr1[i], say x:
- If there does not exists a previous index x-1, then return arr2[x] * arr2[x+1]
- Else If there does not exists a next index x+1, then return arr2[x] * arr2[x-1]
- Else, check which element between arr2[x-1] and arr2[x+1] is closer to arr1[i]:
- If arr2[x-1] is closer return arr2[x] * arr2[x-1]
- Else if arr2[x+1] is closer return arr2[x] * arr2[x+1]
- Else if both arr2[x-1] and arr2[x+1] are equidistant from arr1[i] then return the maximum product between arr2[x] * arr2[x+1] and arr2[x] * arr2[x+1]
Below is the implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Binary search function to// find element closest to arr1[i]int binarySearch(int num, vector<int> arr){ // Initialize left right and mid int mid = -1, left = 0, right = arr.size() - 1; // Initialize closest index and // smallest difference int closestInd = -1; int smallestDiff = INT_MAX; while (left <= right) { mid = (left + right) >> 1; if (abs(arr[mid] - num) < smallestDiff) { // Update smallest difference smallestDiff = abs(arr[mid] - num); // Update closest index closestInd = mid; } else if (abs(arr[mid] - num) == smallestDiff) { if (arr[mid] > arr[closestInd]) closestInd = mid; } if (arr[mid] == num) { // This is the closest // element index return mid; } else if (arr[mid] < num) { // Closer element lies // to the right left = mid + 1; } else { // Closer element lies // to the left right = mid - 1; } } return closestInd;}// Function to find the maximum product of// Closest two elements in second array// for every element in the first arrayvector<int> maxProdClosest(vector<int> arr1, vector<int> arr2){ // Find the length of both arrays int M = arr1.size(), N = arr2.size(); // Initialize an array to store // the result for every element vector<int> ans(M); // Sort the second array arr2 sort(arr2.begin(), arr2.end()); // Iterate the array arr1 for (int i = 0; i < M; i++) { // Apply binary search and // find the index of closest // element to arr1[i] in arr2 int ind = binarySearch(arr1[i], arr2); // No element at previous index if (ind == 0) { ans[i] = arr2[ind] * arr2[ind + 1]; } // No element at the next index else if (ind == N - 1) { ans[i] = arr2[ind] * arr2[ind - 1]; } // Elements at the next and // previous indices are present else { // arr2[ind - 1] is closer // to arr1[i] if (abs(arr2[ind - 1] - arr1[i]) < abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind - 1]; } else if ( // arr2[ind + 1] is // closer to arr1[i] abs(arr2[ind - 1] - arr1[i]) > abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind + 1]; } // If both arr2[ind - 1] and // arr2[ind + 1] are // equidistant from arr1[i] else { ans[i] = max( arr2[ind] * arr2[ind - 1], arr2[ind] * arr2[ind + 1]); } } } // Return the resulting array return ans;}// Driver functionint main(){ // Initialize the arrays vector<int> arr1 = {5, 10, 17, 22, -1}; vector<int> arr2 = {-1, 26, 5, 20, 14, 17, -7}; // Call the function vector<int> res = maxProdClosest(arr1, arr2); // Iterate the array and // print the result for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; }}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the maximum product of // Closest two elements in second array // for every element in the first array public static int[] maxProdClosest(int[] arr1, int[] arr2) { // Find the length of both arrays int M = arr1.length, N = arr2.length; // Initialize an array to store // the result for every element int[] ans = new int[M]; // Sort the second array arr2 Arrays.sort(arr2); // Iterate the array arr1 for (int i = 0; i < M; i++) { // Apply binary search and // find the index of closest // element to arr1[i] in arr2 int ind = binarySearch(arr1[i], arr2); // No element at previous index if (ind == 0) { ans[i] = arr2[ind] * arr2[ind + 1]; } // No element at the next index else if (ind == N - 1) { ans[i] = arr2[ind] * arr2[ind - 1]; } // Elements at the next and // previous indices are present else { // arr2[ind - 1] is closer // to arr1[i] if (Math.abs(arr2[ind - 1] - arr1[i]) < Math.abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind - 1]; } else if ( // arr2[ind + 1] is // closer to arr1[i] Math.abs(arr2[ind - 1] - arr1[i]) > Math.abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind + 1]; } // If both arr2[ind - 1] and // arr2[ind + 1] are // equidistant from arr1[i] else { ans[i] = Math.max( arr2[ind] * arr2[ind - 1], arr2[ind] * arr2[ind + 1]); } } } // Return the resulting array return ans; } // Binary search function to // find element closest to arr1[i] public static int binarySearch(int num, int[] arr) { // Initialize left right and mid int mid = -1, left = 0, right = arr.length - 1; // Initialize closest index and // smallest difference int closestInd = -1; int smallestDiff = Integer.MAX_VALUE; while (left <= right) { mid = (left + right) >> 1; if (Math.abs(arr[mid] - num) < smallestDiff) { // Update smallest difference smallestDiff = Math.abs(arr[mid] - num); // Update closest index closestInd = mid; } else if (Math.abs(arr[mid] - num) == smallestDiff) { if (arr[mid] > arr[closestInd]) closestInd = mid; } if (arr[mid] == num) { // This is the closest // element index return mid; } else if (arr[mid] < num) { // Closer element lies // to the right left = mid + 1; } else { // Closer element lies // to the left right = mid - 1; } } return closestInd; } // Driver function public static void main(String[] args) { // Initialize the arrays int[] arr1 = { 5, 10, 17, 22, -1 }; int[] arr2 = { -1, 26, 5, 20, 14, 17, -7 }; // Call the function int[] res = maxProdClosest(arr1, arr2); // Iterate the array and // print the result for (int i = 0; i < res.length; i++) { System.out.print(res[i] + " "); } }} |
Python3
# python3 code for the above approachINT_MAX = 2147483647# Binary search function to# find element closest to arr1[i]def binarySearch(num, arr): # Initialize left right and mid mid, left, right = -1, 0, len(arr) - 1 # Initialize closest index and # smallest difference closestInd = -1 smallestDiff = INT_MAX while (left <= right): mid = (left + right) >> 1 if (abs(arr[mid] - num) < smallestDiff): # Update smallest difference smallestDiff = abs(arr[mid] - num) # Update closest index closestInd = mid elif (abs(arr[mid] - num) == smallestDiff): if (arr[mid] > arr[closestInd]): closestInd = mid if (arr[mid] == num): # This is the closest # element index return mid elif (arr[mid] < num): # Closer element lies # to the right left = mid + 1 else: # Closer element lies # to the left right = mid - 1 return closestInd# Function to find the maximum product of# Closest two elements in second array# for every element in the first arraydef maxProdClosest(arr1, arr2): # Find the length of both arrays M, N = len(arr1), len(arr2) # Initialize an array to store # the result for every element ans = [0 for _ in range(M)] # Sort the second array arr2 arr2.sort() # Iterate the array arr1 for i in range(0, M): # Apply binary search and # find the index of closest # element to arr1[i] in arr2 ind = binarySearch(arr1[i], arr2) # No element at previous index if (ind == 0): ans[i] = arr2[ind] * arr2[ind + 1] # No element at the next index elif (ind == N - 1): ans[i] = arr2[ind] * arr2[ind - 1] # Elements at the next and # previous indices are present else: # arr2[ind - 1] is closer # to arr1[i] if (abs(arr2[ind - 1] - arr1[i]) < abs(arr2[ind + 1] - arr1[i])): ans[i] = arr2[ind] * arr2[ind - 1] elif ( # arr2[ind + 1] is # closer to arr1[i] abs(arr2[ind - 1] - arr1[i]) > abs(arr2[ind + 1] - arr1[i])): ans[i] = arr2[ind] * arr2[ind + 1] # If both arr2[ind - 1] and # arr2[ind + 1] are # equidistant from arr1[i] else: ans[i] = max( arr2[ind] * arr2[ind - 1], arr2[ind] * arr2[ind + 1]) # Return the resulting array return ans# Driver functionif __name__ == "__main__": # Initialize the arrays arr1 = [5, 10, 17, 22, -1] arr2 = [-1, 26, 5, 20, 14, 17, -7] # Call the function res = maxProdClosest(arr1, arr2) # Iterate the array and # print the result for i in range(0, len(res)): print(res[i], end=" ") # This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;class GFG { // Function to find the maximum product of // Closest two elements in second array // for every element in the first array public static int[] maxProdClosest(int[] arr1, int[] arr2) { // Find the length of both arrays int M = arr1.Length, N = arr2.Length; // Initialize an array to store // the result for every element int[] ans = new int[M]; // Sort the second array arr2 Array.Sort(arr2); // Iterate the array arr1 for (int i = 0; i < M; i++) { // Apply binary search and // find the index of closest // element to arr1[i] in arr2 int ind = binarySearch(arr1[i], arr2); // No element at previous index if (ind == 0) { ans[i] = arr2[ind] * arr2[ind + 1]; } // No element at the next index else if (ind == N - 1) { ans[i] = arr2[ind] * arr2[ind - 1]; } // Elements at the next and // previous indices are present else { // arr2[ind - 1] is closer // to arr1[i] if (Math.Abs(arr2[ind - 1] - arr1[i]) < Math.Abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind - 1]; } else if ( // arr2[ind + 1] is // closer to arr1[i] Math.Abs(arr2[ind - 1] - arr1[i]) > Math.Abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind + 1]; } // If both arr2[ind - 1] and // arr2[ind + 1] are // equidistant from arr1[i] else { ans[i] = Math.Max( arr2[ind] * arr2[ind - 1], arr2[ind] * arr2[ind + 1]); } } } // Return the resulting array return ans; } // Binary search function to // find element closest to arr1[i] public static int binarySearch(int num, int[] arr) { // Initialize left right and mid int mid = -1, left = 0, right = arr.Length - 1; // Initialize closest index and // smallest difference int closestInd = -1; int smallestDiff = Int32.MaxValue; while (left <= right) { mid = (left + right) >> 1; if (Math.Abs(arr[mid] - num) < smallestDiff) { // Update smallest difference smallestDiff = Math.Abs(arr[mid] - num); // Update closest index closestInd = mid; } else if (Math.Abs(arr[mid] - num) == smallestDiff) { if (arr[mid] > arr[closestInd]) closestInd = mid; } if (arr[mid] == num) { // This is the closest // element index return mid; } else if (arr[mid] < num) { // Closer element lies // to the right left = mid + 1; } else { // Closer element lies // to the left right = mid - 1; } } return closestInd; } // Driver function public static void Main(string[] args) { // Initialize the arrays int[] arr1 = { 5, 10, 17, 22, -1 }; int[] arr2 = { -1, 26, 5, 20, 14, 17, -7 }; // Call the function int[] res = maxProdClosest(arr1, arr2); // Iterate the array and // print the result for (int i = 0; i < res.Length; i++) { Console.Write(res[i] + " "); } }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript code for the above approach// Binary search function to// find element closest to arr1[i]function binarySearch(num, arr) { // Initialize left right and mid let mid = -1, left = 0, right = arr.length - 1; // Initialize closest index and // smallest difference let closestInd = -1; let smallestDiff = Number.MAX_SAFE_INTEGER; while (left <= right) { mid = (left + right) >> 1; if (Math.abs(arr[mid] - num) < smallestDiff) { // Update smallest difference smallestDiff = Math.abs(arr[mid] - num); // Update closest index closestInd = mid; } else if (Math.abs(arr[mid] - num) == smallestDiff) { if (arr[mid] > arr[closestInd]) closestInd = mid; } if (arr[mid] == num) { // This is the closest // element index return mid; } else if (arr[mid] < num) { // Closer element lies // to the right left = mid + 1; } else { // Closer element lies // to the left right = mid - 1; } } return closestInd;}// Function to find the maximum product of// Closest two elements in second array// for every element in the first arrayfunction maxProdClosest(arr1, arr2) { // Find the length of both arrays let M = arr1.length, N = arr2.length; // Initialize an array to store // the result for every element let ans = new Array(M); // Sort the second array arr2 arr2.sort((a, b) => a - b); // Iterate the array arr1 for (let i = 0; i < M; i++) { // Apply binary search and // find the index of closest // element to arr1[i] in arr2 let ind = binarySearch(arr1[i], arr2); // No element at previous index if (ind == 0) { ans[i] = arr2[ind] * arr2[ind + 1]; } // No element at the next index else if (ind == N - 1) { ans[i] = arr2[ind] * arr2[ind - 1]; } // Elements at the next and // previous indices are present else { // arr2[ind - 1] is closer // to arr1[i] if (Math.abs(arr2[ind - 1] - arr1[i]) < Math.abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind - 1]; } else if ( // arr2[ind + 1] is // closer to arr1[i] Math.abs(arr2[ind - 1] - arr1[i]) > Math.abs(arr2[ind + 1] - arr1[i])) { ans[i] = arr2[ind] * arr2[ind + 1]; } // If both arr2[ind - 1] and // arr2[ind + 1] are // equidistant from arr1[i] else { ans[i] = Math.max( arr2[ind] * arr2[ind - 1], arr2[ind] * arr2[ind + 1]); } } } // Return the resulting array return ans;}// Driver function// Initialize the arrayslet arr1 = [5, 10, 17, 22, -1];let arr2 = [-1, 26, 5, 20, 14, 17, -7];// Call the functionlet res = maxProdClosest(arr1, arr2);// Iterate the array and// print the resultfor (let i = 0; i < res.length; i++) { document.write(res[i] + " ");}// This code is contributed by Saurabh Jaiswal</script> |
Output
-5 70 340 520 7
Time Complexity: O(N * log N + M * log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
