Given an integer array arr[] of size N, the task is to find the maximum length subarray whose products of element is non zero. .
Examples:
Input: arr[] = [1, 1, 0, 2, 1, 0, 1, 6, 1]
Output: 3
Explanation
Possible subarray whose product are non zero are [1, 1], [2, 1] and [1, 6, 1]
So maximum possible length is 3.
Input: arr[] = [0, 1, 2, 1, 3, 0, 0, 1]
Output: 4
Explanation
Possible subarray whose product are non zero are [1, 2, 1, 3] and [1]
So maximum possible length is 4 .
Approach:
- Save all the indices of zero from input array.
- Longest subarray must lie inside below three ranges:
- Start from zero index and end at first zero index – 1.
- Lies between two zero index.
- Start at last zero index + 1 and end at N-1.
- Finally find the maximum length from all cases.
Here is implementation of above approach :
C++
// C++ program to find maximum // length subarray having non// zero product#include<bits/stdc++.h>using namespace std;// Function that returns the// maximum length subarray // having non zero productvoid Maxlength(int arr[],int N){ vector<int> zeroindex; int maxlen; // zeroindex list to store index // of zero for(int i = 0; i < N; i++) { if(arr[i] == 0) zeroindex.push_back(i); } if(zeroindex.size() == 0) { // If zeroindex list is empty // then Maxlength is as // size of array maxlen = N; } // If zeroindex list is not empty else { // for example list 1 1 0 0 1 // is on index 0 1 2 3 4 // first zero is on index 2 // that means two numbers positive, // before index 2 so as // their product is positive to maxlen = zeroindex[0]; // Checking for other index for(int i = 0; i < zeroindex.size() - 1; i++) { // If the difference is greater // than maxlen then maxlen // is updated if(zeroindex[i + 1]- zeroindex[i] - 1 > maxlen) { maxlen = zeroindex[i + 1] - zeroindex[i] - 1; } } // To check the length of remaining // array after last zeroindex if(N - zeroindex[zeroindex.size() - 1] - 1 > maxlen) { maxlen = N - zeroindex[ zeroindex.size() - 1] - 1; } } cout << maxlen << endl;}// Driver Codeint main(){ int N = 9; int arr[] = {7, 1, 0, 1, 2, 0, 9, 2, 1}; Maxlength(arr, N);} // This code is contributed by Surendra_Gangwar |
Java
// Java program to find maximum // length subarray having non // zero product import java.util.*; class GFG{// Function that returns the // maximum length subarray // having non zero product static void Maxlength(int arr[],int N) { Vector<Integer> zeroindex = new Vector<Integer>(); int maxlen; // zeroindex list to store index // of zero for(int i = 0; i < N; i++) { if (arr[i] == 0) zeroindex.add (i); } if (zeroindex.size() == 0) { // If zeroindex list is empty // then Maxlength is as // size of array maxlen = N; } // If zeroindex list is not empty else { // for example list 1 1 0 0 1 // is on index 0 1 2 3 4 // first zero is on index 2 // that means two numbers positive, // before index 2 so as // their product is positive to maxlen = (int)zeroindex.get(0); // Checking for other index for(int i = 0; i < zeroindex.size() - 1; i++) { // If the difference is greater // than maxlen then maxlen // is updated if ((int)zeroindex.get(i + 1) - (int)zeroindex.get(i) - 1 > maxlen) { maxlen = (int)zeroindex.get(i + 1) - (int)zeroindex.get(i) - 1; } } // To check the length of remaining // array after last zeroindex if (N - (int)zeroindex.get( zeroindex.size() - 1) - 1 > maxlen) { maxlen = N - (int)zeroindex.get( zeroindex.size() - 1) - 1; } } System.out.println(maxlen); } // Driver code public static void main(String args[]) { int N = 9; int arr[] = { 7, 1, 0, 1, 2, 0, 9, 2, 1 }; Maxlength(arr, N); }}// This code is contributed by amreshkumar3 |
Python3
# Python3 program to find # maximum length subarray # having non zero product# function that returns the# maximum length subarray # having non zero productdef Maxlength(arr, N): zeroindex =[] # zeroindex list to store index # of zero for i in range(N): if(arr[i] == 0): zeroindex.append(i) if(len(zeroindex) == 0): # if zeroindex list is empty # then Maxlength is as # size of array maxlen = N # if zeroindex list is not empty else: # for example list 1 1 0 0 1 # is on index 0 1 2 3 4 # first zero is on index 2 # that means two numbers positive, # before index 2 so as # their product is positive to maxlen = zeroindex[0] # checking for other index for i in range(0, len(zeroindex)-1): # if the difference is greater # than maxlen then maxlen # is updated if(zeroindex[i + 1]\ - zeroindex[i] - 1\ > maxlen): maxlen = zeroindex[i + 1]\ - zeroindex[i] - 1 # to check the length of remaining # array after last zeroindex if(N - zeroindex[len(zeroindex) - 1]\ - 1 > maxlen): maxlen = N\ - zeroindex[len(zeroindex) - 1] - 1 print(maxlen)# Driver Codeif __name__ == "__main__": N = 9 arr = [7, 1, 0, 1, 2, 0, 9, 2, 1] Maxlength(arr, N) |
C#
// C# program to find maximum // length subarray having non // zero product using System; using System.Collections.Generic;class GFG{// Function that returns the // maximum length subarray // having non zero product static void Maxlength(int []arr,int N) { int[] zeroindex = new int[20000]; int maxlen; // zeroindex list to store index // of zero int size = 0; for(int i = 0; i < N; i++) { if (arr[i] == 0) zeroindex[size++] = i; } if (size == 0) { // If zeroindex list is empty // then Maxlength is as // size of array maxlen = N; } // If zeroindex list is not empty else { // for example list 1 1 0 0 1 // is on index 0 1 2 3 4 // first zero is on index 2 // that means two numbers positive, // before index 2 so as // their product is positive to maxlen = zeroindex[0]; // Checking for other index for(int i = 0; i < size; i++) { // If the difference is greater // than maxlen then maxlen // is updated if (zeroindex[i + 1]- zeroindex[i] - 1 > maxlen) { maxlen = zeroindex[i + 1] - zeroindex[i] - 1; } } // To check the length of remaining // array after last zeroindex if (N - zeroindex[size - 1] - 1 > maxlen) { maxlen = N - zeroindex[size - 1] - 1; } } Console.WriteLine(maxlen); } // Driver code public static void Main() { int N = 9; int []arr = { 7, 1, 0, 1, 2, 0, 9, 2, 1 }; Maxlength(arr, N); }}// This code is contributed by amreshkumar3 |
Javascript
<script>// Javascript program to find maximum // length subarray having non // zero product // Function that returns the // maximum length subarray // having non zero product function Maxlength(arr, N) { let zeroindex = Array.from({length: 20000}, (_, i) => 0); let maxlen; // zeroindex list to store index // of zero let size = 0; for(let i = 0; i < N; i++) { if (arr[i] == 0) zeroindex[size++] = i; } if (size == 0) { // If zeroindex list is empty // then Maxlength is as // size of array maxlen = N; } // If zeroindex list is not empty else { // for example list 1 1 0 0 1 // is on index 0 1 2 3 4 // first zero is on index 2 // that means two numbers positive, // before index 2 so as // their product is positive to maxlen = zeroindex[0]; // Checking for other index for(let i = 0; i < size; i++) { // If the difference is greater // than maxlen then maxlen // is updated if (zeroindex[i + 1]- zeroindex[i] - 1 > maxlen) { maxlen = zeroindex[i + 1] - zeroindex[i] - 1; } } // To check the length of remaining // array after last zeroindex if (N - zeroindex[size - 1] - 1 > maxlen) { maxlen = N - zeroindex[size - 1] - 1; } } document.write(maxlen); } // Driver Code let N = 9; let arr = [ 7, 1, 0, 1, 2, 0, 9, 2, 1 ]; Maxlength(arr, N); </script> |
Output:
3
Time complexity: O (N)
Auxiliary Space: O (N)
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!
