El subarreglo más grande con el mismo número de 0 y 1

Dado un arreglo que contiene solo 0 y 1, encuentre el subarreglo más grande que contenga el mismo número de 0 y 1. La complejidad temporal esperada es O(n). 

Ejemplos: 

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 
(Starting and Ending indexes of output subarray)

Input: arr[] = {1, 1, 1, 1}
Output: No such subarray

Input: arr[] = {0, 0, 1, 1, 0}
Output: 0 to 3 Or 1 to 4

Método 1 : Fuerza bruta.

Enfoque: El enfoque de fuerza bruta en este tipo de preguntas es generar todos los sub-arreglos posibles. Luego, en primer lugar, verifique si el subarreglo tiene el mismo número de 0 y 1 o no. Para facilitar este proceso, tome la suma acumulativa de los subconjuntos tomando 0 como -1 y 1 como está. El punto donde la suma acumulativa = 0 significará que el subarreglo desde el inicio hasta ese punto tiene el mismo número de 0 y 1 . Ahora que este es un subconjunto válido, compare su tamaño con el tamaño máximo de dicho subconjunto encontrado hasta ahora. 

Algoritmo: 

  1. Utilice un puntero inicial que signifique el punto inicial del subarreglo.
  2. Tome una variable sum=0 que tomará la suma acumulada de todos los elementos del subconjunto.
  3. Inicialícelo con el valor 1 si el valor en el punto de inicio = 1 , de lo contrario, inicialícelo con -1 .
  4. Ahora inicie un ciclo interno y comience a tomar la suma acumulada de elementos siguiendo la misma lógica.
  5. Si la suma acumulativa (valor de la suma) = 0 , significa que el subarreglo tiene el mismo número de 0 y 1 .
  6. Ahora compare su tamaño con el tamaño del subconjunto más grande, si es mayor, almacene el primer índice de dicho subconjunto en una variable y actualice el valor del tamaño.
  7. Imprima el subarreglo con el índice inicial y el tamaño devuelto por el algoritmo anterior.

Pseudocódigo: 

Run a loop from i=0 to n-2
  if(arr[i]==1)
  sum=1
  else
  sum=-1
  Run inner loop from j=i+1 to n-1
      sum+=arr[j]
      if(sum==0)
        if(j-i+1>max_size)
           start_index=i
           max_size=j-i+1
Run a loop from i=start_index till max_size-1
print(arr[i])

C++

// A simple C++ program to find the largest
// subarray with equal number of 0s and 1s
#include <bits/stdc++.h>
 
using namespace std;
 
// This function Prints the starting and ending
// indexes of the largest subarray with equal
// number of 0s and 1s. Also returns the size
// of such subarray.
 
int findSubArray(int arr[], int n)
{
    int sum = 0;
    int maxsize = -1, startindex;
 
    // Pick a starting point as i
    for (int i = 0; i < n - 1; i++) {
        sum = (arr[i] == 0) ? -1 : 1;
 
        // Consider all subarrays starting from i
        for (int j = i + 1; j < n; j++) {
            (arr[j] == 0) ? (sum += -1) : (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;
                startindex = i;
            }
        }
    }
    if (maxsize == -1)
        cout << "No such subarray";
    else
        cout << startindex << " to "
             << startindex + maxsize - 1;
 
    return maxsize;
}
 
/* Driver code*/
int main()
{
    int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
 
    findSubArray(arr, size);
    return 0;
}
 
// This code is contributed by rathbhupendra

C

// A simple program to find the largest subarray
// with equal number of 0s and 1s
 
#include <stdio.h>
 
// This function Prints the starting and ending
// indexes of the largest subarray with equal
// number of 0s and 1s. Also returns the size
// of such subarray.
 
int findSubArray(int arr[], int n)
{
    int sum = 0;
    int maxsize = -1, startindex;
 
    // Pick a starting point as i
 
    for (int i = 0; i < n - 1; i++) {
        sum = (arr[i] == 0) ? -1 : 1;
 
        // Consider all subarrays starting from i
 
        for (int j = i + 1; j < n; j++) {
            (arr[j] == 0) ? (sum += -1) : (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;
                startindex = i;
            }
        }
    }
    if (maxsize == -1)
        printf("No such subarray");
    else
        printf("%d to %d", startindex, startindex + maxsize - 1);
 
    return maxsize;
}
 
