I'm posting a solution for LeetCode's "Non-decreasing Array". If you'd like to review, please do. Thank you!
Problem
Given an array nums
with n
integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
We define an array is non-decreasing if nums[i] <= nums[i + 1]
holds for every i (0-based) such that (0 <= i <= n - 2
).
Example 1:
- Input: nums = [4,2,3]
- Output: true
- Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
- Input: nums = [4,2,1]
- Output: false
- Explanation: You can't get a non-decreasing array by modify at most one element.
Constraints:
1 <= n <= 10 ^ 4
-10 ^ 5 <= nums[i] <= 10 ^ 5
Code
// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
struct Solution {
using ValueType = std::int_fast32_t;
static const bool checkPossibility(
std::vector<int>& nums
) {
if (std::size(nums) < 3) {
return true;
}
ValueType max_changes = 0;
for (ValueType index = 1; max_changes < 2 && index < std::size(nums); ++index) {
if (nums[index - 1] > nums[index]) {
++max_changes;
if (index - 2 < 0 || nums[index - 2] <= nums[index]) {
nums[index - 1] = nums[index];
} else {
nums[index] = nums[index - 1];
}
}
}
return max_changes < 2;
}
};
int main() {
std::vector<int> nums = {3, 4, 2, 3};
std::cout << std::to_string(Solution().checkPossibility(nums) == false) << "\n";
return 0;
}