పరస్పర మూలకాలతో అతిపెద్ద సబ్‌రే యొక్క పొడవు


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ బ్లూమ్బెర్గ్ సిస్కో కారత్ మోనోటైప్ సొల్యూషన్స్ Paytm PayU పబ్లిసిస్ సపియంట్ SAP లాబ్స్
అర్రే హాష్

“పరస్పర మూలకాలతో అతిపెద్ద సబ్‌రే యొక్క పొడవు” అనే సమస్య మీకు ఇవ్వబడింది పూర్ణ సంఖ్య అమరిక. సమస్యాత్మక స్టేట్మెంట్ యొక్క పొడవైన వరుస ఉప-శ్రేణి యొక్క పొడవును తెలుసుకోవడానికి అడుగుతుంది, వీటిలో మూలకాలను ఒక క్రమంలో అమర్చవచ్చు (నిరంతరాయంగా, ఆరోహణ లేదా అవరోహణ). శ్రేణిలోని సంఖ్యలు చాలాసార్లు సంభవించవచ్చు.

ఉదాహరణ

పరస్పర మూలకాలతో అతిపెద్ద సబ్‌రే యొక్క పొడవు

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

వివరణ

0 వ సూచిక నుండి 3 వ సూచిక వరకు ప్రారంభమయ్యే సంఖ్య 10, 12, 13, 11 సంఖ్యలను కలిగి ఉంటుంది, వీటిని 10, 11, 12, 13 పద్ధతిలో అమర్చవచ్చు, వీటిలో పొడవు 4 అవుతుంది.

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

వివరణ

1 వ సూచిక నుండి 3 వ సూచిక వరకు ప్రారంభమయ్యే సంఖ్య 1, 3, 2 సంఖ్యలను కలిగి ఉంటుంది, వీటిని 1, 2, 3 పద్ధతిలో అమర్చవచ్చు, వీటిలో పొడవు 3 అవుతుంది.

అల్గారిథం

  1. సెట్ గరిష్ట పొడవు 1 కు.
  2. లూప్ తెరవండి, i = 0, నేను <l -1,
    1. ప్రకటించండి a సెట్ మరియు సెట్లో arr [i] ను జోడించండి.
    2. యొక్క విలువను సెట్ చేయండి మాక్స్లెన్ మరియు మిల్లెన్ to arr [i].
    3. J = i + 1 నుండి ప్రారంభించి, j <l,
      1. సెట్‌లో అర్ [j] విలువ ఉందో లేదో తనిఖీ చేయండి,
        1. నిజమైతే, విచ్ఛిన్నం.
        2. లేకపోతే,
          1. సెట్‌లో arr [j] ని జోడించండి.
          2. మిల్లెన్ మరియు అర్ర్ [j] మధ్య కనిష్టాన్ని కనుగొని మిల్లెన్‌లో నిల్వ చేయండి.
          3. మాక్స్లెన్ మరియు అర్ర్ [j] ల మధ్య గరిష్టాన్ని కనుగొని దానిని మాక్స్లెన్‌లో నిల్వ చేయండి.
          4. మాక్స్లెన్- min = = j - i అని తనిఖీ చేయండి
            1. నిజమైతే, గరిష్ట పొడవు మరియు మాక్స్-మిల్లెన్ +1 మధ్య గరిష్టాన్ని కనుగొని, గరిష్ట పొడవుకు నిల్వ చేయండి.
  3. గరిష్ట పొడవును తిరిగి ఇవ్వండి.

వివరణ

క్రమం లో అమర్చగలిగే కొన్ని సంఖ్యలను కలిగి ఉన్న పొడవైన వరుస ఉప-శ్రేణి యొక్క పొడవును తెలుసుకోవడానికి మాకు ఒక ప్రశ్న ఇవ్వబడింది. ఇచ్చిన శ్రేణికి నకిలీ సంఖ్యలు ఉన్న సందర్భం ఉండవచ్చు. మేము ఆ కేసును కూడా నిర్వహించాలి. పరిష్కారం పొందడానికి, మేము a ని ఉపయోగిస్తాము సెట్ మరియు నకిలీ మూలకాలను జాగ్రత్తగా చూసుకునే సమూహ లూప్.

