Problem Description

You are given an integer array nums of length n.

An array is called trionic if it can be divided into three parts with the following properties:

• The first part nums[0...p] is strictly increasing
• The second part nums[p...q] is strictly decreasing
• The third part nums[q...n-1] is strictly increasing

where p and q are indices satisfying 0 < p < q < n - 1.

Your task is to determine if the given array is trionic. Return true if nums is trionic, otherwise return false.

Key requirements:

• The array must have at least 4 elements (to accommodate three non-empty parts with the index constraints)
• Each part must be strictly monotonic (no equal consecutive elements allowed)
• The transition points p and q must exist within the valid range
• The first part ends at index p, the second part starts at p and ends at q, and the third part starts at q and goes to the end

For example:

• [1, 3, 2, 4] would be trionic with p=1 and q=2: increasing [1,3], decreasing [3,2], increasing [2,4]
• [1, 2, 3, 4] would not be trionic as there's no decreasing section
• [4, 3, 2, 1] would not be trionic as there's no initial increasing section or final increasing section

Intuition

The key insight is that a trionic array has a very specific shape: it goes up, then down, then up again. We can think of it like a valley between two hills. To verify this pattern, we need to find the two transition points where the direction changes.

Since we need to check for strict monotonicity in each section, we can traverse the array once and identify where these transitions occur. The natural approach is to:

1. Start from the beginning and keep moving forward while the array is strictly increasing. This gives us the peak of the first hill (point p).

2. From that peak, continue moving forward while the array is strictly decreasing. This takes us to the bottom of the valley (point q).

3. From the valley bottom, check if the remaining elements form a strictly increasing sequence until the end.

