Skip to content

3637. Trionic Array I

Description

You are given an integer array nums of length n.

An array is trionic if there exist indices 0 < p < q < n − 1 such that:

  • nums[0...p] is strictly increasing,
  • nums[p...q] is strictly decreasing,
  • nums[q...n − 1] is strictly increasing.

Return true if nums is trionic, otherwise return false.

 

Example 1:

Input: nums = [1,3,5,4,2,6]

Output: true

Explanation:

Pick p = 2, q = 4:

  • nums[0...2] = [1, 3, 5] is strictly increasing (1 < 3 < 5).
  • nums[2...4] = [5, 4, 2] is strictly decreasing (5 > 4 > 2).
  • nums[4...5] = [2, 6] is strictly increasing (2 < 6).

Example 2:

Input: nums = [2,1,3]

Output: false

Explanation:

There is no way to pick p and q to form the required three segments.

 

Constraints:

  • 3 <= n <= 100
  • -1000 <= nums[i] <= 1000

Solutions

Solution 1: Single Pass

Thinking

A trionic array is a nonempty strict rise, a nonempty strict fall, and another nonempty strict rise. Walking the three segments is simpler than enumerating two turning points.

Pointer \(p\) consumes the first ascent; stopping at the start fails. \(q\) then consumes the descent; no movement or finishing at the end means a missing middle or last segment.

The final ascent must end exactly at \(n-1\). One pass checks existence and strictness of all three parts.

We first define a pointer \(p\), initially \(p = 0\), pointing to the first element of the array. We move \(p\) to the right until we find the first element that doesn't satisfy strict increasing order, i.e., \(nums[p] \geq nums[p + 1]\). If \(p = 0\) at this point, it means the first part of the array doesn't have a strictly increasing section, so we return \(\text{false}\) directly.

Next, we define another pointer \(q\), initially \(q = p\), pointing to the first element of the second part of the array. We move \(q\) to the right until we find the first element that doesn't satisfy strict decreasing order, i.e., \(nums[q] \leq nums[q + 1]\). If \(q = p\) or \(q = n - 1\) at this point, it means the second part of the array doesn't have a strictly decreasing section or there's no third part, so we return \(\text{false}\) directly.

If all the above conditions are satisfied, it means the array is trionic, and we return \(\text{true}\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\), using only constant extra space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isTrionic(self, nums: List[int]) -> bool:
        n = len(nums)
        p = 0
        while p < n - 2 and nums[p] < nums[p + 1]:
            p += 1
        if p == 0:
            return False
        q = p
        while q < n - 1 and nums[q] > nums[q + 1]:
            q += 1
        if q == p or q == n - 1:
            return False
        while q < n - 1 and nums[q] < nums[q + 1]:
            q += 1
        return q == n - 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isTrionic(int[] nums) {
        int n = nums.length;
        int p = 0;
        while (p < n - 2 && nums[p] < nums[p + 1]) {
            p++;
        }
        if (p == 0) {
            return false;
        }
        int q = p;
        while (q < n - 1 && nums[q] > nums[q + 1]) {
            q++;
        }
        if (q == p || q == n - 1) {
            return false;
        }
        while (q < n - 1 && nums[q] < nums[q + 1]) {
            q++;
        }
        return q == n - 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        int n = nums.size();
        int p = 0;
        while (p < n - 2 && nums[p] < nums[p + 1]) {
            p++;
        }
        if (p == 0) {
            return false;
        }
        int q = p;
        while (q < n - 1 && nums[q] > nums[q + 1]) {
            q++;
        }
        if (q == p || q == n - 1) {
            return false;
        }
        while (q < n - 1 && nums[q] < nums[q + 1]) {
            q++;
        }
        return q == n - 1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func isTrionic(nums []int) bool {
    n := len(nums)
    p := 0
    for p < n-2 && nums[p] < nums[p+1] {
        p++
    }
    if p == 0 {
        return false
    }
    q := p
    for q < n-1 && nums[q] > nums[q+1] {
        q++
    }
    if q == p || q == n-1 {
        return false
    }
    for q < n-1 && nums[q] < nums[q+1] {
        q++
    }
    return q == n-1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function isTrionic(nums: number[]): boolean {
    const n = nums.length;
    let p = 0;
    while (p < n - 2 && nums[p] < nums[p + 1]) {
        p++;
    }
    if (p === 0) {
        return false;
    }
    let q = p;
    while (q < n - 1 && nums[q] > nums[q + 1]) {
        q++;
    }
    if (q === p || q === n - 1) {
        return false;
    }
    while (q < n - 1 && nums[q] < nums[q + 1]) {
        q++;
    }
    return q === n - 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn is_trionic(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut p = 0usize;

        while p + 2 < n && nums[p] < nums[p + 1] {
            p += 1;
        }
        if p == 0 {
            return false;
        }

        let mut q = p;
        while q + 1 < n && nums[q] > nums[q + 1] {
            q += 1;
        }
        if q == p || q + 1 == n {
            return false;
        }

        while q + 1 < n && nums[q] < nums[q + 1] {
            q += 1;
        }

        q + 1 == n
    }
}

Comments