3830. Longest Alternating Subarray After Removing At Most One Element

Description

You are given an integer array nums.

A subarray nums[l..r] is alternating if one of the following holds:

nums[l] < nums[l + 1] > nums[l + 2] < nums[l + 3] > ...
nums[l] > nums[l + 1] < nums[l + 2] > nums[l + 3] < ...

In other words, if we compare adjacent elements in the subarray, then the comparisons alternate between strictly greater and strictly smaller.

You can remove at most one element from nums. Then, you select an alternating subarray from nums.

Return an integer denoting the maximum length of the alternating subarray you can select.

A subarray of length 1 is considered alternating.

Example 1:

Input: nums = [2,1,3,2]

Output: 4

Explanation:

Choose not to remove elements.
Select the entire array [2, 1, 3, 2], which is alternating because 2 > 1 < 3 > 2.

Example 2:

Input: nums = [3,2,1,2,3,2,1]

Output: 4

Explanation:

Choose to remove nums[3] i.e., [3, 2, 1, 2, 3, 2, 1]. The array becomes [3, 2, 1, 3, 2, 1].
Select the subarray [3, 2, 1, 3, 2, 1].

Example 3:

Input: nums = [100000,100000]

Output: 1

Explanation:

Choose not to remove elements.
Select the subarray [100000, 100000].

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Solutions

Solution 1: Prefix-Suffix Decomposition + Enumeration

We use two arrays $l_1$ and $l_2$ to represent the length of the longest alternating subarray ending at position $i$ with the last comparison being “<” and “>”, respectively. Similarly, we use $r_1$ and $r_2$ to represent the length of the longest alternating subarray starting at position $i$ with the first comparison being “<” and “>”, respectively.

We can compute $l_1$ and $l_2$ through a single left-to-right traversal, and then compute $r_1$ and $r_2$ through a single right-to-left traversal.

Next, we initialize the answer as $\max(\max(l_1), \max(l_2))$, which represents the length of the longest alternating subarray without removing any elements.

Then, we enumerate the position $i$ of the element to be removed. If after removing position $i$, positions $i-1$ and $i+1$ can still form an alternating relationship, we can add $l_1[i-1]$ and $r_1[i+1]$ (or $l_2[i-1]$ and $r_2[i+1]$) together to update the answer.

The time complexity is $O(n)$ and the space complexity is $O(n)$.

class Solution {
    public int longestAlternating(int[] nums) {
        int n = nums.length;
        int[] l1 = new int[n];
        int[] l2 = new int[n];
        int[] r1 = new int[n];
        int[] r2 = new int[n];

        for (int i = 0; i < n; i++) {
            l1[i] = 1;
            l2[i] = 1;
            r1[i] = 1;
            r2[i] = 1;
        }

        int ans = 0;

        for (int i = 1; i < n; i++) {
            if (nums[i - 1] < nums[i]) {
                l1[i] = l2[i - 1] + 1;
            } else if (nums[i - 1] > nums[i]) {
                l2[i] = l1[i - 1] + 1;
            }
            ans = Math.max(ans, l1[i]);
            ans = Math.max(ans, l2[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i + 1] > nums[i]) {
                r1[i] = r2[i + 1] + 1;
            } else if (nums[i + 1] < nums[i]) {
                r2[i] = r1[i + 1] + 1;
            }
        }

        for (int i = 1; i < n - 1; i++) {
            if (nums[i - 1] < nums[i + 1]) {
                ans = Math.max(ans, l2[i - 1] + r2[i + 1]);
            } else if (nums[i - 1] > nums[i + 1]) {
                ans = Math.max(ans, l1[i - 1] + r1[i + 1]);
            }
        }

        return ans;
    }
}

class Solution {
public:
    int longestAlternating(vector<int>& nums) {
        int n = nums.size();
        vector<int> l1(n, 1), l2(n, 1), r1(n, 1), r2(n, 1);

        int ans = 0;

        for (int i = 1; i < n; i++) {
            if (nums[i - 1] < nums[i]) {
                l1[i] = l2[i - 1] + 1;
            } else if (nums[i - 1] > nums[i]) {
                l2[i] = l1[i - 1] + 1;
            }
            ans = max(ans, l1[i]);
            ans = max(ans, l2[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i + 1] > nums[i]) {
                r1[i] = r2[i + 1] + 1;
            } else if (nums[i + 1] < nums[i]) {
                r2[i] = r1[i + 1] + 1;
            }
        }

        for (int i = 1; i < n - 1; i++) {
            if (nums[i - 1] < nums[i + 1]) {
                ans = max(ans, l2[i - 1] + r2[i + 1]);
            } else if (nums[i - 1] > nums[i + 1]) {
                ans = max(ans, l1[i - 1] + r1[i + 1]);
            }
        }

        return ans;
    }
};