The elegance of this approach lies in its simplicity - we're essentially following the "shape" of the array. If at any point we can't find the expected pattern (like if there's no initial increase, or no decrease after the first peak, or no final increase), we know the array isn't trionic.

We also need to be careful about edge cases:

• If p = 0, it means we never found an increasing part at the start
• If q = p, it means we never found a decreasing part after the first peak
• If q = n - 1, it means there's no room for a final increasing part
• If we can't reach the end with the final increasing check, the third part isn't fully increasing

This linear scan approach naturally validates all the constraints while finding the transition points in a single pass through the array.

Solution Approach

The implementation uses a single-pass algorithm with pointer manipulation to identify the three required sections of a trionic array.

Step 1: Find the end of the strictly increasing section

We initialize a pointer p = 0 and move it rightward as long as nums[p] < nums[p + 1]. This loop continues while we have a strictly increasing sequence. The loop stops when we either reach the position n - 2 (to avoid index out of bounds) or find an element that doesn't satisfy the strict increase condition.

while p < n - 2 and nums[p] < nums[p + 1]:
    p += 1

After this loop, p points to the last element of the first increasing section. We check if p = 0, which would mean no increasing section was found at the beginning, and return false immediately.

Step 2: Find the end of the strictly decreasing section

We initialize q = p (starting from where the increasing section ended) and move it rightward as long as nums[q] > nums[q + 1]. This identifies the strictly decreasing section.

while q < n - 1 and nums[q] > nums[q + 1]:
    q += 1

After this loop, q points to the last element of the decreasing section. We check two conditions:

• If q = p: No decreasing section was found
• If q = n - 1: The decreasing section extends to the end, leaving no room for the third increasing section

If either condition is true, we return false.

Step 3: Verify the final strictly increasing section

Starting from the current position of q, we check if the remaining elements form a strictly increasing sequence:

while q < n - 1 and nums[q] < nums[q + 1]:
    q += 1

Step 4: Final validation

If q = n - 1 after the third loop, it means we successfully traversed the entire array following the trionic pattern (increase → decrease → increase). We return true. Otherwise, the third section didn't extend to the end of the array as required, so we return false.

The time complexity is O(n) since we traverse the array at most once, and the space complexity is O(1) as we only use two pointers.

Example Walkthrough

Let's walk through the algorithm with the array nums = [2, 5, 3, 1, 4, 6].

Initial Setup:

• Array length n = 6
• Initialize pointer p = 0

Step 1: Find the first increasing section

• Start at p = 0: Check if nums[0] < nums[1] → 2 < 5 ✓, move p to 1
• At p = 1: Check if nums[1] < nums[2] → 5 < 3 ✗, stop
• First increasing section: [2, 5] (indices 0 to 1)
• p = 1 (last index of increasing section)

Step 2: Find the decreasing section

• Initialize q = p = 1
• At q = 1: Check if nums[1] > nums[2] → 5 > 3 ✓, move q to 2
• At q = 2: Check if nums[2] > nums[3] → 3 > 1 ✓, move q to 3
• At q = 3: Check if nums[3] > nums[4] → 1 > 4 ✗, stop
• Decreasing section: [5, 3, 1] (indices 1 to 3)
• q = 3 (last index of decreasing section)

Step 3: Verify the final increasing section

• At q = 3: Check if nums[3] < nums[4] → 1 < 4 ✓, move q to 4
• At q = 4: Check if nums[4] < nums[5] → 4 < 6 ✓, move q to 5
• At q = 5: We've reached n - 1, stop
• Final increasing section: [1, 4, 6] (indices 3 to 5)

Step 4: Final validation

• Check if q == n - 1 → 5 == 5 ✓
• The array successfully forms the pattern: increase → decrease → increase
• Return true

The array [2, 5, 3, 1, 4, 6] is trionic with transition points at p = 1 and q = 3.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm makes a single pass through the array using three sequential while loops. In the worst case, each element is visited at most once across all three loops combined. The first loop iterates through elements while they're increasing, the second loop continues from where the first stopped and iterates while elements are decreasing, and the third loop continues from where the second stopped and iterates while elements are increasing again. Since each element is processed at most once, the total time complexity is linear.

The space complexity is O(1), using only constant extra space. The algorithm uses only a fixed number of variables (n, p, and q) regardless of the input size. No additional data structures like arrays, lists, or recursive call stacks are created, so the memory usage remains constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Off-by-One Errors with Index Boundaries

A critical mistake occurs when developers misunderstand how the indices p and q relate to the array segments. After the first while loop, p points to the last element of the increasing section, not the first element of the decreasing section. This confusion often leads to incorrect boundary checks.

Incorrect approach:

# Wrong: Treating p as the start of decreasing section
if p >= n - 2:  # This check is too restrictive
    return False

Correct approach:

# Right: p is the last element of increasing section
# We need at least 2 more elements after p for valid trionic
if p == 0:  # No increasing section found
    return False

Pitfall 2: Not Handling Adjacent Duplicate Values

The problem requires strictly monotonic sequences, meaning consecutive equal values invalidate the pattern. Developers often use <= or >= comparisons instead of strict < or >.

Incorrect approach:

# Wrong: Allows equal consecutive values
while p < n - 2 and nums[p] <= nums[p + 1]:  # Should be strict <
    p += 1

Correct approach:

# Right: Strict inequality ensures no duplicates
while p < n - 2 and nums[p] < nums[p + 1]:
    p += 1

Pitfall 3: Incorrect Minimum Array Length Validation

Some developers add explicit length checks that are either unnecessary or incorrect. The algorithm naturally handles the minimum length requirement through its logic.

Incorrect approach:

def isTrionic(self, nums):
    n = len(nums)
    if n < 3:  # Wrong threshold - should be 4 minimum
        return False
    # ... rest of code

Better approach: The current solution implicitly handles this through the while loop conditions. The first loop requires p < n - 2, ensuring at least 3 elements. The subsequent checks ensure we need at least 4 elements total for a valid trionic pattern.

Pitfall 4: Misunderstanding the Shared Boundary Elements

A subtle but important detail: the element at index p belongs to both the first increasing section (as its last element) and the second decreasing section (as its first element). Similarly for index q.

Example with [1, 3, 2, 4]:

• First section: indices 0 to 1, values [1, 3]
• Second section: indices 1 to 2, values [3, 2]
• Third section: indices 2 to 3, values [2, 4]

The boundaries overlap - this is correct and intended behavior. Developers sometimes try to "fix" this by adjusting indices unnecessarily, breaking the algorithm.