ఒక ఉదాహరణను పరిశీలిద్దాం:

ఉదాహరణ

అర్ [] = {10, 12, 13, 11, 8, 10}

మేము ఒక లూప్ తెరిచిన తర్వాత ఒక సెట్‌ను ఉపయోగిస్తాము మరియు ఒక సమయంలో సంఖ్యను జోడించి, మాక్స్లెన్ మరియు మిల్లెన్ యొక్క విలువను అర్ [i] కు సెట్ చేస్తాము. ప్రస్తుత మూలకం కంటే ఒక మూలకం నుండి ప్రారంభమయ్యే సమూహ లూప్‌ను తెరవండి, ఎందుకంటే మేము ఇప్పటికే ప్రస్తుత మూలకాన్ని సెట్‌లోకి చేర్చాము. సెట్ అర్ [j] విలువను కలిగి ఉందో లేదో తనిఖీ చేయండి, మూలకం దొరికితే, విచ్ఛిన్నం. లేకపోతే అర్ర్ [j] యొక్క విలువను సెట్‌లోకి చొప్పించండి మరియు మాక్స్లెన్ మరియు అర్ర్ [j] ల మధ్య గరిష్టాన్ని కనుగొనండి మరియు మిల్లెన్ మరియు అర్ర్ [j] ల మధ్య కనిష్టాన్ని కనుగొని దానిని వరుసగా మాక్స్లెన్ మరియు మిల్లెన్‌లో నిల్వ చేయండి. మాక్స్లెన్-మిన్ జికి సమానంగా ఉందో లేదో తనిఖీ చేసి, ఆపై గరిష్ట పొడవు విలువను నవీకరించండి.

maxLength = 1.

i = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, మైసెట్ 12 కలిగి ఉంటే, అది తప్పు,

కాబట్టి మైసెట్‌లోకి 12 చొప్పించండి మరియు గరిష్టంగా 12 మరియు 10 మరియు కనిష్టాన్ని కనుగొని 12 ను మాక్స్‌లెన్‌గా మరియు 10 మిల్లెన్‌లో నిల్వ చేయండి మరియు మాక్స్లెన్-మిల్లెన్ j - i కి సమానంగా ఉందో లేదో తనిఖీ చేయండి, కానీ ఇది తప్పు.

j = 2, మైసెట్ 13 కలిగి ఉంటే, అది తప్పు,

కాబట్టి 13 ను మైసెట్‌లోకి చొప్పించండి మరియు గరిష్టంగా 13 మరియు 12 లను కనుగొని 13 ని మాక్స్‌లెన్‌గా మరియు 10 ని మిల్లెన్‌గా నిల్వ చేయండి మరియు మాక్స్లెన్-మిల్లెన్ j కి సమానంగా ఉందో లేదో తనిఖీ చేయండి - నేను అబద్ధం.

j = 3, మైసెట్ 11 కలిగి ఉంటే, అది తప్పు,

కాబట్టి 11 ను మైసెట్‌లోకి చొప్పించి, గరిష్టంగా 11 మరియు 10 లను కనుగొని 13 ని మాక్స్‌లెన్‌గా మరియు 10 ని మిల్లెన్‌లో నిల్వ చేసి, మాక్స్లెన్-మిల్లెన్ j కి సమానంగా ఉందో లేదో తనిఖీ చేయండి - నేను ఇప్పుడు నిజం ఎందుకంటే 13-10 3-0కి సమానం. కాబట్టి గరిష్ట పొడవు మరియు మాక్స్లెన్-మిల్లెన్ + 1 గరిష్టంగా (1, 13-10 + 1) కనుగొనడం ద్వారా గరిష్ట పొడవును నవీకరించండి మరియు ఇది 4 అని కనుగొనబడింది మరియు 4 గరిష్ట పొడవులో నిల్వ చేయబడుతుంది మరియు ఇది శ్రేణిని దాటుతూ ఉంటుంది ఇది తరువాతి ఉప-శ్రేణి కంటే ఎక్కువ పొడవును కనుగొనే వరకు సెట్ చేయండి.

అవుట్పుట్: 4

కోడ్

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

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

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

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

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

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

పై2) (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.

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

పై) (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.