Problem Statement in English

You’re given a 0-indexed integer array nums. An array is called a trionic array if there exist indices 0 < p < q < nums.length - 1 such that:

  • nums[0] < nums[1] < ... < nums[p - 1] < nums[p]
  • nums[p] > nums[p + 1] > ... > nums[q - 1] > nums[q]
  • nums[q] < nums[q + 1] < ... < nums[nums.length - 1]

Return true if nums is a trionic array. Otherwise, return false.

Approach

We can solve this problem by traversing the array while checking for the three segments: strictly increasing, strictly decreasing, and strictly increasing again.

Basically, just do exactly what the problem statement says. And add some checks to ensure that each segment has at least one element.

Solution in Python


class Solution:
    def isTrionic(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 4:
            return False

        i = 1

        # strictly increasing
        while i < n and nums[i] > nums[i - 1]:
            i += 1
        p = i - 1

        # must have at least one element in first segment
        if p == 0:
            return False

        # strictly decreasing
        while i < n and nums[i] < nums[i - 1]:
            i += 1
        q = i - 1

        # must have at least one element in second segment
        if q == p or q == n - 1:
            return False

        # strictly increasing again
        while i < n and nums[i] > nums[i - 1]:
            i += 1

        return i == n

Complexity

  • Time: $O(n)$
    Since we traverse the array once.

  • Space: $O(1)$
    Since we use constant space.

Mistakes I Made

I overcomplicated the solution a lot.

And we are done.