Problem Description

Given an integer array nums, your task is to determine the minimum number of operations required to make the array either non-decreasing or non-increasing. In one operation, you can change any single element of the array to any integer value of your choice.

Definitions:

• An array is non-decreasing if for every i, nums[i] ≤ nums[i+1].
• An array is non-increasing if for every i, nums[i] ≥ nums[i+1].

• There is always at least one valid solution.
• You may change the same element multiple times, but each change counts as an operation.
• Do not reuse elements in a way that violates the array order.

Thought Process

To solve this problem, let's first think about what it means to convert the array into a non-decreasing or non-increasing sequence. For each option, we want to minimize the number of changes. A brute-force approach would be to try all possible sequences, but this is not efficient.

Instead, we realize that for each position, we can compare the original array to the closest possible non-decreasing and non-increasing sequences, and count the mismatches (places where nums[i] does not match the target sequence). The minimum of these two counts is our answer.

This leads us to consider dynamic programming or using Longest Non-Decreasing/Non-Increasing Subsequence (LNDS/LNIS) concepts. The key insight is that the minimum number of changes equals the array length minus the length of the longest non-decreasing (or non-increasing) subsequence.

Why? Because if we keep the elements that form this subsequence and only change the rest, we minimize operations.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Find the length of the Longest Non-Decreasing Subsequence (LNDS):
   • This tells us the maximum number of elements we can keep unchanged if we want a non-decreasing array.
2. Find the length of the Longest Non-Increasing Subsequence (LNIS):
   • This tells us the maximum number of elements we can keep unchanged if we want a non-increasing array.
3. Compute the minimum number of changes:
   • For each case, the number of changes required is len(nums) - length of subsequence.
   • Return the minimum of these two values.

• For LNDS: For each element, use binary search to find where it fits in a current sequence.
• For LNIS: Reverse the array and apply the same algorithm, or adjust the comparison direction.

Example Walkthrough

Let's use the input nums = [3, 2, 5, 1, 7].

Step 1: Find LNDS.

• Start with an empty sequence.
• 3: Add to sequence [3]
• 2: Replace 3 with 2 (since 2 < 3), sequence [2]
• 5: 5 > 2, append: [2,5]
• 1: Replace 2 with 1: [1,5]
• 7: 7 > 5, append: [1,5,7]
• LNDS length = 3 ([2,5,7] or [1,5,7])

• Apply the same process but for non-increasing:
• 3: [3]
• 2: 2 < 3, append: [3,2]
• 5: 5 > 3, replace 3 with 5: [5,2]
• 1: 1 < 2, append: [5,2,1]
• 7: 7 > 5, replace 5 with 7: [7,2,1]
• LNIS length = 3 ([5,2,1] or [7,2,1])

• Array length = 5
• Minimum changes = 5 - max(3,3) = 2

Time and Space Complexity

Brute-force approach:

• Try all possible sequences: O(2^N) time, which is impractical for large N.

• For both LNDS and LNIS, we use patience sorting with binary search: O(N log N) time.
• Space complexity is O(N), for storing the subsequence tails.

Summary

The key insight is that the minimum number of operations needed to make an array non-decreasing or non-increasing is the length of the array minus the length of the longest monotonic subsequence. By efficiently finding these subsequences using binary search, we solve the problem in O(N log N) time. This approach is both elegant and optimal, leveraging classic dynamic programming and greedy techniques.

Code Implementation

from bisect import bisect_right, bisect_left

def min_operations_to_monotonic(nums):
    def longest_non_decreasing(seq):
        dp = []
        for num in seq:
            idx = bisect_right(dp, num)
            if idx == len(dp):
                dp.append(num)
            else:
                dp[idx] = num
        return len(dp)
    
    def longest_non_increasing(seq):
        dp = []
        for num in seq:
            # For non-increasing, use negative values to invert the ordering
            idx = bisect_right(dp, -num)
            if idx == len(dp):
                dp.append(-num)
            else:
                dp[idx] = -num
        return len(dp)
    
    n = len(nums)
    lnnds = longest_non_decreasing(nums)
    lnnids = longest_non_increasing(nums)
    return n - max(lnnds, lnnids)
      

#include <vector>
#include <algorithm>

int minOperationsToMonotonic(std::vector<int>& nums) {
    auto LNDS = [](const std::vector<int>& seq) {
        std::vector<int> dp;
        for (int num : seq) {
            auto it = std::upper_bound(dp.begin(), dp.end(), num);
            if (it == dp.end())
                dp.push_back(num);
            else
                *it = num;
        }
        return dp.size();
    };

    auto LNIS = [](const std::vector<int>& seq) {
        std::vector<int> dp;
        for (int num : seq) {
            auto it = std::upper_bound(dp.begin(), dp.end(), -num);
            if (it == dp.end())
                dp.push_back(-num);
            else
                *it = -num;
        }
        return dp.size();
    };

    int n = nums.size();
    int lnds = LNDS(nums);
    int lnis = LNIS(nums);
    return n - std::max(lnds, lnis);
}
      

import java.util.*;

public class Solution {
    public int minOperationsToMonotonic(int[] nums) {
        return nums.length - Math.max(LNDS(nums), LNIS(nums));
    }

    private int LNDS(int[] nums) {
        ArrayList<Integer> dp = new ArrayList<>();
        for (int num : nums) {
            int idx = upperBound(dp, num);
            if (idx == dp.size())
                dp.add(num);
            else
                dp.set(idx, num);
        }
        return dp.size();
    }

    private int LNIS(int[] nums) {
        ArrayList<Integer> dp = new ArrayList<>();
        for (int num : nums) {
            int idx = upperBound(dp, -num);
            if (idx == dp.size())
                dp.add(-num);
            else
                dp.set(idx, -num);
        }
        return dp.size();
    }

    private int upperBound(ArrayList<Integer> dp, int target) {
        int left = 0, right = dp.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (dp.get(mid) <= target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}
      

function minOperationsToMonotonic(nums) {
    function LNDS(seq) {
        const dp = [];
        for (let num of seq) {
            let left = 0, right = dp.length;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (dp[mid] <= num) left = mid + 1;
                else right = mid;
            }
            if (left === dp.length) dp.push(num);
            else dp[left] = num;
        }
        return dp.length;
    }
    function LNIS(seq) {
        const dp = [];
        for (let num of seq) {
            let left = 0, right = dp.length;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (dp[mid] <= -num) left = mid + 1;
                else right = mid;
            }
            if (left === dp.length) dp.push(-num);
            else dp[left] = -num;
        }
        return dp.length;
    }
    const n = nums.length;
    return n - Math.max(LNDS(nums), LNIS(nums));
}