Wednesday, July 13, 2022
HomeWordPress DevelopmentDiscover 132 Sample from given Array

Discover 132 Sample from given Array


View Dialogue

Enhance Article

Save Article

Like Article

Given an array arr[] of dimension N. The duty is to test if the array has 3 components in indices i, j and ok such that i < j < ok and arr[i] < arr[j] > arr[k] and arr[i] < arr[k].

Examples:

Enter: N = 6, arr[] = {4, 7, 11, 5, 13, 2}
Output: True
Rationalization: [4, 7, 5] suits the situation.

Enter: N = 4, arr[] = {11, 11, 12, 9}
Output: False
Rationalization: No 3 components match the given situation. 

 

Method: The issue could be solved utilizing the next thought:

Traverse the array from N-1 to 0 and test for each ith factor if the best factor on the fitting which is smaller than ith factor is larger than the smallest factor on the left of i then true else false. 

To seek out the best factor smaller than ith factor we will use Subsequent Larger Aspect 

Comply with the steps talked about under to implement the concept:

  • Create a vector small[]. 
  • Traverse the array arr[] and preserve a min worth that’s the smallest worth of arr[0, . . ., i]. 
    • If there isn’t a factor smaller than Arr[i] retailer -1 else retailer min.
  • Initialize an empty stack (say S). Run a loop from N-1 to 0:
    • If stack isn’t empty and high factor in stack <= small[i], then pop the factor;
    • If stack isn’t empty and small[i] < Prime factor in stack < arr[i] then return true.
    • In any other case, push arr[i] into stack.
  • If the situation isn’t glad, return false.

Under is the implementation of the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

bool recreationalSpot(int arr[], int n)

{

    vector<int> small;

  

    

    

    int min1 = arr[0];

    for (int i = 0; i < n; i++) {

        if (min1 >= arr[i]) {

            min1 = arr[i];

  

            

            

            

            small.push_back(-1);

        }

        else {

  

            

            small.push_back(min1);

        }

    }

  

    

    stack<int> s;

  

    

    

    

    for (int i = n - 1; i > 0; i--) {

  

        

        

        whereas (!s.empty() && s.high() <= small[i]) {

            s.pop();

        }

  

        

        

        

        if (!s.empty() && small[i] != -1

            && s.high() < arr[i])

            return true;

        s.push(arr[i]);

    }

  

    return false;

}

  

int predominant()

{

  

    int arr[] = { 4, 7, 11, 5, 13, 2 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    if (recreationalSpot(arr, N)) {

        cout << "True";

    }

    else {

        cout << "False";

    }

    return 0;

}

Time Complexity: O(N).
Auxiliary Area: O(N).

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments