Trionic Array I — Solution in Python, Java & C++
Trionic Array I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.
Trionic Array I is an easy coding problem on arrays, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An array nums of length n is trionic if there are indices 0 < p < q < n - 1 such that:
nums[0..p]is strictly increasing,nums[p..q]is strictly decreasing, andnums[q..n - 1]is strictly increasing.
In other words, the array goes up, then down, then up again, each part with at least one step. Return true if nums is trionic and false otherwise.
Example 1
Input: nums = [1,3,5,4,2,6]
Output: true
Explanation: p = 2 and q = 4: [1,3,5] rises, [5,4,2] falls, [2,6] rises.
Example 2
Input: nums = [2,1,3]
Output: false
Explanation: The array starts by falling, so no valid p exists.
Example 3
Input: nums = [1,2,1,2]
Output: true
Explanation: p = 1 and q = 2: one step up, one down, one up.
Constraints
3 <= n <= 100-1000 <= nums[i] <= 1000
Hints for Trionic Array I
Hint 1
The three parts are forced:
pmust be where the first rise ends andqwhere the following fall ends.Hint 2
Walk forward while the array rises, then while it falls, then while it rises again — and check each phase moved at least one step.
Hint 3
The array is trionic exactly when the third phase reaches the last index.
How to solve Trionic Array I
If the array is trionic, p is the end of the maximal strictly increasing prefix and q the end of the strictly decreasing run after it — there is no choice. So three greedy walks decide it.
Approach
- Advance
ifrom0whilenums[i] < nums[i + 1]; setp = i. Ifp == 0, returnfalse. - Advance while
nums[i] > nums[i + 1]; setq = i. Ifq == porq == n - 1, returnfalse. - Advance while
nums[i] < nums[i + 1]. Returni == n - 1.
Why it works
The first part must be a strictly increasing prefix ending at a peak, and it cannot stop before the rise does (the next step would be part of the decreasing part, but it rises) nor go past it. The same argument fixes q given p. With both forced, the remaining condition — the rest rises — is exactly what the third walk checks; equal neighbours stop every walk, as "strictly" requires.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Each phase needs at least one step:
p > 0,q > pandq < n - 1. - Equal neighbours stop every phase —
[1,2,2,1,3]is not trionic.
Reference solution
Python
from typing import List
def isTrionic(nums: List[int]) -> bool:
n = len(nums)
i = 0
while i + 1 < n and nums[i] < nums[i + 1]:
i += 1
p = i
if p == 0:
return False
while i + 1 < n and nums[i] > nums[i + 1]:
i += 1
q = i
if q == p or q == n - 1:
return False
while i + 1 < n and nums[i] < nums[i + 1]:
i += 1
return i == n - 1Java
public static boolean isTrionic(int[] nums) {
int n = nums.length, i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) i++;
int p = i;
if (p == 0) return false;
while (i + 1 < n && nums[i] > nums[i + 1]) i++;
int q = i;
if (q == p || q == n - 1) return false;
while (i + 1 < n && nums[i] < nums[i + 1]) i++;
return i == n - 1;
}C++
bool isTrionic(vector<int>& nums) {
int n = nums.size(), i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) i++;
int p = i;
if (p == 0) return false;
while (i + 1 < n && nums[i] > nums[i + 1]) i++;
int q = i;
if (q == p || q == n - 1) return false;
while (i + 1 < n && nums[i] < nums[i + 1]) i++;
return i == n - 1;
}JavaScript
var isTrionic = function(nums) {
var n = nums.length, i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) i++;
var p = i;
if (p === 0) return false;
while (i + 1 < n && nums[i] > nums[i + 1]) i++;
var q = i;
if (q === p || q === n - 1) return false;
while (i + 1 < n && nums[i] < nums[i + 1]) i++;
return i === n - 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays