2263. Make Array Non-decreasing or Non-increasing - Detailed Explanation

Problem Statement

Given an array of integers, the goal is to remove as few elements as possible so that the remaining array becomes either non-decreasing (each element is less than or equal to the next) or non-increasing (each element is greater than or equal to the next). In other words, you want to achieve one of the following two conditions by removing some elements:

• Non-decreasing: For every valid index i, nums[i] ≤ nums[i + 1].
• Non-increasing: For every valid index i, nums[i] ≥ nums[i + 1].

The task is to determine the minimum number of removals needed.

Example Inputs, Outputs, and Explanations

Example 1

Input:

nums = [4, 2, 3, 5, 1]

Output:

2

Explanation:

• For a non-decreasing array, one possible remaining sequence is [2, 3, 5] (length 3).
• For a non-increasing array, one possible remaining sequence is [4, 2, 1] (length 3).
• In both cases, the maximum number of elements you can keep is 3, so you need to remove 5 − 3 = 2 elements.

Example 2

Input:

nums = [1, 3, 2, 2, 5]

Output:

1

Explanation:

• For a non-decreasing array, one possible subsequence is [1, 2, 2, 5] (length 4).
• For a non-increasing array, a possible subsequence might be shorter.
• The best you can do is keep 4 elements, so you remove 5 − 4 = 1 element.

Hints for the Approach

1. Longest Monotonic Subsequence:
   To minimize removals, you want to keep as many elements as possible that form a monotonic (either non-decreasing or non-increasing) subsequence. This is a variation of the classic "Longest Increasing Subsequence" problem.

2. Two Cases:
   Since the resulting array can be either non-decreasing or non-increasing, compute:

   • The length of the longest non-decreasing subsequence (LNDS).
   • The length of the longest non-increasing subsequence (LNIS).

3. Final Answer:
   The minimum number of removals equals the total number of elements minus the maximum of the two subsequence lengths.

Approach 1: Dynamic Programming (O(n²))

Explanation

• Longest Non-decreasing Subsequence (LNDS):
  Use a DP array where dp[i] represents the length of the longest non-decreasing subsequence ending at index i.

  • For each element at index i, look at all previous indices j (0 ≤ j < i).
  • If nums[j] ≤ nums[i], then you can extend the subsequence ending at j.
  • Set:

    dp[i] = max(dp[i], dp[j] + 1)
    

  • Initialize every dp[i] to 1 (each element alone is a valid subsequence).

• Longest Non-increasing Subsequence (LNIS):
  Similarly, use a DP array for non-increasing subsequences. For each index i:

  • For every index j (0 ≤ j < i), if nums[j] ≥ nums[i], update:

    dp[i] = max(dp[i], dp[j] + 1)
    

• Combining the Results:
  Let L1 be the maximum value from the LNDS DP array and L2 be the maximum from the LNIS DP array.
  The maximum number of elements you can keep is:

  maxKeep = max(L1, L2)
  

  Thus, the minimum removals required is:

  removals = n - maxKeep
  

Approach 2: Patience Sorting / Binary Search (O(n log n))

Explanation

• Optimized LNDS Calculation:
  Instead of the O(n²) DP, you can compute the LNDS using a method similar to the "Longest Increasing Subsequence" problem with binary search.

  • Maintain an array (or list) that represents the smallest possible tail for a subsequence of a given length.
  • For each number in the array, use binary search to determine its position in the tail array and update accordingly.
  • This approach gives an O(n log n) solution for the non-decreasing case.

• Optimized LNIS Calculation:
  Similarly, compute the longest non-increasing subsequence by modifying the comparison in the binary search (or by reversing the array and applying the same method).

• Final Calculation:
  Once you have both LNDS and LNIS lengths, determine the maximum keepable elements and subtract from the total count.

Complexity Analysis

• Dynamic Programming Approach:

  • Time Complexity: O(n²) due to the nested loops.
  • Space Complexity: O(n) for the DP arrays.

• Binary Search Approach:

  • Time Complexity: O(n log n) for each subsequence calculation, leading to overall O(n log n).

  • Space Complexity: O(n) for the arrays used in the binary search method.

Code Implementation

Python Code