સબઅર્રે પર્વતની રૂપે છે કે નહીં તે શોધો  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન બ્લેકરોક સિસ્કો સિટ્રીક્સ ફેક્ટસેટ હનીવેલ ટેસ્લા યાન્ડેક્ષ
અરે ક્વેરી સમસ્યા

સમસ્યા નિવેદન  

સમસ્યા "એક સબઅર્રે પર્વતની રૂપે છે કે નહીં તે શોધો" કહે છે કે તમને એક આપવામાં આવ્યું છે પૂર્ણાંક એરે અને એક શ્રેણી. સમસ્યાનું નિવેદન તે શોધવા માટે પૂછે છે કે આપેલ શ્રેણી વચ્ચે રચાયેલ પેટા-એરે પર્વત સ્વરૂપના સ્વરૂપમાં છે કે નહીં? જો સંખ્યા વધતા ક્રમમાં અથવા ઘટતા ક્રમમાં હોય અથવા પ્રથમ વધતી હોય તો ઓછી થતી હોય તો પર્વત એરે રચાય છે.

ઉદાહરણ  

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (0, 3)
Mountain Form

સમજૂતી

કારણ કે પેટા એરે {3, 4, 5, 6. વધી રહ્યો છે, તેથી તે પર્વત એરેના રૂપમાં છે.

સબઅર્રે પર્વતની રૂપે છે કે નહીં તે શોધોપિન

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (5, 7)
Not a Mountain form

સમજૂતી

કારણ કે સબ એરે {5, 1, 2. ઘટી રહ્યો છે પછી વધી રહ્યો છે. તેથી તે પર્વત એરેના રૂપમાં નથી.

અલ્ગોરિધમ  

  1. બે એરે બનાવો એરેએલ અને એરેઆર મૂળ એરેની લંબાઈ જેટલું જ કદ.
  2. એરેએલનો પ્રથમ તત્વ અને એરેઆરનો છેલ્લો તત્વ પ્રારંભ કરો.
  3. જો વર્તમાન એરે તત્વ પહેલાના તત્વ કરતા વધારે છે.
    1. અપડેટ કરો વધતી સંખ્યા અનુક્રમણિકા પર.
    2. મૂલ્ય વધતી સંખ્યાને એરેમાં સોંપો.
  4. એરેને જમણેથી ડાબી તરફ વળો અને તપાસો કે અગાઉના તત્વ (વર્તમાન તત્વની જમણી બાજુએ તત્વ) કરતા મોટી સંખ્યા છે કે નહીં.
    1. પછી અપડેટ કરો ઘટતા નંબર અનુક્રમણિકા માટે
    2. ઘટતા નંબર પર એરેઆર સોંપો.
  5. દરેક આપેલ ક્વેરી માટે, એરેઆર [ડાબી] એરેલી કરતા વધારે છે [જમણે] સાચું પાછા ફરો, નહીં તો ખોટું પાછા ફરો.
આ પણ જુઓ
એમ રેન્જ ટgગલ ઓપરેશન્સ પછી બાઈનરી એરે

સમજૂતી  

અમે પૂર્ણાંક એરે આપ્યો છે અને એક શ્રેણી ડાબી, જમણી. અમે તે શોધવા માટે પૂછ્યું છે કે આપેલ શ્રેણી સાથે બનેલી સુબર્રે પર્વત એરે હોઈ શકે છે કે નહીં. જો આટલું રચાયેલ સબબ્રે એ પર્વત એરે છે તો આપણે સાચા વળગીશું, નહીં તો ખોટું પાછા ફરો અમે બે એરે જાહેર કરીશું. એક એરેની ડાબી બાજુ માટે છે અને બીજું એરેની જમણી બાજુ માટે છે. પછી અમે આ એરે બનાવીશું જેથી દરેક ક્વેરી સતત જગ્યામાં સમાધાન આપી શકે.

આપણે અનુક્રમે એરેએલ અને એરેરે બનાવેલા એરેના પ્રથમ અને છેલ્લા તત્વની શરૂઆત કરીશું. પછી આપણે એરેની ડાબી બાજુ માટે એરેને પસાર કરીએ છીએ અથવા આપણે ડાબેથી જમણે કહી શકીએ છીએ. હાલની એરે એલિમેન્ટ અગાઉના તત્વ કરતાં ઓછી છે કે નહીં તેની હાલત ચકાસીશું. જો તે સાચું હોવાનું જણાયું છે, તો પછી આપણે સંખ્યાની અનુક્રમણિકામાં વધતી સંખ્યાને અપડેટ કરીશું. અને શરત સાચી છે કે નહીં તે દરેક વખતે વધતી સંખ્યા પર એરેએલનું વર્તમાન તત્ત્વ સોંપો.

આગળનાં પગલામાં આપણે એરેને જમણેથી ડાબે, મૂળભૂત રીતે બીજા છેલ્લા તત્વથી એરેના પ્રથમ તત્વ તરફ જઈશું, અને એરેનું વર્તમાન તત્વ આગલા તત્વ કરતા વધારે છે કે કેમ તે ચકાસીશું. આપણે જમણેથી ડાબેથી પસાર થઈ રહ્યાં હોવાથી, આપણે પહેલાનાં તત્વ સાથે તપાસ કહી શકીએ. જો સ્થિતિ સાચી કે સાચી છે, તો ઘટતું સંખ્યા મૂલ્ય વર્તમાન અનુક્રમણિકામાં બદલાઈ જશે. શરતોને ધ્યાનમાં લીધા વિના ઘટતા સંખ્યામાં એરેને અપડેટ કરો. સાચું પાછા ફરો, જો એરેરે [ડાબી] એરેથી વધારે અથવા તેના બરાબર છે [જમણે], નહીં તો ખોટું પાછા ફરો.

આ પણ જુઓ
પાલિન્ડ્રોમ લિંક્ડ સૂચિ લીટકોડ સોલ્યુશન

કોડ  

સી ++ કોડ શોધવા માટે કે સબઅરેરે પર્વતની રૂપે છે કે નહીં

#include<iostream>

using namespace std;

void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
{
    arrayL[0] = 0;
    int increasingNumber = 0;

    for (int i = 1; i < N; i++)
    {
        if (arr[i] > arr[i - 1])
            increasingNumber = i;
        arrayL[i] = increasingNumber;
    }
    arrayR[N - 1] = N - 1;
    int decreasingNumber = N - 1;

    for (int i = N - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1])
            decreasingNumber = i;
        arrayR[i] = decreasingNumber;
    }
}

