Minimized Maximum Of Products Distributed To Any Store - Leetcode Solution

Problem:

You are given two arrays of integers, nums1 and nums2, and a positive integer k. You can distribute nums1[i] * nums2[j] products to any ith store and any jth store such that (0 <= i < nums1.length) and (0 <= j < nums2.length), and there must be exactly k products distributed in total. Return the minimized maximum product of any shopping cart, where a shopping cart is the set of products distributed to a single store.

Solution:

Approach:

• We need to find the minimized maximum product of any shopping cart.
• So, we can use binary search to minimize the maximum product of any shopping cart. We can set the left boundary as 0 and the right boundary as the product of the maximum element of nums1 and nums2.
• We will define a function, ‘count’ which takes in a number ‘mid’ as input. This function will calculate the total number of products distributed such that the maximum product of any shopping cart is less than mid.
• Based on the output of the count function, we will adjust the boundaries of the binary search.

Algorithm:

1. Create a function ‘count’ which takes in ‘mid’ as input. This function will do the following:

• Initialize the variables ‘count’ and ‘j’ to 0.
• Loop through all the elements of nums1 and nums2 and do the following:
  • If the product of the current elements is less than or equal to mid:
    • Increment the variable ‘count’ by (j+1) as all previously visited elements of nums2 will also form a product less than or equal to mid with current element.
    • Increment the variable ‘j’ by 1.
  • If the product of the current elements is greater than mid:
    • Break out of the loop as all further products will also be greater than mid.
• Return the variable ‘count’.

2. Implement the binary search with left boundary as 0 and right boundary as the product of the maximum element of nums1 and nums2.

• While the left boundary is less than or equal to the right boundary:
  • Calculate the mid value as the average of left and right boundary.
  • If the count function returns a value greater than or equal to k:
    • Update the value of left boundary as mid+1.
  • Else, update the value of right boundary as mid-1.

3. Return the value of right boundary + 1, as the binary search will stop when the left boundary becomes greater than the right boundary. The last value of right boundary will be the minimized maximum product of any shopping cart.

Time Complexity:

• O(N*log(M)) where N is the maximum length of nums1 and nums2 and M is the product of the maximum element of nums1 and nums2. The count function will take O(N) and the binary search will take O(log(M)).

Space Complexity:

• O(1) constant extra space is used.

Code:

class Solution { public int maxProduct(int[] nums1, int[] nums2, int k) { int left = 0, right = 0; for(int num: nums1) left = Math.max(left, num); for(int num: nums2) right = Math.max(right, num); right *= left; while(left <= right) { int mid = (left + right) / 2; if(count(nums1, nums2, mid) >= k) right = mid - 1; else left = mid + 1; } return left; } public int count(int[] nums1, int[] nums2, int mid) { int count = 0, j = 0; for(int i=0; i<nums1.length; i++) { while(j<nums2.length && nums1[i]*nums2[j] <= mid) { j++; } count += j; } return count; } }

1