Given an array arr[] of length N, the task is to find the minimum product of subarray of size K of an array including negative integers.
Example:
Input: arr = [2, 3, -1, -5, 4, 0], K = 3
Output: -6
Explanation: The product of the subarray {2, 3, -1} is -6 which is the minimum possible.Input: arr = [-2, -4, 0, 1, 5, -6, 9], K =4
Output: -270
Explanation: The product of the subarray {1, 5, -6, 9} is -270 which is the minimum possible.
If the array consists of only positive numbers the problem can be efficiently solved using only the sliding window technique as discussed here.
Approach: The given problem can be solved using the two-pointers technique and the sliding window approach. Below steps can be followed to solve the problem:
- Iterate the array arr till K – 1 and multiply every non-zero number to find the product and also count the number of zeros in the subarray.
- Iterate the array arr from K till the end of the array and at every iteration:
- If the current element is not a zero then multiply it to the product or else increment the count of zeros
- If the element to the left of the current sliding window is not a zero then divide the product by that element or else reduce the count of zeros
- If the number of zeros in the sliding window is 0 then update the result with the current product or else update it with zero
- Return the result res.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// product of subarray of size Kint minProdK(vector<int>& arr, int K){ // Initialize prod to 1 // and zeros to 0 int prod = 1, zeros = 0; // Initialize length of the array int N = arr.size(); // Iterate the array arr till K - 1 for (int i = 0; i < K; i++) { // If current element is 0 // then increment zeros if (arr[i] == 0) zeros++; // Else multiply current // element to prod else prod *= arr[i]; } // Initialize prod to 0 if zeros > 0 // else to prod int res = zeros == 0 ? prod : 0; // Iterate the array arr // from K till the end for (int right = K; right < N; right++) { // If current element is 0 // then increment zeros if (arr[right] == 0) zeros++; // Else multiply arr[right] // to prod else prod *= arr[right]; // If leftmost element in // the sliding window is 0 // then decrement zeros if (arr[right - K] == 0) zeros--; // Else divide prod by arr[right-K] else prod /= arr[right - K]; // If zeros == 0 then update // res by taking minimum value // of res and prod if (zeros == 0) res = min(res, prod); // If zeros > 0 and res > 0 // then initialize res to 0 else if (res > 0) res = 0; } // Return the answer as res return res;}// Driver codeint main(){ // Initialize the array vector<int> arr = { 2, 3, -1, -5, 4, 0 }; // Initialize the value of K int K = 3; // Call the function and // print the result cout << minProdK(arr, K); return 0;} // This code is contributed by rakeshsahni |
Java
// Java implementation for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum // product of subarray of size K public static int minProdK( int arr[], int K) { // Initialize prod to 1 // and zeros to 0 int prod = 1, zeros = 0; // Initialize length of the array int N = arr.length; // Iterate the array arr till K - 1 for (int i = 0; i < K; i++) { // If current element is 0 // then increment zeros if (arr[i] == 0) zeros++; // Else multiply current // element to prod else prod *= arr[i]; } // Initialize prod to 0 if zeros > 0 // else to prod int res = zeros == 0 ? prod : 0; // Iterate the array arr // from K till the end for (int right = K; right < N; right++) { // If current element is 0 // then increment zeros if (arr[right] == 0) zeros++; // Else multiply arr[right] // to prod else prod *= arr[right]; // If leftmost element in // the sliding window is 0 // then decrement zeros if (arr[right - K] == 0) zeros--; // Else divide prod by arr[right-K] else prod /= arr[right - K]; // If zeros == 0 then update // res by taking minimum value // of res and prod if (zeros == 0) res = Math.min(res, prod); // If zeros > 0 and res > 0 // then initialize res to 0 else if (res > 0) res = 0; } // Return the answer as res return res; } // Driver code public static void main(String[] args) { // Initialize the array int[] arr = { 2, 3, -1, -5, 4, 0 }; // Initialize the value of K int K = 3; // Call the function and // print the result System.out.println(minProdK(arr, K)); }} |
Python3
# Python 3 implementation for the above approach# Function to find the minimum# product of subarray of size Kdef minProdK(arr, K): # Initialize prod to 1 # and zeros to 0 prod = 1 zeros = 0 # Initialize length of the array N = len(arr) # Iterate the array arr till K - 1 for i in range(K): # If current element is 0 # then increment zeros if (arr[i] == 0): zeros += 1 # Else multiply current # element to prod else: prod *= arr[i] # Initialize prod to 0 if zeros > 0 # else to prod if zeros == 0: res = prod else: res = 0 # Iterate the array arr # from K till the end for right in range(K, N): # If current element is 0 # then increment zeros if (arr[right] == 0): zeros += 1 # Else multiply arr[right] # to prod else: prod *= arr[right] # If leftmost element in # the sliding window is 0 # then decrement zeros if (arr[right - K] == 0): zeros -= 1 # Else divide prod by arr[right-K] else: prod //= arr[right - K] # If zeros == 0 then update # res by taking minimum value # of res and prod if (zeros == 0): res = min(res, prod) # If zeros > 0 and res > 0 # then initialize res to 0 elif (res > 0): res = 0 # Return the answer as res return res# Driver codeif __name__ == "__main__": # Initialize the array arr = [2, 3, -1, -5, 4, 0] # Initialize the value of K K = 3 # Call the function and # print the result print(minProdK(arr, K)) # This code is contributed by ukasp. |
C#
// C# implementation for the above approachusing System;class GFG{ // Function to find the minimum // product of subarray of size K public static int minProdK( int []arr, int K) { // Initialize prod to 1 // and zeros to 0 int prod = 1, zeros = 0; // Initialize length of the array int N = arr.Length; // Iterate the array arr till K - 1 for (int i = 0; i < K; i++) { // If current element is 0 // then increment zeros if (arr[i] == 0) zeros++; // Else multiply current // element to prod else prod *= arr[i]; } // Initialize prod to 0 if zeros > 0 // else to prod int res = zeros == 0 ? prod : 0; // Iterate the array arr // from K till the end for (int right = K; right < N; right++) { // If current element is 0 // then increment zeros if (arr[right] == 0) zeros++; // Else multiply arr[right] // to prod else prod *= arr[right]; // If leftmost element in // the sliding window is 0 // then decrement zeros if (arr[right - K] == 0) zeros--; // Else divide prod by arr[right-K] else prod /= arr[right - K]; // If zeros == 0 then update // res by taking minimum value // of res and prod if (zeros == 0) res = Math.Min(res, prod); // If zeros > 0 and res > 0 // then initialize res to 0 else if (res > 0) res = 0; } // Return the answer as res return res; } // Driver code public static void Main() { // Initialize the array int[] arr = { 2, 3, -1, -5, 4, 0 }; // Initialize the value of K int K = 3; // Call the function and // print the result Console.Write(minProdK(arr, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript implementation for the above approach// Function to find the minimum// product of subarray of size Kfunction minProdK(arr, K) { // Initialize prod to 1 // and zeros to 0 let prod = 1, zeros = 0; // Initialize length of the array let N = arr.length; // Iterate the array arr till K - 1 for (let i = 0; i < K; i++) { // If current element is 0 // then increment zeros if (arr[i] == 0) zeros++; // Else multiply current // element to prod else prod *= arr[i]; } // Initialize prod to 0 if zeros > 0 // else to prod let res = zeros == 0 ? prod : 0; // Iterate the array arr // from K till the end for (let right = K; right < N; right++) { // If current element is 0 // then increment zeros if (arr[right] == 0) zeros++; // Else multiply arr[right] // to prod else prod *= arr[right]; // If leftmost element in // the sliding window is 0 // then decrement zeros if (arr[right - K] == 0) zeros--; // Else divide prod by arr[right-K] else prod /= arr[right - K]; // If zeros == 0 then update // res by taking minimum value // of res and prod if (zeros == 0) res = Math.min(res, prod); // If zeros > 0 and res > 0 // then initialize res to 0 else if (res > 0) res = 0; } // Return the answer as res return res;}// Driver code// Initialize the arraylet arr = [2, 3, -1, -5, 4, 0];// Initialize the value of Klet K = 3;// Call the function and// print the resultdocument.write(minProdK(arr, K));// This code is contributed by Saurabh Jaiswal</script> |
Output
-6
Time Complexity: O(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!