/* Driver program to test above functions*/
 
int main()
{
    int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
 
    findSubArray(arr, size);
    return 0;
}

Java

class LargestSubArray {
 
    // This function Prints the starting and ending
    // indexes of the largest subarray with equal
    // number of 0s and 1s. Also returns the size
    // of such subarray.
 
    int findSubArray(int arr[], int n)
    {
        int sum = 0;
        int maxsize = -1, startindex = 0;
        int endindex = 0;
 
        // Pick a starting point as i
 
        for (int i = 0; i < n - 1; i++) {
            sum = (arr[i] == 0) ? -1 : 1;
 
            // Consider all subarrays starting from i
 
            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;
                    startindex = i;
                }
            }
        }
        endindex = startindex + maxsize - 1;
        if (maxsize == -1)
            System.out.println("No such subarray");
        else
            System.out.println(startindex + " to " + endindex);
 
        return maxsize;
    }
 
    /* Driver program to test the above functions */
 
    public static void main(String[] args)
    {
        LargestSubArray sub;
        sub = new LargestSubArray();
        int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
        int size = arr.length;
 
        sub.findSubArray(arr, size);
    }
}

Python3

# A simple program to find the largest subarray
# with equal number of 0s and 1s
 
# This function Prints the starting and ending
# indexes of the largest subarray with equal
# number of 0s and 1s. Also returns the size
# of such subarray.
def findSubArray(arr, n):
 
    sum = 0
    maxsize = -1
 
    # Pick a starting point as i
 
    for i in range(0, n-1):
     
        sum = -1 if(arr[i] == 0) else 1
 
        # Consider all subarrays starting from i
 
        for j in range(i + 1, n):
         
            sum = sum + (-1) if (arr[j] == 0) else sum + 1
 
            # If this is a 0 sum subarray, then
            # compare it with maximum size subarray
            # calculated so far
 
            if (sum == 0 and maxsize < j-i + 1):
                 
                maxsize = j - i + 1
                startindex = i
             
         
     
    if (maxsize == -1):
        print("No such subarray");
    else:
        print(startindex, "to", startindex + maxsize-1);
 
    return maxsize
 
# Driver program to test above functions
arr = [1, 0, 0, 1, 0, 1, 1]
size = len(arr)
findSubArray(arr, size)
 
# This code is contributed by Smitha Dinesh Semwal

C#

// A simple program to find the largest subarray
// with equal number of 0s and 1s
using System;
 
class GFG {
 
    // This function Prints the starting and ending
    // indexes of the largest subarray with equal
    // number of 0s and 1s. Also returns the size
    // of such subarray.
 
