0s మరియు 1s సమాన సంఖ్యలో అతిపెద్ద సబ్రే


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ Coursera గ్రేఆరెంజ్ MakeMyTrip మోర్గాన్ స్టాన్లీ Paytm Synopsys టైమ్స్ ఇంటర్నెట్
అర్రే హాష్

మీకు పూర్ణాంకాల శ్రేణి ఇవ్వబడుతుంది. ఇన్పుట్ శ్రేణిలో పూర్ణాంకాలు 0 మరియు 1 మాత్రమే. సమస్య స్టేట్మెంట్ 0 సె మరియు 1 సె సమాన గణనను కలిగి ఉన్న అతిపెద్ద ఉప-శ్రేణిని తెలుసుకోవడానికి అడుగుతుంది.

ఉదాహరణ

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

వివరణ

శ్రేణి స్థానం 0 నుండి 5 వరకు 0 సె మరియు 1 సె సమాన సంఖ్య లేదు

0 సె లెక్కింపు 3

1 సె లెక్కింపు ⇒ 3

మరియు ఇది 0 సె మరియు 1 సె సమానమైన అతిపెద్ద ఉప-శ్రేణి.

సమాన సంఖ్య 0 సె మరియు 1 సెలతో అతిపెద్ద సబ్‌రేను కనుగొనడానికి అల్గోరిథం

  1. ప్రకటించండి a హాష్ మ్యాప్.
  2. సెట్ మొత్తం, గరిష్ట పొడవు, startIndex నుండి 0 మరియు endIndex నుండి -1 వరకు.
  3. శ్రేణిని దాటి, శ్రేణి యొక్క ప్రతి మూలకాన్ని 1 కి సమానంగా ఉంటే -0 గా నవీకరించండి.
  4. 0 నుండి n-1 వరకు లూప్‌ను ప్రారంభించండి (n అనేది శ్రేణి యొక్క పొడవు).
    1. Ar [i] యొక్క ప్రతి విలువను మొత్తానికి జోడించండి.
    2. మొత్తం 0 కి సమానంగా ఉందో లేదో తనిఖీ చేయండి, నిజమైతే,
      1. అప్పుడు నవీకరించండి గరిష్ట పొడవు i + 1, మరియు endIndex నేను.
    3. మ్యాప్‌లో + n మొత్తం ఉందో లేదో తనిఖీ చేయండి,
      1. అప్పుడు మ్యాక్స్ నుండి గరిష్ట పొడవు యొక్క విలువను విలువ i - మ్యాప్ (మొత్తం + n) గా అప్‌డేట్ చేయండి మరియు ఇండెక్స్‌ను i గా ముగించండి.
    4. లేకపోతే ఆ మొత్తాన్ని + n మ్యాప్‌లో ఉంచండి.
  5. ప్రింటింగ్ ఎండింగ్ఇండెక్స్ - మాక్స్ లెంగ్త్ + 1 మరియు ఎండింగ్ఇండెక్స్.

వివరణ

శ్రేణి ఇవ్వబడింది మరియు సమాన సంఖ్య 0 సె మరియు 1 సెలతో అతిపెద్ద ఉప-శ్రేణిని కనుగొనమని అడుగుతారు. ఉప-శ్రేణి యొక్క పరిధిని కనుగొనండి, తద్వారా ఇది అన్ని ఉప-శ్రేణుల యొక్క అన్ని పొడవులలో అతిపెద్దదిగా ఉండాలి, ఇది సమాన సంఖ్య 0 సె మరియు 1 సె కలిగి ఉంటుంది. మేము ఉపయోగిస్తాము హాష్ మ్యాప్ నిల్వ చేయడానికి పూర్ణ సంఖ్య దానిలోని విలువలు. హ్యాషింగ్ సమర్థవంతమైన విధానం మరియు మంచి సమయ సంక్లిష్టతను అందిస్తుంది. విలువలను తీసుకోండి మొత్తం, గరిష్ట పొడవు 0 గా మేము దానిని కోడ్‌లో ఏకకాలంలో అప్‌డేట్ చేయబోతున్నాము. మనకు ఎండింగ్ఇండెక్స్ అని పిలువబడే ఒక వేరియబుల్ ఉంటుంది, ఇది శ్రేణి యొక్క చివరి బిందువు యొక్క విలువను కలిగి ఉంటుంది, ఇక్కడ ఉప-శ్రేణి చివరల పరిధి యొక్క గరిష్ట పొడవు ఉండాలి.

