LeetCode 3637 - Trionic Array I

We are given an integer array nums and need to determine whether it can be divided into three consecutive segments that follow a very specific pattern: 1. A strictly increasing segment. 2. A strictly decreasing segment. 3. A strictly increasing segment.

leetcodeeasyarray

LeetCode Problem 3637

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

We are given an integer array nums and need to determine whether it can be divided into three consecutive segments that follow a very specific pattern:

  1. A strictly increasing segment.
  2. A strictly decreasing segment.
  3. A strictly increasing segment.

More formally, we must find two indices p and q such that:

  • 0 < p < q < n - 1
  • nums[0...p] is strictly increasing
  • nums[p...q] is strictly decreasing
  • nums[q...n-1] is strictly increasing

The word "strictly" is important. Adjacent elements must satisfy either < or > exactly. Equal values are not allowed in any segment.

The input is an integer array nums of length n, and the output should be:

  • true if such indices p and q exist
  • false otherwise

The constraints are very small:

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

Since n is only 100, even relatively inefficient solutions would work. However, we can still design a clean linear-time solution.

Some important edge cases include arrays that are entirely increasing, entirely decreasing, contain equal adjacent values, or do not have enough elements to form all three required segments. The conditions 0 < p and q < n - 1 guarantee that all three segments must contain at least two elements, meaning each segment contributes at least one comparison.

Approaches

Brute Force

A straightforward approach is to try every possible pair (p, q).

For each pair:

  • Verify that nums[0...p] is strictly increasing.
  • Verify that nums[p...q] is strictly decreasing.
  • Verify that nums[q...n-1] is strictly increasing.

If any pair satisfies all conditions, return true.

This approach is correct because it explicitly checks every valid choice of turning points. If a valid trionic decomposition exists, one of the examined pairs will find it.

However, there are O(n²) possible (p, q) pairs, and each verification may take O(n) time, leading to O(n³) complexity.

Key Insight

The trionic pattern is very rigid:

  • First we climb strictly upward.
  • Then we descend strictly downward.
  • Then we climb strictly upward again.

Instead of testing every possible split, we can simulate this pattern directly.

Starting from the beginning:

  • Move forward while values are strictly increasing.
  • Then move forward while values are strictly decreasing.
  • Then move forward while values are strictly increasing.

If all three phases consume at least one comparison and we finish exactly at the last element, the array is trionic.

This works because a valid trionic array has a unique traversal order of increasing, decreasing, then increasing. We do not need to guess p and q; they naturally appear where the direction changes.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Try every (p, q) and validate all segments
Optimal O(n) O(1) Single scan through the three required phases

Algorithm Walkthrough

  1. Let i = 0. This pointer will walk through the array.
  2. Traverse the first increasing segment.

Continue advancing while nums[i] < nums[i + 1].

When this loop stops, we have reached the potential peak p. 3. Verify that the first segment exists.

If no movement occurred, then p = 0, which violates 0 < p. Return false. 4. Traverse the decreasing segment.

Continue advancing while nums[i] > nums[i + 1].

When this loop stops, we have reached the potential valley q. 5. Verify that the decreasing segment exists.

If no movement occurred during this phase, then no valid decreasing section exists. Return false. 6. Traverse the final increasing segment.

Continue advancing while nums[i] < nums[i + 1]. 7. Verify that the final increasing segment exists.

If no movement occurred during this phase, then the third segment does not exist. Return false. 8. After completing all three phases, check whether i reached the last index.

If yes, the entire array exactly matches the required pattern and we return true.

Otherwise, some elements remain that do not fit the pattern, so return false.

Why it works

The algorithm maintains the invariant that the array prefix processed so far exactly follows the required trionic pattern. The first phase consumes the maximal strictly increasing prefix, the second phase consumes the maximal strictly decreasing section, and the third phase consumes the maximal strictly increasing suffix. If each phase contains at least one comparison and the traversal ends precisely at the final element, then valid indices p and q exist and all problem requirements are satisfied. Conversely, any trionic array must follow this exact sequence of direction changes, so the algorithm cannot miss a valid solution.

Python Solution

from typing import List

class Solution:
    def isTrionic(self, nums: List[int]) -> bool:
        n = len(nums)
        i = 0

        # First strictly increasing segment
        start = i
        while i + 1 < n and nums[i] < nums[i + 1]:
            i += 1

        if i == start:
            return False

        # Strictly decreasing segment
        start = i
        while i + 1 < n and nums[i] > nums[i + 1]:
            i += 1

        if i == start:
            return False

        # Final strictly increasing segment
        start = i
        while i + 1 < n and nums[i] < nums[i + 1]:
            i += 1

        if i == start:
            return False

        return i == n - 1

The implementation uses a single pointer i to walk through the array.

The first loop consumes the initial strictly increasing section. If no movement occurs, then the first segment does not exist and the array cannot be trionic.

The second loop consumes the strictly decreasing section. Again, at least one step must be taken or the required middle segment is missing.

The third loop consumes the final strictly increasing section. This segment must also contain at least one comparison.

Finally, the algorithm verifies that every element was consumed by the three phases. If i is exactly n - 1, then the entire array follows the trionic structure.

