Leetcode 978: Longest Turbulent Subarray
Given an integer array arr, return the length of the largest subarray that is turbulent. A subarray is considered turbulent if the comparison sign alternates between each adjacent pair of elements.
Problem
Approach
Steps
Complexity
Input: An integer array arr.
Example: arr = [5, 3, 8, 10, 2, 7, 9]
Constraints:
• 1 <= arr.length <= 4 * 10^4
• 0 <= arr[i] <= 10^9
Output: The length of the largest turbulent subarray of arr.
Example: 5
Constraints:
• The length of the subarray should be at least 1.
Goal: Find the longest turbulent subarray by tracking the alternating comparisons between adjacent elements.
Steps:
• Use a dynamic programming approach with two states to track alternating comparisons.
• Maintain a variable to store the maximum length of the turbulent subarray encountered so far.
• Iterate through the array to detect and extend the turbulent subarrays.
Goal: Ensure that the input array meets the problem's constraints.
Steps:
• 1 <= arr.length <= 4 * 10^4
• 0 <= arr[i] <= 10^9
Assumptions:
• The array has at least one element.
• Input: arr = [5, 3, 8, 10, 2, 7, 9]
• Explanation: The longest turbulent subarray is [3, 8, 10, 2, 7], where comparisons alternate as expected.
• Input: arr = [1, 2, 3, 4, 5]
• Explanation: The longest turbulent subarray is [1, 2], where the comparison alternates once.
Approach: Use a dynamic programming approach to keep track of alternating comparison states and find the longest turbulent subarray.
Observations:
• The comparison between adjacent elements alternates between greater than and less than.
• A dynamic programming approach with two states will help efficiently solve the problem.
Steps:
• Initialize two variables to track the length of the increasing and decreasing turbulent subarrays.
• Iterate through the array to update these lengths based on the comparisons between adjacent elements.
• Update the maximum length encountered during the iteration.
Empty Inputs:
• An empty input array should return 0.
Large Inputs:
• Large arrays with up to 40,000 elements should be processed efficiently.
Special Values:
• Single-element arrays, which are trivially turbulent with a length of 1.
Constraints:
• The input array must contain at least one element.
int maxTurbulenceSize(vector<int>& arr) {
vector<int> dp(2, 1);
int res = 1, n = arr.size(), prv = 0;
for(int i = 1; i < n; i++) {
if ((prv == 0 || prv == -1) && arr[i - 1] < arr[i] ) {
dp[0] = dp[1] + 1;
res = max(res, dp[0]);
prv = 1;
} else if ((prv == 0 || prv == 1) && arr[i - 1] > arr[i] ) {
dp[1] = dp[0] + 1;
res = max(res, dp[1]);
prv = -1;
}
else if (arr[i - 1] == arr[i] ) {
dp[0] = 1;
dp[1] = 1;
prv = 0;
} else {
dp[0] = 2;
dp[1] = 2;
prv = (arr[i - 1] < arr[i]) ? 1 : -1;
}
}
return res;
}
1 : Function Definition
int maxTurbulenceSize(vector<int>& arr) {
Defines the function `maxTurbulenceSize` which takes a reference to a vector of integers `arr` and returns an integer representing the length of the maximum turbulent subarray.
2 : Dynamic Programming Initialization
vector<int> dp(2, 1);
Initializes a dynamic programming array `dp` of size 2, with both elements set to 1, which will be used to track the length of the turbulent subarrays. The two values represent the lengths of the turbulent subarrays ending in an increasing or decreasing manner.
3 : Variable Initialization
int res = 1, n = arr.size(), prv = 0;
Initializes the result variable `res` to 1 (the minimum possible length of a turbulent subarray), `n` to the size of the input array `arr`, and `prv` to 0 (representing the previous comparison state).
4 : Loop Initialization
for(int i = 1; i < n; i++) {
Starts a loop that iterates through the array from the second element (index 1) to the last element. This loop will check each pair of adjacent elements to determine if they form a turbulent subarray.
5 : Increasing Comparison
if ((prv == 0 || prv == -1) && arr[i - 1] < arr[i] ) {
Checks if the previous state was either 0 (initial state) or -1 (decreasing), and if the current pair is increasing (i.e., `arr[i - 1] < arr[i]`). If true, the current subarray can continue as turbulent in an increasing direction.
6 : Update DP for Increasing
dp[0] = dp[1] + 1;
Updates the length of the turbulent subarray ending in an increasing direction by incrementing the length of the turbulent subarray that was previously decreasing.
7 : Update Result for Increasing
res = max(res, dp[0]);
Updates the result `res` to the maximum value between the current result and the newly calculated length of the increasing turbulent subarray.
8 : Set Previous State to Increasing
prv = 1;
Sets the previous state `prv` to 1, indicating that the last comparison was an increasing one.
9 : Decreasing Comparison
} else if ((prv == 0 || prv == 1) && arr[i - 1] > arr[i] ) {
Checks if the previous state was either 0 (initial state) or 1 (increasing), and if the current pair is decreasing (i.e., `arr[i - 1] > arr[i]`). If true, the current subarray can continue as turbulent in a decreasing direction.
10 : Update DP for Decreasing
dp[1] = dp[0] + 1;
Updates the length of the turbulent subarray ending in a decreasing direction by incrementing the length of the turbulent subarray that was previously increasing.
11 : Update Result for Decreasing
res = max(res, dp[1]);
Updates the result `res` to the maximum value between the current result and the newly calculated length of the decreasing turbulent subarray.
12 : Set Previous State to Decreasing
prv = -1;
Sets the previous state `prv` to -1, indicating that the last comparison was a decreasing one.
13 : Handle Equal Adjacent Elements
else if (arr[i - 1] == arr[i] ) {
Checks if the current and previous elements are equal. If true, the turbulent subarray ends, and the dynamic programming states are reset.
14 : Reset DP for Equal Elements
dp[0] = 1;
Resets both dynamic programming values to 1, as the turbulent subarray must start fresh.
15 : Reset DP for Equal Elements
dp[1] = 1;
Resets the second dynamic programming value to 1 as well, ensuring the subarray starts over.
16 : Reset Previous State
prv = 0;
Resets the previous state `prv` to 0, indicating no trend (increasing or decreasing).
17 : Handle New Trend
} else {
Handles the case where the adjacent elements form a new trend (either increasing or decreasing).
18 : Start New Turbulent Subarray
dp[0] = 2;
Starts a new turbulent subarray with a length of 2.
19 : Start New Turbulent Subarray
dp[1] = 2;
Starts a new turbulent subarray with a length of 2 in the decreasing direction.
20 : Update Previous State
prv = (arr[i - 1] < arr[i]) ? 1 : -1;
Sets the previous state `prv` to 1 (increasing) or -1 (decreasing) depending on the comparison between `arr[i - 1]` and `arr[i]`.
21 : Return Result
return res;
Returns the length of the longest turbulent subarray found.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution iterates through the array once, leading to a time complexity of O(n).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only store a few variables for tracking the current and maximum subarray lengths.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus