3637. Trionic Array I
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
.
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
at0
. Incrementp
as long asnums[p] < nums[p + 1]
andp < n - 2
. This finds the longest strictly increasing prefix. Ifp
is still at0
, there is no initial increase, so returnFalse
. -
Middle Decreasing Segment: Set another index
q
top
. Incrementq
as long asnums[q] > nums[q + 1]
andq < n - 1
. This finds the strictly decreasing segment coming after the increasing part. Ifq == p
(no decreasing segment) orq == n - 1
(array ends, so no place for final increase), returnFalse
. -
Final Increasing Segment: Continue incrementing
q
as long asnums[q] < nums[q + 1]
andq < n - 1
to verify the last segment is strictly increasing up to the end. Ifq
reachesn - 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 EvaluatorExample 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
andnums[1] = 4
. Since1 < 4
, incrementp
to1
. - Next, compare
nums[1] = 4
andnums[2] = 3
. Since4 > 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
andnums[2] = 3
. Since4 > 3
, incrementq
to2
. - Compare
nums[2] = 3
andnums[3] = 2
. Since3 > 2
, incrementq
to3
. - Compare
nums[3] = 2
andnums[4] = 5
. Since2 < 5
, the decreasing segment ends. Now,q = 3
. - Since
q != p
andq < n - 1
, the second segment exists.
Step 3: Check the last strictly increasing segment.
- From
q = 3
, comparenums[3] = 2
andnums[4] = 5
. Since2 < 5
, incrementq
to4
. - Compare
nums[4] = 5
andnums[5] = 7
. Since5 < 7
, incrementq
to5
. - 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.
Which technique can we use to find the middle of a linked list?
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!