3637. Trionic Array I

Easy

Problem 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.

To solve this problem, start with a pointer p at 0 and move it to the right as long as each next element is strictly greater than the current one. If p is still at 0, the first part isn't strictly increasing, so return false.

Next, set a pointer q to p and move it to the right as long as each next element is strictly less than the current one. If q is either still at p, or reaches the end (n - 1), the decreasing segment wasn't found or no space left for the final segment, so return false.

Finally, from q, check that the remaining elements up to the end are strictly increasing. If so, the array is trionic, and return true. Otherwise, return false.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To decide if an array can be split into three specific parts—first strictly increasing, next strictly decreasing, and finally strictly increasing again—we can mimic moving through each phase in order.

We start at the left and look for the longest strictly increasing prefix. This makes sure the first segment exists. Once the increase stops, we check for a strictly decreasing portion. If found, we continue to verify that what's left forms a strictly increasing suffix.

By advancing three times—from increasing to decreasing to increasing—we naturally check all conditions in a single scan. Each change in direction is guided by comparing adjacent elements, quickly revealing if the pattern is possible. This greedy approach is direct and efficient, as it stops and rules out invalid cases early.

Solution Approach

The solution uses a single pass with pointer variables to segment the array according to the required pattern.

First Increasing Segment: Initialize an index p at 0. Increment p as long as nums[p] < nums[p + 1] and p < n - 2. This finds the longest strictly increasing prefix. If p is still at 0, there is no initial increase, so return False.
Middle Decreasing Segment: Set another index q to p. Increment q as long as nums[q] > nums[q + 1] and q < n - 1. This finds the strictly decreasing segment coming after the increasing part. If q == p (no decreasing segment) or q == n - 1 (array ends, so no place for final increase), return False.
Final Increasing Segment: Continue incrementing q as long as nums[q] < nums[q + 1] and q < n - 1 to verify the last segment is strictly increasing up to the end. If q reaches n - 1, the pattern holds and the array is trionic.

This method uses pointers and simple comparisons, so no extra data structures are needed. The process guarantees that every segment is non-empty and strictly follows the required order. The overall complexity is O(n), since each index is processed at most once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the array nums = [1, 4, 3, 2, 5, 7] as an example.

Step 1: Find the first strictly increasing segment.

Start with p = 0.
Compare nums[0] = 1 and nums[1] = 4. Since 1 < 4, increment p to 1.
Next, compare nums[1] = 4 and nums[2] = 3. Since 4 > 3, stop. Now, p = 1.
Since p > 0, the first segment exists.

Step 2: Find the strictly decreasing segment.

Start with q = p = 1.
Compare nums[1] = 4 and nums[2] = 3. Since 4 > 3, increment q to 2.
Compare nums[2] = 3 and nums[3] = 2. Since 3 > 2, increment q to 3.
Compare nums[3] = 2 and nums[4] = 5. Since 2 < 5, the decreasing segment ends. Now, q = 3.
Since q != p and q < n - 1, the second segment exists.

Step 3: Check the last strictly increasing segment.

From q = 3, compare nums[3] = 2 and nums[4] = 5. Since 2 < 5, increment q to 4.
Compare nums[4] = 5 and nums[5] = 7. Since 5 < 7, increment q to 5.
Now, q = n - 1 = 5, and we've reached the end with a strictly increasing segment.

Conclusion: All three required segments are found, so the array is trionic. The function should return True.

Solution Implementation

1from typing import List
2
3class Solution:
4    def isTrionic(self, nums: List[int]) -> bool:
5        n = len(nums)
6        peak = 0
7
8        # Find strictly increasing sequence
9        while peak < n - 2 and nums[peak] < nums[peak + 1]:
10            peak += 1
11
12        # The increasing part must have at least one element
13        if peak == 0:
14            return False
15
16        valley = peak
17
18        # Find strictly decreasing sequence after the increase
19        while valley < n - 1 and nums[valley] > nums[valley + 1]:
20            valley += 1
21
22        # The decreasing part must have at least one element and not be at the end
23        if valley == peak or valley == n - 1:
24            return False
25
26        # Find strictly increasing sequence after the decrease
27        while valley < n - 1 and nums[valley] < nums[valley + 1]:
28            valley += 1
29
30        # If we reach the end, the array is trionic
31        return valley == n - 1
32

1class Solution {
2    public boolean isTrionic(int[] nums) {
3        int n = nums.length;
4        int i = 0;
5
6        // Step 1: Find the end of the first increasing sequence
7        while (i < n - 2 && nums[i] < nums[i + 1]) {
8            i++;
9        }
10        // The increasing part must have at least one element
11        if (i == 0) {
12            return false;
13        }
14
15        int peak = i;
16
17        // Step 2: Find the end of the following decreasing sequence
18        while (i < n - 1 && nums[i] > nums[i + 1]) {
19            i++;
20        }
21        // There must be at least one decreasing movement, and cannot end here
22        if (i == peak || i == n - 1) {
23            return false;
24        }
25
26        // Step 3: Find the final increasing sequence
27        while (i < n - 1 && nums[i] < nums[i + 1]) {
28            i++;
29        }
30        // The array is trionic if we reached the end
31        return i == n - 1;
32    }
33}
34

1class Solution {
2public:
3    bool isTrionic(std::vector<int>& nums) {
4        int n = nums.size();
5        int p = 0;
6
7        // Find the strictly increasing part from the beginning
8        while (p < n - 2 && nums[p] < nums[p + 1]) {
9            p++;
10        }
11
12        // There must be at least one increasing element
13        if (p == 0) {
14            return false;
15        }
16
17        int q = p;
18
19        // Find the strictly decreasing part
20        while (q < n - 1 && nums[q] > nums[q + 1]) {
21            q++;
22        }
23
24        // There must be at least one decreasing element
25        // Check: did we decrease at all, and did we reach the end?
26        if (q == p || q == n - 1) {
27            return false;
28        }
29
30        // Check for strictly increasing sequence after the peak
31        while (q < n - 1 && nums[q] < nums[q + 1]) {
32            q++;
33        }
34
35        // If we have reached the last element, the pattern matches
36        return q == n - 1;
37    }
38};
39

1/**
2 * Determines whether the given array of numbers is "trionic".
3 * A "trionic" array first strictly increases, then strictly decreases, then strictly increases again.
4 * The sequence must be at least three elements long.
5 *
6 * @param nums - The array of numbers to check.
7 * @returns true if the array is trionic, false otherwise.
8 */
9function isTrionic(nums: number[]): boolean {
10    const length = nums.length;
11    let i = 0;
12
13    // Step 1: Strictly increasing sequence
14    while (i < length - 2 && nums[i] < nums[i + 1]) {
15        i++;
16    }
17    // Must have at least one increasing step
18    if (i === 0) {
19        return false;
20    }
21
22    let j = i;
23
24    // Step 2: Strictly decreasing sequence
25    while (j < length - 1 && nums[j] > nums[j + 1]) {
26        j++;
27    }
28    // Must have at least one decreasing step
29    // Decrease cannot overlap start or reach the end
30    if (j === i || j === length - 1) {
31        return false;
32    }
33
34    // Step 3: Strictly increasing sequence again
35    while (j < length - 1 && nums[j] < nums[j + 1]) {
36        j++;
37    }
38
39    // All elements must have been used in the pattern
40    return j === length - 1;
41}
42

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input array nums. This is because each of the three while loops increases their pointer variable without overlapping, leading to a total of at most n iterations across all loops.

The space complexity is O(1) since the algorithm only uses a constant amount of extra space for the pointer variables (p, q) and does not use any additional data structures whose size depends on the input.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know