Longest Alternating Sequences ā Problem Statement & Solution Guide
Problem Description
Given an array of integers values, determine the length of the longest increasing-decreasing sequence and the longest decreasing-increasing sequence.
Examples
Input
[1, 2, 3, 2, 1, 5, 5, 5]
Output
[5, 5]
Explanation: Step-by-step: with input [1, 2, 3, 2, 1, 5, 5, 5], we first initialize two arrays, one for increasing-decreasing sequence and one for decreasing-increasing sequence. Then we iterate through the input array, and for each element, we check if it is greater than the last element in the increasing-decreasing sequence array, if so, we append it to the increasing-decreasing sequence array. We do the same for the decreasing-increasing sequence array. Finally, we return the maximum length of the two arrays.
Input
[5, 5, 5]
Output
[3, 3]
Explanation: Step-by-step: with input [5, 5, 5], we first initialize two arrays, one for increasing-decreasing sequence and one for decreasing-increasing sequence. Then we iterate through the input array, and for each element, we check if it is greater than the last element in the increasing-decreasing sequence array, if so, we append it to the increasing-decreasing sequence array. We do the same for the decreasing-increasing sequence array. Finally, we return the maximum length of the two arrays.
Constraints
- 2 <= length of input array <= 1000
- -1000 <= each element in the input array <= 1000
Optimal Approach & Strategy
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.
Brute Force Approach
One naive approach is to compare each element with every other element to identify increasing and decreasing sequences, resulting in a time complexity of O(nĀ²). This approach is inefficient and should be avoided for large inputs. A better approach would involve iterating over the array only once.
Verified Code Solutions
function longestAlternatingSequences(values) {
if (values.length === 0) return [0, 0];
let bullRun = 1, bearRun = 1, maxBullRun = 1, maxBearRun = 1;
for (let i = 1; i < values.length; i++) {
if (values[i] > values[i - 1]) {
bullRun += 1;
maxBullRun = Math.max(maxBullRun, bullRun);
bearRun = 1;
} else if (values[i] < values[i - 1]) {
bearRun += 1;
maxBearRun = Math.max(maxBearRun, bearRun);
bullRun = 1;
} else {
bullRun = 1;
bearRun = 1;
}
}
return [Math.max(maxBullRun, values.length), Math.max(maxBearRun, values.length)];
}class Solution {
public int[] longestAlternatingSequences(int[] nums) {
int[] increasing_decreasing = {nums[0]};
int[] decreasing_increasing = {nums[0]};
for (int i = 1; i < nums.length; i++) {
if (nums[i] > increasing_decreasing[increasing_decreasing.length - 1]) {
int[] temp = new int[increasing_decreasing.length + 1];
System.arraycopy(increasing_decreasing, 0, temp, 0, increasing_decreasing.length);
temp[increasing_decreasing.length] = nums[i];
increasing_decreasing = temp;
} else if (nums[i] < increasing_decreasing[increasing_decreasing.length - 1]) {
int[] temp = new int[decreasing_increasing.length + 1];
System.arraycopy(decreasing_increasing, 0, temp, 0, decreasing_increasing.length);
temp[decreasing_increasing.length] = nums[i];
decreasing_increasing = temp;
}
}
return new int[] {increasing_decreasing.length, decreasing_increasing.length};
}
}def longestAlternatingSequences(nums):
increasing_decreasing = [nums[0]]
decreasing_increasing = [nums[0]]
for i in range(1, len(nums)):
if nums[i] > increasing_decreasing[-1]:
increasing_decreasing.append(nums[i])
elif nums[i] < increasing_decreasing[-1]:
decreasing_increasing.append(nums[i])
return [len(increasing_decreasing), len(decreasing_increasing)]function longestAlternatingSequences(values) {
if (values.length === 0) return [0, 0];
let bullRun = 1, bearRun = 1, maxBullRun = 1, maxBearRun = 1;
for (let i = 1; i < values.length; i++) {
if (values[i] > values[i - 1]) {
bullRun += 1;
maxBullRun = Math.max(maxBullRun, bullRun);
bearRun = 1;
} else if (values[i] < values[i - 1]) {
bearRun += 1;
maxBearRun = Math.max(maxBearRun, bearRun);
bullRun = 1;
} else {
bullRun = 1;
bearRun = 1;
}
}
return [Math.max(maxBullRun, values.length), Math.max(maxBearRun, values.length)];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.