Go Solution

func isTrionic(nums []int) bool {
	n := len(nums)
	i := 0

	// First strictly increasing segment
	start := i
	for i+1 < n && nums[i] < nums[i+1] {
		i++
	}
	if i == start {
		return false
	}

	// Strictly decreasing segment
	start = i
	for i+1 < n && nums[i] > nums[i+1] {
		i++
	}
	if i == start {
		return false
	}

	// Final strictly increasing segment
	start = i
	for i+1 < n && nums[i] < nums[i+1] {
		i++
	}
	if i == start {
		return false
	}

	return i == n-1
}

The Go implementation follows exactly the same logic as the Python version. No additional data structures are required. Integer overflow is not a concern because we only perform comparisons. Slices are accessed directly using indices, and the algorithm uses constant extra space.

Worked Examples

Example 1

Input:

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

First Increasing Phase

i Before Comparison Result i After
0 1 < 3 True 1
1 3 < 5 True 2
2 5 < 4 False 2

Potential p = 2.

Decreasing Phase

i Before Comparison Result i After
2 5 > 4 True 3
3 4 > 2 True 4
4 2 > 6 False 4

Potential q = 4.

Final Increasing Phase

i Before Comparison Result i After
4 2 < 6 True 5

Now i = 5 = n - 1.

Result:

true

Example 2

Input:

nums = [2, 1, 3]

First Increasing Phase

i Before Comparison Result i After
0 2 < 1 False 0

No movement occurred.

This means the first increasing segment does not exist, violating 0 < p.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is visited at most once across the three phases
Space O(1) Only a few variables are used

The pointer only moves forward and never retreats. Across all three loops, it advances at most n - 1 times, giving linear time complexity. No auxiliary data structures are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

s = Solution()

assert s.isTrionic([1, 3, 5, 4, 2, 6]) == True      # provided example
assert s.isTrionic([2, 1, 3]) == False             # provided example

assert s.isTrionic([1, 2, 1, 2]) == True           # smallest valid trionic pattern
assert s.isTrionic([1, 2, 3, 2, 1, 2, 3]) == True # longer valid pattern

assert s.isTrionic([1, 2, 3, 4]) == False         # only increasing
assert s.isTrionic([4, 3, 2, 1]) == False         # only decreasing

assert s.isTrionic([1, 2, 3, 2, 1]) == False      # missing final increase
assert s.isTrionic([3, 2, 1, 2, 3]) == False      # missing initial increase

assert s.isTrionic([1, 2, 2, 1, 2]) == False      # equal values in first segment
assert s.isTrionic([1, 3, 2, 2, 4]) == False      # equal values in middle segment
assert s.isTrionic([1, 3, 2, 4, 4]) == False      # equal values in final segment

assert s.isTrionic([1, 3, 2, 4, 3]) == False      # extra decreasing tail
assert s.isTrionic([1, 3, 2, 4, 5]) == True       # valid final increase

assert s.isTrionic([-5, -2, -4, 0]) == True       # negative values
assert s.isTrionic([0, 5, 1, 6]) == True          # short valid case

Test Summary

Test Why
[1,3,5,4,2,6] Official valid example
[2,1,3] Official invalid example
[1,2,1,2] Smallest practical valid pattern
[1,2,3,2,1,2,3] Larger valid pattern
[1,2,3,4] Missing decreasing phase
[4,3,2,1] Missing increasing phases
[1,2,3,2,1] Missing final increase
[3,2,1,2,3] Missing initial increase
[1,2,2,1,2] Equality breaks strict increase
[1,3,2,2,4] Equality breaks strict decrease
[1,3,2,4,4] Equality breaks final increase
[1,3,2,4,3] Pattern continues after third phase
[1,3,2,4,5] Valid trionic ending
[-5,-2,-4,0] Negative numbers
[0,5,1,6] Minimal style valid pattern

Edge Cases

Equal Adjacent Elements

Arrays containing equal adjacent values are a common source of mistakes because the problem requires strict inequalities. For example, [1, 2, 2, 1, 2] might appear to have an increasing section followed by a decreasing section, but the equality 2 == 2 violates strict monotonicity. The implementation uses only < and > comparisons, so equal values immediately stop a phase and correctly cause the array to be rejected.

Missing One of the Three Segments

An array such as [1, 2, 3, 2, 1] contains an increasing section and a decreasing section but never starts the final increasing section. A naive implementation might incorrectly accept it after finding two direction changes. The algorithm explicitly requires movement during all three phases, ensuring that each segment exists.

Extra Elements After the Third Phase

Consider [1, 3, 2, 4, 3]. The array initially looks valid because it increases, decreases, then increases again. However, after the final increase there is another decrease, which is not allowed. The final check i == n - 1 guarantees that the entire array is consumed by exactly the required three phases and rejects any additional direction changes.

Very Small Arrays

The smallest valid trionic array has length four, for example [1, 2, 1, 2]. Arrays of length three can never satisfy all three required segments because there are not enough elements to form increasing, decreasing, and increasing portions simultaneously. The implementation naturally handles this because at least one movement is required in each of the three phases.