    static int findSubArray(int[] arr, int n)
    {
        int sum = 0;
        int maxsize = -1, startindex = 0;
        int endindex = 0;
 
        // Pick a starting point as i
        for (int i = 0; i < n - 1; i++) {
            sum = (arr[i] == 0) ? -1 : 1;
 
            // Consider all subarrays starting from i
 
            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;
                    startindex = i;
                }
            }
        }
        endindex = startindex + maxsize - 1;
        if (maxsize == -1)
            Console.WriteLine("No such subarray");
        else
            Console.WriteLine(startindex + " to " + endindex);
 
        return maxsize;
    }
 
    // Driver program
    public static void Main()
    {
 
        int[] arr = { 1, 0, 0, 1, 0, 1, 1 };
        int size = arr.Length;
        findSubArray(arr, size);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// A simple program to find the
// largest subarray with equal
// number of 0s and 1s
 
// This function Prints the starting
// and ending indexes of the largest
// subarray with equal number of 0s
// and 1s. Also returns the size of
// such subarray.
function findSubArray(&$arr, $n)
{
    $sum = 0;
    $maxsize = -1;
 
    // Pick a starting point as i
 
    for ($i = 0; $i < $n - 1; $i++)
    {
        $sum = ($arr[$i] == 0) ? -1 : 1;
 
        // Consider all subarrays
        // starting from i
        for ($j = $i + 1; $j < $n; $j++)
        {
            ($arr[$j] == 0) ?
               ($sum += -1) : ($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;
                $startindex = $i;
            }
        }
    }
    if ($maxsize == -1)
        echo "No such subarray";
    else
        echo $startindex. " to " .
            ($startindex + $maxsize - 1);
 
    return $maxsize;
}
 
// Driver Code
$arr = array(1, 0, 0, 1, 0, 1, 1);
$size = sizeof($arr);
 
findSubArray($arr, $size);
 
// This code is contributed
// by ChitraNayal
?>

Javascript

<script>
     
    // This function Prints the starting and ending
    // indexes of the largest subarray with equal
    // number of 0s and 1s. Also returns the size
    // of such subarray.
    function findSubArray(arr,n)
    {
        let sum = 0;
        let maxsize = -1, startindex = 0;
        let endindex = 0;
        // Pick a starting point as i
        for (let i = 0; i < n - 1; i++)
        {
            sum = (arr[i] == 0) ? -1 : 1;
            // Consider all subarrays starting from i
            for (let 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;
                    startindex = i;
                }
            }
        }
        endindex = startindex + maxsize - 1;
        if (maxsize == -1)
            document.write("No such subarray");
        else
            document.write(startindex + " to " + endindex);
  
        return maxsize;
         
    }
     
    /* Driver program to test the above functions */
    let arr=[1, 0, 0, 1, 0, 1, 1];
    let  size = arr.length;
    findSubArray(arr, size);
     
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

Producción: 

 0 to 5

Análisis de Complejidad: 

  • Complejidad de tiempo: O(n^2). 
    Como todos los subconjuntos posibles se generan utilizando un par de bucles anidados.
  • Espacio Auxiliar: O(1). 
    Como no se utiliza una estructura de datos adicional que ocupe espacio auxiliar.

Método 2: Hashmap .

Enfoque: El concepto de tomar una suma acumulativa, tomar 0 como -1 nos ayudará a optimizar el enfoque. Al tomar la suma acumulativa, hay dos casos en los que puede haber una subarray con el mismo número de 0 y 1. 

  1. Cuando la suma acumulativa = 0 , lo que significa que la subarray desde el índice (0) hasta el índice actual tiene el mismo número de 0 y 1 .
  2. Cuando encontramos un valor de suma acumulativa que ya hemos encontrado antes, lo que significa que la subarray desde el índice anterior + 1 hasta el índice actual tiene el mismo número de 0 y 1, ya que dan una suma acumulativa de 0 .

En pocas palabras, este problema es equivalente a encontrar dos índices i & j en array[] tal que array[i] = array[j] y (ji) sea máximo . Para almacenar la primera aparición de cada valor de suma acumulativa único, usamos un hash_map en el que, si obtenemos ese valor nuevamente, podemos encontrar el tamaño del subconjunto y compararlo con el tamaño máximo encontrado hasta ahora.

Algoritmo:  

  1. Deje que la array de entrada sea arr[] de tamaño n y max_size sea el tamaño de la sub-array de salida.
  2. Cree una array temporal sumleft[] de tamaño n. Almacene la suma de todos los elementos desde arr[0] hasta arr[i] en sumleft[i].
  3. Hay dos casos, el subarreglo de salida puede comenzar desde el índice 0 o puede comenzar desde algún otro índice. Devolveremos el máximo de los valores obtenidos por dos casos.
  4. Para encontrar la subarray de longitud máxima a partir del índice 0, escanee sumleft[] y encuentre la i máxima donde sumleft[i] = 0.
  5. Ahora, necesitamos encontrar el subarreglo donde la suma del subarreglo es 0 y el índice de inicio no es 0. Este problema es equivalente a encontrar dos índices i & j en sumleft[] tal que sumleft[i] = sumleft[j] y ji es máximo . Para resolver esto, creamos una tabla hash con tamaño = max-min+1 donde min es el valor mínimo en sumleft[] y max es el valor máximo en sumleft[]. Hash las ocurrencias más a la izquierda de todos los valores diferentes en sumleft[]. El tamaño del hash se elige como max-min+1 porque puede haber muchos valores diferentes posibles en sumleft[]. Inicialice todos los valores en hash como -1.
  6. Para llenar y usar hash[], recorra sumleft[] de 0 a n-1. Si un valor no está presente en hash[], almacene su índice en hash. Si el valor está presente, calcule la diferencia del índice actual de sumleft[] y el valor previamente almacenado en hash[]. Si esta diferencia es mayor que el tamaño máximo, actualice el tamaño máximo.
  7. Para manejar casos de esquina (todos los 1 y todos los 0), inicializamos maxsize como -1. Si el tamaño máximo sigue siendo -1, imprima que no existe tal subarreglo.

