Check Array Pattern

Moderate

0/80

1 upvote

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

5
1 5 2 4 3

Sample Output 1 :

True

Explanation of sample input 1 :

In the given array A = [1, 5, 2, 4, 3], we can choose i = 0, j = 1, and k = 3.
Here, i < j < k (0 < 1 < 3) and A[i] < A[k] < A[j] (1 < 4 < 5).
Thus, the answer is True.

Sample Input 2 :

4
4 3 2 1

Sample Output 2 :

False

Hint 1

Hint 2

Consider iterating through all possible combinations of indices 'i', 'j', and 'k'.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N^3), where 'N' is the length of the array 'A'.

We have three nested loops, with the outer loop running 'N - 2' times, the middle loop running up to 'N - 1' times, and the inner loop running up to 'N' times in the worst case. Thus the overall time complexity is of the order O(N^3).

Space Complexity

O(1).

We are only using a constant amount of extra space for the loop variables 'i', 'j', and 'k'. Thus, the overall space complexity is of the order O(1).

(100% EXP penalty)

Check Array Pattern

Console