Problem: Given an binary array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s.
Examples:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0,0,1}
Output: 1 to 8 (Starting and Ending indexes of output sub array)
Implementation:
In this method,use two nested loops. The outer loop picks a starting point i. The inner loop considers all subarrays starting from i. If size of a subarray is greater than maximum size so far, then update the maximum size.
In this implementation, 0s are considered as -1 and sum of all values from i to j is calculated. If sum becomes 0, then size of this subarray is compared with largest size so far. Complexity of this method is O(n^2).
int findLargestSubArray(int arr[], int n) { int sum = 0; int maxsize = -1, fromIndex; // Pick a starting point as i for (int i = 0; i < n-1; i++) { if(arr[j] == 0) sum = -1; else sum = 1; // Consider all subarrays for (int j = i+1; j < n; j++) { if(arr[j] == 0) sum += -1; else sum += 1; /* If this is a 0 sum subarray, then compare it with maximum size subarray calculated so far */ if(sum == 0 && maxsize < j-i+1) { maxsize = j - i + 1; fromIndex = i; } } } return maxsize; }
Time Complexity: O(n^2)
Auxiliary Space: O(1)
Any better approach if you have, please do comments.
O(nlgn) time) and O(n) space
int findLargestSubArray(int arr[], int n)
{
int i = 0,max = 0,index = 0;
stack s = NULL;
if (0 >=n)
return -1;
push(&s,arr[0])
for (i =1; i max)
max = index;
}
if (s.empty())
return n;
else
return max;
}
Neha Garg I don't know which algorithm can improve time complexity but what approach is given here is just a brute force approach.
can be done in O(n) time and space … asked in Gate2006 CS exam.
Time Complexity : O(n)
Auxiliary Space : O(n)
public static int maxLength(String line){
int counter = 0;
int max = 0;
int[] minPos = new int[line.length()*2+1];
for(int i = 0;i<line.length();i++){
boolean isOne = line.charAt(i) == '1';
counter = isOne ? counter+1 : counter-1;
if(counter==0){
max = i+1;
}else{
int lastPosOcurr = minPos[counter+line.length()];
if(lastPosOcurr!=0){
max = Math.max(max, i-lastPosOcurr);
}
}
}
return max;
}
Can be done in O(n)
take a global max=0;
treat 0 as -1
a) make cummulative sum and keep hashing them
b) once you find that hash value again update the size of max as (current_index-hash[arr[current_index]])
see code in c++
let int arr[]={};
map hash;
hash.clear();
for(int i=0;i<n;i++)
{
int temp;
if(arr[i]==0)
temp=-1;
your ideal is correct but the code not totally correct.
the full implementation in java pasted below:
public class LargestZeroOneSubarray {
public class Data {
public int start = 0;
public int end = 0;
public int length = 0;
public String toString() {
StringBuilder sb = new StringBuilder(“Data{ start [");
sb.append(start).append("], end [").append(end)
.append("], length [").append(length).append("]}”);
return sb.toString();
}
}
public Data getLargestSubarray(int[] a) {
// key will be the cumulative sum, and value will be index
Map sumIndexMap = new HashMap();
int sum = 0;
Data largestData = new Data();
//push first value into map first
sumIndexMap.put(0, 0);
for (int i = 0; i largestData.length) {
largestData.start = preIndex;
largestData.end = i;
largestData.length = i – preIndex + 1;
}
} else {
sumIndexMap.put(sum, i+1);
}
}
return largestData;
}
public static void main(String[] args){
int[] a = {1,1,1,1,0,0,1,1,1,1};
System.out.println(a);
Data output = new LargestZeroOneSubarray().getLargestSubarray(a);
System.out.println(output);
}
}
#Largest subarray with equal number of -1s and 1s
def max_sub_array(a):
st=0;
sum=a[0]
end=0
i=1;
n=len(a)
while(i<n):
sum += a[i]
if(sum == 0):
end=i;
i = i + 1
if(i==n and sum != 0) :
end = n
if(sum < 0):
st = st – sum
else:
st = st + sum
print "Input array "+str(a)
print "largest sub array with equal number of -1 and 1 start with =" + str(st) +"end with =" + str(end)
print "largest sub array"+str(a[st:end+1])
a=[-1,1,1,1,-1,-1,1,-1,1,1,1]
max_sub_array(a)
b=[-1,-1,-1,1,1]
max_sub_array(b)
c=[1,1,1,-1]
max_sub_array(c)
#include <iostream>
using namespace std;
int main()
{
int arr[] = {1, 0, 1, 1, 1, 0, 0,0,1};
int length,i;
length=(sizeof(arr)/sizeof(*arr));
int indexCounter=0;
int sum=0;
for(i=0;i<length;i++)
{
if(arr[i]==1)
sum++;
else if(arr[i]==0)
sum–;
if(sum==0)
{
indexCounter=i+1;
}
}
cout<<"1 to "<<indexCounter;
return 0;
}
Best solution
TC =o(n); space =o(n)
1- create hash table.
2-for each element before storing in hash check if it is present in hash table then count_0++ or count_1++.
3- check if (count_0==count_1)
max = count_0;
flag=1;
4- try it for all elements
5-return max
6- start index= 0 and last index = max*2.
meri book de ja bhai fir coding kar jam ke…
O(n) method that is really easy to understand:
Imagine you had a line chart. Every time there is a 1, you go one unit forward with a slope of 1. Every time there is a zero, you go one unit forward with a slope of -1. Now, any horizontal line you draw that crosses two points is a possible solution. So it is O(n) to make the chart, and O(1) to find the largest of the solutions.
To actually implement this, just use a counter, and check for two points where the counter is equal.
This is far better than the O(n^2) solution.
Actually it is working with your example. The solution is a dynamic programming.
In each step he uses the element for the set or not (the main loop)
public class MaxSizesubarray {
/**
* @param args
*/
public static void main(String[] args) {
MaxSizesubarray d = new MaxSizesubarray();
d.maxSubArrya(new int[]{1, -1, 1, 1, 1, -1, -1,-1,1});
}
public void maxSubArrya(int[] array) {
int maxSize = -1;
int i = 0;
int sum = -1;
int startingPoint=0;
for (i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j=j+2) {
sum = array[i] + sumSubArray(array, j, i);
if (sum == 0) {
if (maxSize < j) {
maxSize = j;
startingPoint =i;
}
}
}
}
System.out.println(startingPoint +" "+ maxSize);
}
public int sumSubArray(int[] a, int j, int i) {
int totalSunArraySum = 0;
while (j > i) {
totalSunArraySum = totalSunArraySum + a[j];
j–;
}
return totalSunArraySum;
}
}
#include
int call(int[],int,int);
int i;
int main(void) {
int a[10],n;
scanf(“%d”,&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
call(a,0,n-1);
return 0;
}
int call(int a[],int i,int j)
{int k;
int count1,count0;
count1=count0=0;
for(k=i;k<=j;k++)
{if(a[k]==0)
count0++;
else
if(a[k]==1)
count1++;
}
if(count1==count0)
{printf(" i & j%d %d",i,j);
return 0;
}
call(a,i,j-1);
call(a,i+1,j);
}
int main()
{
char arr[500] = “”;
char subStr[500] = “”;
int cnt = 0;
int cntIn = 0;
int sum = 0;
int maxLen = 0;
printf(“Please Enter the values\n”);
gets(arr);
while(arr[cnt])
{
cntIn = cnt;
sum = 0;
while(arr[cntIn])
{
sum += ((arr[cntIn] – 48) ? -1 : 1) ;
if(!sum && maxLen < (cntIn – cnt))
{
maxLen = cntIn – cnt;
strncpy(subStr, arr + cnt, cntIn – cnt + 1);
subStr[cntIn - cnt + 1] = '';
}
cntIn++;
}
cnt++;
}
if(maxLen)
{
printf("The biggest sub str is %s\n", subStr);
}
return 0;
}
try with giving all the possible ways
subStr[cntIn - cnt + 1] = 0;
#include
#include
void main()
{
int a,c,b[100],i,n,counta=0,countc=0;
clrscr();
printf(“write the values of total elements”);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
a=1;
c=0;
for(i=1;icountc)
{
for(i=1;i<=countc;i++)
{
printf("1,0,");
}
}
else
{
for(i=1;i<=counta;i++)
{
printf("1,0,");
}
}
getch();
}
String findLargestSubArray(int arr[], int n) {
int sum = 0;
int maxsize = -1, fromIndex = 0, endIndex = arr.length, reserveMaxsize = 0, reserveFromIndex =0;
int maxReserveEndIndex = 0;
// Pick a starting point as i
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0)
sum = -1;
else
sum = 1;
for (int j = i + 1; j < n; j++) {
if (arr[j] == 0)
sum += -1;
else
sum += 1;
if (sum == 0) {
endIndex = j;
maxsize = j -i +1;
fromIndex=i;
}
}
if(reserveMaxsize < maxsize){
reserveMaxsize = maxsize ;
reserveFromIndex = fromIndex;
maxReserveEndIndex = endIndex;
}
}
return "max Size…"+reserveMaxsize +" fromIndex… "+reserveFromIndex+ " endIndex…" + maxReserveEndIndex;
}
#include
using namespace std;
void processFromFront(int arr[], int size, int& lenF, int& startF, int& endF)
{
int aggArr[size][2];
for(int i=0;i<size;i++)
{
aggArr[i][0] = 0;
aggArr[i][1] = 0;
}
if(arr[0])
aggArr[0][1]++;
else
aggArr[0][0]++;
for(int i=1;i=0;i–)
{
if(!endF && aggArr[i][0] == aggArr[i][1])
{
lenF = 2*aggArr[i][1];
endF = i;
startF = lenF-endF-1;
break;
}
}
}
void processFromEnd(int arr[], int size, int& lenE, int& startE, int& endE)
{
int aggArr[size][2];
for(int i=size-1;i>=0;i–)
{
aggArr[i][0] = 0;
aggArr[i][1] = 0;
}
if(arr[size-1])
aggArr[size-1][1]++;
else
aggArr[size-1][0]++;
for(int i=size-2;i>=0;i–)
{
if(arr[i])
{
aggArr[i][1] = aggArr[i+1][1]+1;
aggArr[i][0] = aggArr[i+1][0];
}
else
{
aggArr[i][0] = aggArr[i+1][0]+1;
aggArr[i][1] = aggArr[i+1][1];
}
}
for(int i=0;i<size;i++)
{
if(!endE && aggArr[i][0] == aggArr[i][1])
{
lenE = 2*aggArr[i][1];
startE = i;
endE = startE+lenE-1;
break;
}
}
}
int main()
{
int arr[] = {1, 1, 1, 0, 0, 0, 1, 1};
int size = sizeof(arr)/sizeof(*arr);
int lenF = 0, startF = 0, endF = 0;
int lenE = 0, startE = 0, endE = 0;
processFromFront(arr, size, lenF, startF, endF);
processFromEnd(arr, size, lenE, startE, endE);
system("PAUSE");
return 0;
}
Time Complexity – O(n)
Space COmplexity – O(n)