శ్రేణి యొక్క విలువ ఏదైనా 0 కి సమానంగా ఉందో లేదో తెలుసుకోవడానికి శ్రేణిని దాటండి, అప్పుడు మేము దానిని -1 గా గుర్తించాము మరియు దానిలో 1 ని కలిగి ఉన్న శ్రేణి విలువను వదిలివేయండి. ఎందుకంటే ఇక్కడ మనం అసలు పరిధిని కనుగొనడం లేదు. తర్కం అంటే సున్నాల సంఖ్యను మరియు పొడవు పరిధిని అర్ధం. కాబట్టి మనం 0 ను -1 గా గుర్తించాము మరియు శ్రేణిలో విలువలను జోడించినప్పుడు. మేము మొత్తాన్ని 0 గా కనుగొంటే, దీని అర్థం మనం ఒక జత సమానమైన మరియు సున్నాలను కనుగొన్నాము, ఎందుకంటే ప్రతి -1 మరియు 1 0 ను మొత్తంగా 0 నుండి 1 గా గుర్తించినందున, కాబట్టి మనం దానిని లెక్కించవచ్చు.

మేము ఒక శ్రేణిలోని ప్రతి విలువను సంక్షిప్తీకరించడానికి వెళ్తున్నాము మరియు అది 0 కి సమానంగా ఉందో లేదో కనుగొనండి, సమానంగా ఉంటే శ్రేణి యొక్క గరిష్ట పొడవును మరియు శ్రేణి యొక్క ముగింపు ఇండెక్స్‌ను నవీకరించండి. ఇది ఇప్పటికే లేనట్లయితే మేము మొత్తం + n ను మ్యాప్‌లో ఉంచబోతున్నాము, మరియు అది ఉనికిలో ఉంటే కొన్ని షరతులను తనిఖీ చేసి, గరిష్ట పొడవు మరియు ఎండింగ్ఇండెక్స్ విలువను నవీకరించండి. ఎండింగ్ఇండెక్స్ - గరిష్ట పొడవు + 1 ను శ్రేణి యొక్క ప్రారంభ బిందువుగా మరియు ఎండింగ్ఇండెక్స్ పరిధి యొక్క ముగింపు బిందువుగా ముద్రించండి.

0s మరియు 1s సమాన సంఖ్యలో అతిపెద్ద సబ్రే

కోడ్

సమాన సంఖ్య 0 సె మరియు 1 సెలతో అతిపెద్ద సబ్‌రేను కనుగొనడానికి సి ++ కోడ్

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

సమాన సంఖ్యలో 0 సె మరియు 1 సెలతో అతిపెద్ద సబ్‌రేను కనుగొనడానికి జావాలో అమలు

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. ఇక్కడ మేము ఈ సమస్యను O (n) లో పరిష్కరించగలము ఎందుకంటే మేము హాష్ మ్యాప్ ను ఉపయోగించాము. ఎందుకంటే హాష్ మ్యాప్ O (1) సమయ సంక్లిష్టతలోని అంశాలను చొప్పించగలదు, తొలగించగలదు లేదా సవరించగలదు.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. చెత్త సందర్భంలో హ్యాష్‌మాప్‌లోకి చేర్చబడే మూలకాల సంఖ్య గరిష్టంగా n ఉంటుంది. ఈ సరళ స్థల సంక్లిష్టత సాధించబడుతుంది.