mediumArraysPattern: Mixed
Longest Alternating Sequences Solution
Problem Statement
Given an array of integers `values`, determine the length of the longest increasing-decreasing sequence and the longest decreasing-increasing sequence.
Examples
Example 1:
Input:{"values":[12321]}
Output:[32]
Explanation: The longest bull-run is the sequence 1,2,3 of length 3 and the longest bear-run is the sequence 3,2,1 of length 3, but since bull-run is followed by bear-run in the problem description, so the longest bear-run here is the sequence 3,2 of length 2
Example 2:
Input:{"values":[54321]}
Output:[15]
Explanation: The longest bull-run is the sequence of single element 5 of length 1 and the longest bear-run is the sequence 5,4,3,2,1 of length 5
Constraints
- 2 <= length of input array <= 1000
- -1000 <= each element in the input array <= 1000
Time: O(n) Space: O(1)
The optimal approach involves iterating over the array to identify increasing and decreasing sequences in a single pass, resulting in a time complexity of O(n). This can be achieved by maintaining two variables to track the length of the longest bull-run and bear-run sequences.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.