Last Updated: 1 Apr, 2025

Check Array Pattern

Moderate

Asked in company

Solve now

Problem statement

You are given an array 'A' of length 'N' containing integers.

Determine if there exist three indices 'i', 'j', and 'k' such that 0 <= 'i' < 'j' < 'k' < 'N' and 'A[i]' < 'A[k]' < 'A[j]'.

For Example :

Let 'N' = 5, 'A' = [1, 5, 2, 4, 3].
Here, if we take 'i' = 0, 'j' = 1, and 'k' = 3, then 'i' < 'j' < 'k' (0 < 1 < 3) and 'A[i]' < 'A[k]' < 'A[j]' (1 < 4 < 5).
Therefore, the answer is True.

Input Format :

The first line contains an integer 'N', the length of the array 'A'.
The second line contains 'N' integers representing the elements of the array 'A', separated by spaces.

Output Format :

Return True if such indices 'i', 'j', and 'k' exist, otherwise return False.

Note :

You don’t need to print anything. Just implement the given function.

Constraints :

3 <= 'N' <= 10^5
-10^9 <= 'A[i]' <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

We can iterate through all possible triplets of indices ('i', 'j', 'k') such that 0 <= 'i' < 'j' < 'k' < 'N'. For each triplet, we check if the condition 'A[i]' < 'A[k]' < 'A[j]' holds. If we find such a triplet, we can immediately return True. If we iterate through all possible triplets and don't find any that satisfy the condition, we return False.

Algorithm:

Iterate using 'i' from 0 to 'N - 3' :
- Iterate using 'j' from 'i + 1' to 'N - 2' :
  - Iterate using 'k' from 'j + 1' to 'N - 1' :
    - If ( 'A[ i ]' < 'A[ k ]' and 'A[ k ]' < 'A[ j ]' ) :
      - Return True.
Return False.

Solve now

02 Approach

Approach:

We iterate through the array from right to left. For each element 'A[k]', we want to find if there exists a 'j' to its left ('j' < 'k') such that 'A[j]' > 'A[k]', and an 'i' to the left of 'j' ('i' < 'j') such that 'A[i]' < 'A[k]'. We can maintain a stack to store potential 'A[k]' values. We also precompute the minimum value to the left of each index.

Algorithm:

Initialize an empty stack 'stack'.
Create an array 'min_left' of size 'N'.
Initialize 'min_left[0]' to infinity.
Iterate using 'i' from 1 to 'N - 1' :
- Assign the minimum of 'min_left[i - 1]' and 'A[i - 1]' to 'min_left[i]'.
Iterate through the array 'A' from right to left using index 'k' from 'N - 1' down to 1 :
- If ( 'A[k]' <= 'min_left[k]' ) :
  - Continue to the next iteration.
- While ( 'stack' is not empty and the last element of 'stack' <= 'min_left[k]' ) :
  - Pop the last element from 'stack'.
- If ( 'stack' is not empty and the last element of 'stack' < 'A[k]' ) :
  - Return True.
- Push 'A[k]' onto 'stack'.
Return False.

Solve now