class Solution:
    def longestAlternating(self, nums: List[int]) -> int:
        n = len(nums)
        l1 = [1] * n
        l2 = [1] * n
        r1 = [1] * n
        r2 = [1] * n
        ans = 0
        for i in range(1, n):
            if nums[i - 1] < nums[i]:
                l1[i] = l2[i - 1] + 1
            elif nums[i - 1] > nums[i]:
                l2[i] = l1[i - 1] + 1
            ans = max(ans, l1[i], l2[i])
        for i in range(n - 2, -1, -1):
            if nums[i + 1] > nums[i]:
                r1[i] = r2[i + 1] + 1
            elif nums[i + 1] < nums[i]:
                r2[i] = r1[i + 1] + 1
        for i in range(1, n - 1):
            if nums[i - 1] < nums[i + 1]:
                ans = max(ans, l2[i - 1] + r2[i + 1])
            elif nums[i - 1] > nums[i + 1]:
                ans = max(ans, l1[i - 1] + r1[i + 1])
        return ans

func longestAlternating(nums []int) int {
	n := len(nums)
	l1 := make([]int, n)
	l2 := make([]int, n)
	r1 := make([]int, n)
	r2 := make([]int, n)

	for i := 0; i < n; i++ {
		l1[i] = 1
		l2[i] = 1
		r1[i] = 1
		r2[i] = 1
	}

	ans := 0

	for i := 1; i < n; i++ {
		if nums[i-1] < nums[i] {
			l1[i] = l2[i-1] + 1
		} else if nums[i-1] > nums[i] {
			l2[i] = l1[i-1] + 1
		}

		ans = max(ans, l1[i], l2[i])
	}

	for i := n - 2; i >= 0; i-- {
		if nums[i+1] > nums[i] {
			r1[i] = r2[i+1] + 1
		} else if nums[i+1] < nums[i] {
			r2[i] = r1[i+1] + 1
		}
	}

	for i := 1; i < n-1; i++ {
		if nums[i-1] < nums[i+1] {
			if l2[i-1]+r2[i+1] > ans {
				ans = l2[i-1] + r2[i+1]
			}
		} else if nums[i-1] > nums[i+1] {
			if l1[i-1]+r1[i+1] > ans {
				ans = l1[i-1] + r1[i+1]
			}
		}
	}

	return ans
}

function longestAlternating(nums: number[]): number {
    const n = nums.length;
    const l1 = new Array<number>(n).fill(1);
    const l2 = new Array<number>(n).fill(1);
    const r1 = new Array<number>(n).fill(1);
    const r2 = new Array<number>(n).fill(1);

    let ans = 0;

    for (let i = 1; i < n; i++) {
        if (nums[i - 1] < nums[i]) {
            l1[i] = l2[i - 1] + 1;
        } else if (nums[i - 1] > nums[i]) {
            l2[i] = l1[i - 1] + 1;
        }
        ans = Math.max(ans, l1[i]);
        ans = Math.max(ans, l2[i]);
    }

    for (let i = n - 2; i >= 0; i--) {
        if (nums[i + 1] > nums[i]) {
            r1[i] = r2[i + 1] + 1;
        } else if (nums[i + 1] < nums[i]) {
            r2[i] = r1[i + 1] + 1;
        }
    }

    for (let i = 1; i < n - 1; i++) {
        if (nums[i - 1] < nums[i + 1]) {
            ans = Math.max(ans, l2[i - 1] + r2[i + 1]);
        } else if (nums[i - 1] > nums[i + 1]) {
            ans = Math.max(ans, l1[i - 1] + r1[i + 1]);
        }
    }

    return ans;
}

impl Solution {
    pub fn longest_alternating(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut l1 = vec![1; n];
        let mut l2 = vec![1; n];
        let mut r1 = vec![1; n];
        let mut r2 = vec![1; n];

        let mut ans = 0;

        for i in 1..n {
            if nums[i - 1] < nums[i] {
                l1[i] = l2[i - 1] + 1;
            } else if nums[i - 1] > nums[i] {
                l2[i] = l1[i - 1] + 1;
            }
            ans = ans.max(l1[i]);
            ans = ans.max(l2[i]);
        }

        for i in (0..n - 1).rev() {
            if nums[i + 1] > nums[i] {
                r1[i] = r2[i + 1] + 1;
            } else if nums[i + 1] < nums[i] {
                r2[i] = r1[i + 1] + 1;
            }
        }

        for i in 1..n - 1 {
            if nums[i - 1] < nums[i + 1] {
                ans = ans.max(l2[i - 1] + r2[i + 1]);
            } else if nums[i - 1] > nums[i + 1] {
                ans = ans.max(l1[i - 1] + r1[i + 1]);
            }
        }

        ans
    }
}

3830 - Longest Alternating Subarray After Removing At Most One Element

3830. Longest Alternating Subarray After Removing At Most One Element

Description

Solutions

Solution 1: Prefix-Suffix Decomposition + Enumeration

All Problems

All Solutions

Welcome to Subscribe On Youtube

3830. Longest Alternating Subarray After Removing At Most One Element

Description

Solutions

Solution 1: Prefix-Suffix Decomposition + Enumeration

All Problems

All Solutions