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] <= 1000Problem Overview: You are given an integer array and must determine whether it forms a trionic pattern. A trionic array has three consecutive phases: strictly increasing, then strictly decreasing, then strictly increasing again. Each phase must contain at least one valid transition.
Approach 1: Single Pass State Tracking (O(n) time, O(1) space)
Traverse the array once while tracking which phase of the pattern you are currently in. Start in the increasing phase and move forward comparing nums[i] with nums[i-1]. When the sequence stops increasing and begins decreasing, transition to the second phase. When the sequence switches from decreasing to increasing again, transition to the third phase. If any comparison violates the expected direction of the current phase, the array cannot be trionic.
The key insight is that the pattern is strictly ordered: increase → decrease → increase. You only move forward through these phases and never go backward. Each element comparison determines whether you remain in the current phase or transition to the next one. If the traversal finishes while successfully reaching the third phase and maintaining strict inequalities, the array satisfies the trionic condition.
This approach works because every element is examined exactly once. No auxiliary structures are required—only a few variables to track the phase and validate transitions. Time complexity is O(n) since the array is scanned once, and space complexity is O(1).
The technique is essentially a lightweight state machine implemented during array traversal. Problems that involve detecting patterns in sequences often rely on similar ideas using simple counters or phase flags. You can explore related traversal patterns in array problems and pattern-detection strategies often used alongside two pointers or simulation techniques.
Recommended for interviews: The single-pass approach is exactly what interviewers expect. It demonstrates that you recognize the pattern structure and can enforce it using constant space. A brute-force segmentation approach would work but adds unnecessary complexity, while the linear scan shows strong control over state transitions.
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 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 false directly.
If all the above conditions are satisfied, it means the array is trionic, and we return 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Segment Detection (Multiple Scans) | O(n) | O(1) | When explicitly separating increasing and decreasing segments for clarity |
| Single Pass State Tracking | O(n) | O(1) | Best general solution; minimal logic and optimal traversal |
Trionic Array I | Simple Intuition | Dry Run | Leetcode 3637 | codestorywithMIK • codestorywithMIK • 7,330 views views
Watch 9 more video solutions →Practice Trionic Array I with our built-in code editor and test cases.
Practice on FleetCode