Pseudocódigo: 

int sum_left[n]
Run a loop from i=0 to n-1
  if(arr[i]==0)
  sumleft[i] = sumleft[i-1]+-1
  else
  sumleft[i] = sumleft[i-1]+ 1
        if (sumleft[i] > max)
            max = sumleft[i];


Run a loop from i=0 to n-1
 if (sumleft[i] == 0)
        {
           maxsize = i+1;
           startindex = 0;
        }
 
        // Case 2: fill hash table value. If already
        then use it

        if (hash[sumleft[i]-min] == -1)
            hash[sumleft[i]-min] = i;
        else
        {
            if ((i - hash[sumleft[i]-min]) > maxsize)
            {
                maxsize = i - hash[sumleft[i]-min];
                startindex = hash[sumleft[i]-min] + 1;
            }
        }

return maxsize

C++

// C++ program to find largest subarray with equal number of
// 0's and 1's.
 
#include <bits/stdc++.h>
using namespace std;
 
// Returns largest subarray with equal number of 0s and 1s
 
int maxLen(int arr[], int n)
{
    // Creates an empty hashMap hM
 
    unordered_map<int, int> hM;
 
    int sum = 0; // Initialize sum of elements
    int max_len = 0; // Initialize result
    int ending_index = -1;
 
    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;
 
    // Traverse through the given array
 
    for (int i = 0; i < n; i++) {
        // Add current element to sum
 
        sum += arr[i];
 
        // To handle sum=0 at last index
 
        if (sum == 0) {
            max_len = i + 1;
            ending_index = i;
        }
 
        // If this sum is seen before, then update max_len
        // if required
 
        if (hM.find(sum) != hM.end()) {
            if (max_len < i - hM[sum]) {
                max_len = i - hM[sum];
                ending_index = i;
            }
        }
        else // Else put this sum in hash table
            hM[sum] = i;
    }
 
    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == -1) ? 0 : 1;
 
    printf("%d to %d\n",
           ending_index - max_len + 1, ending_index);
 
    return max_len;
}
 
// Driver method
 
int main()
{
    int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    maxLen(arr, n);
    return 0;
}
 
// This code is contributed by Aditya Goel

C

// A O(n) program to find the largest subarray
// with equal number of 0s and 1s
 
#include <stdio.h>
#include <stdlib.h>
 
// A utility function to get maximum of two
// integers
 
int max(int a, int b) { return a > b ? a : b; }
 
// This function Prints the starting and ending
// indexes of the largest subarray with equal
// number of 0s and 1s. Also returns the size
// of such subarray.
 
