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

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.

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3637. Trionic Array I

Description

Solutions

Solution 1: Single Pass

Comments