bool solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
{
    return (arrayR[Left] >= arrayL[Right]);
}

int main()
{
    int arr[] = {3,4,5,6,1,5,1,2,1};
    int N = sizeof(arr) / sizeof(int);

    int arrayL[N], arrayR[N];
    buildArrays(arr, N, arrayL, arrayR);

    int L = 0;
    int R = 3;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    L = 5;
    R = 7;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    return 0;
}
Mountain form
Not a mountain form

જાવા કોડ શોધવા માટે કે સબઅરેરે પર્વતની રૂપે છે કે નહીં

class MountainArray
{
    static void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
    {
        arrayL[0] = 0;
        int increasingNumber = 0;

        for (int i = 1; i < N; i++)
        {
            if (arr[i] > arr[i - 1])
                increasingNumber = i;
            arrayL[i] = increasingNumber;
        }
        arrayR[N - 1] = N - 1;
        int decreasingNumber = N - 1;

        for (int i = N - 2; i >= 0; i--)
        {
            if (arr[i] > arr[i + 1])
                decreasingNumber = i;
            arrayR[i] = decreasingNumber;
        }
    }
    
    static boolean solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
    {
        return (arrayR[Left] >= arrayL[Right]);
    }

    public static void main(String[] args)
    {
        int arr[] = {3,4,5,6,1,5,1,2,1};
        int N = arr.length;
        int arrayL[] = new int[N];
        int arrayR[] = new int[N];
        buildArrays(arr, N, arrayL, arrayR);
        int L = 0;
        int R = 3;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");

        L = 5;
        R = 7;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");
    }
}
Mountain form
Not a mountain form

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન + ક્યૂ), અમને બંને એરે બનાવવા માટે ઓ (એન) સમય જોઈએ છે. અને એકવાર એરે બનાવવામાં આવે છે. આપણે ઓ (1) માં પ્રશ્નોના જવાબો આપી શકીએ છીએ.

આ પણ જુઓ
મીન સ્ટેક લેટકોડ સોલ્યુશન

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.