Trionic Array I

Easy
1850.

Trionic Array I

Trionic Array I is an easy coding problem on arrays, asked in Amazon interviews.

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, and
  • nums[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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isTrionic = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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, and
  • nums[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

  1. Hint 1

    The three parts are forced: p must be where the first rise ends and q where the following fall ends.

  2. 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.

  3. 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

  1. Advance i from 0 while nums[i] < nums[i + 1]; set p = i. If p == 0, return false.
  2. Advance while nums[i] > nums[i + 1]; set q = i. If q == p or q == n - 1, return false.
  3. Advance while nums[i] < nums[i + 1]. Return i == 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 > p and q < 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 - 1

Java

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