int findSubArray(int arr[], int n)
{
    // variables to store result values
 
    int maxsize = -1, startindex;
 
    // Create an auxiliary array sunmleft[].
    // sumleft[i] will be sum of array
    // elements from arr[0] to arr[i]
 
    int sumleft[n];
 
    // For min and max values in sumleft[]
 
    int min, max;
    int i;
 
    // Fill sumleft array and get min and max
    // values in it.  Consider 0 values in arr[]
    // as -1
 
    sumleft[0] = ((arr[0] == 0) ? -1 : 1);
    min = arr[0];
    max = arr[0];
    for (i = 1; i < n; i++) {
        sumleft[i] = sumleft[i - 1]
                     + ((arr[i] == 0) ? -1 : 1);
        if (sumleft[i] < min)
            min = sumleft[i];
        if (sumleft[i] > max)
            max = sumleft[i];
    }
 
    // Now calculate the max value of j - i such
    // that sumleft[i] = sumleft[j]. The idea is
    // to create a hash table to store indexes of all
    // visited values.
    // If you see a value again, that it is a case of
    // sumleft[i] = sumleft[j]. Check if this j-i is
    // more than maxsize.
    // The optimum size of hash will be max-min+1 as
    // these many different values of sumleft[i] are
    // possible. Since we use optimum size, we need
    // to shift all values in sumleft[] by min before
    // using them as an index in hash[].
 
    int hash[max - min + 1];
 
    // Initialize hash table
 
    for (i = 0; i < max - min + 1; i++)
        hash[i] = -1;
 
    for (i = 0; i < n; i++) {
        // Case 1: when the subarray starts from
        // index 0
 
        if (sumleft[i] == 0) {
            maxsize = i + 1;
            startindex = 0;
        }
 
        // Case 2: fill hash table value. If already
        // filled, then use it
 
        if (hash[sumleft[i] - min] == -1)
            hash[sumleft[i] - min] = i;
        else {
            if ((i - hash[sumleft[i] - min]) > maxsize) {
                maxsize = i - hash[sumleft[i] - min];
                startindex = hash[sumleft[i] - min] + 1;
            }
        }
    }
    if (maxsize == -1)
        printf("No such subarray");
    else
        printf("%d to %d", startindex,
               startindex + maxsize - 1);
 
    return maxsize;
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
 
    findSubArray(arr, size);
    return 0;
}

Java

import java.util.HashMap;
 
class LargestSubArray1 {
 
    // Returns largest subarray with
    // equal number of 0s and 1s
 
    int maxLen(int arr[], int n)
    {
        // Creates an empty hashMap hM
 
        HashMap<Integer, Integer> hM
            = new HashMap<Integer, Integer>();
 
        // Initialize sum of elements
        int sum = 0;
 
        // Initialize result
        int max_len = 0;
        int ending_index = -1;
        int start_index = 0;
 
        for (int i = 0; i < n; i++) {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }
 
        // Traverse through the given array
 
        for (int i = 0; i < n; i++) {
            // Add current element to sum
 
            sum += arr[i];
 
            // To handle sum=0 at last index
 
            if (sum == 0) {
                max_len = i + 1;
                ending_index = i;
            }
 
            // If this sum is seen before,
            // then update max_len if required
            if (hM.containsKey(sum)) {
                if (max_len < i - hM.get(sum)) {
                    max_len = i - hM.get(sum);
                    ending_index = i;
                }
            }
            else // Else put this sum in hash table
                hM.put(sum, i);
        }
 
        for (int i = 0; i < n; i++) {
            arr[i] = (arr[i] == -1) ? 0 : 1;
        }
 
        int end = ending_index - max_len + 1;
        System.out.println(end + " to " + ending_index);
 
        return max_len;
    }
 
    /* Driver program to test the above functions */
    public static void main(String[] args)
    {
        LargestSubArray1 sub = new LargestSubArray1();
        int arr[] = { 1, 0, 0, 1, 0, 1, 1 };
        int n = arr.length;
 
        sub.maxLen(arr, n);
    }
}
 
// This code has been by Mayank Jaiswal(mayank_24)

Python3

# Python 3 program to find largest
# subarray with equal number of
# 0's and 1's.
 
# Returns largest subarray with
# equal number of 0s and 1s
def maxLen(arr, n):
 
    # NOTE: Dictionary in python in
    # implemented as Hash Maps.
    # Create an empty hash map (dictionary)
    hash_map = {} 
    curr_sum = 0
    max_len = 0
    ending_index = -1
 
    for i in range (0, n):
        if(arr[i] == 0):
            arr[i] = -1
        else:
            arr[i] = 1
 
    # Traverse through the given array
    for i in range (0, n):
     
        # Add current element to sum
        curr_sum = curr_sum + arr[i]
 
        # To handle sum = 0 at last index
        if (curr_sum == 0):
            max_len = i + 1
            ending_index = i
 
        # If this sum is seen before,
        if curr_sum in hash_map:
             
            # If max_len is smaller than new subarray
            # Update max_len and ending_index
            if max_len < i - hash_map[curr_sum]:
                max_len = i - hash_map[curr_sum]
                ending_index = i
        else:
 
            # else put this sum in dictionary
            hash_map[curr_sum] = i 
         
    for i in range (0, n):
        if(arr[i] == -1):
            arr[i] = 0
        else:
            arr[i] = 1
             
    print (ending_index - max_len + 1, end =" ")
    print ("to", end = " ")
    print (ending_index)
 
    return max_len
 
# Driver Code
arr = [1, 0, 0, 1, 0, 1, 1]
n = len(arr) 
 
maxLen(arr, n)
     
# This code is contributed
# by Tarun Garg

C#

// C# program to find the largest subarray
// with equal number of 0s and 1s
using System;
using System.Collections.Generic;
 
class LargestSubArray1 {
 
    // Returns largest subarray with
    // equal number of 0s and 1s
    public virtual int maxLen(int[] arr, int n)
    {
 
        // Creates an empty Dictionary hM
        Dictionary<int,
                   int>
            hM = new Dictionary<int,
                                int>();
 
        int sum = 0; // Initialize sum of elements
        int max_len = 0; // Initialize result
        int ending_index = -1;
        int start_index = 0;
 
        for (int i = 0; i < n; i++) {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }
 
        // Traverse through the given array
        for (int i = 0; i < n; i++) {
            // Add current element to sum
            sum += arr[i];
 
            // To handle sum=0 at last index
            if (sum == 0) {
                max_len = i + 1;
                ending_index = i;
            }
 
            // If this sum is seen before,
            // then update max_len
            // if required
            if (hM.ContainsKey(sum)) {
                if (max_len < i - hM[sum]) {
                    max_len = i - hM[sum];
                    ending_index = i;
                }
            }
 
            else // Else put this sum in hash table
            {
                hM[sum] = i;
            }
        }
 
        for (int i = 0; i < n; i++) {
            arr[i] = (arr[i] == -1) ? 0 : 1;
        }
 
        int end = ending_index - max_len + 1;
        Console.WriteLine(end + " to " + ending_index);
 
        return max_len;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
 
        LargestSubArray1 sub = new LargestSubArray1();
        int[] arr = new int[] {
            1,
            0,
            0,
            1,
            0,
            1,
            1
        };
 
        int n = arr.Length;
        sub.maxLen(arr, n);
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// Javascript program to find largest
// subarray with equal number of
// 0's and 1's.
 
// Returns largest subarray with equal
// number of 0s and 1s
function maxLen(arr, n)
{
     
    // Creates an empty hashMap hM
    let hM = new Map();
     
    // Initialize sum of elements
    let sum = 0;
     
    // Initialize result
    let max_len = 0;
    let ending_index = -1;
 
    for(let i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;
 
    // Traverse through the given array
    for(let i = 0; i < n; i++)
    {
         
        // Add current element to sum
        sum += arr[i];
 
        // To handle sum=0 at last index
        if (sum == 0)
        {
            max_len = i + 1;
            ending_index = i;
        }
 
        // If this sum is seen before, then
        // update max_len if required
        if (hM.has(sum))
        {
            if (max_len < i - hM[sum])
            {
                max_len = i - hM[sum];
                ending_index = i;
            }
        }
         
        // Else put this sum in hash table
        else
            hM[sum] = i;
    }
 
    for(let i = 0; i < n; i++)
        arr[i] = (arr[i] == -1) ? 0 : 1;
 
    document.write(ending_index - max_len + 1 +
                   " to " + ending_index);
 
    return max_len;
}
 
// Driver code
let arr = [ 1, 0, 0, 1, 0, 1, 1 ];
let n = arr.length;
 
maxLen(arr, n);
 
// This code is contributed by gfgking
 
</script>

Producción: 

0 to 5

Análisis de Complejidad: 

  • Complejidad temporal: O(n). 
    Como la array dada se recorre una sola vez.
  • Espacio Auxiliar: O(n). 
    Como se ha utilizado hash_map , que ocupa espacio adicional.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *