LeetCode 665: Non-decreasing Array

Question

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;
}

Answer 1

Avoid unnecessary special case handling

You exit early if the size of the array is less than 3, but this is unnecessary: the rest of the code already handles arrays of size 0, 1 and 2 correctly. You might save a cycle if you feed it a small array, but you pay for this check with a cycle or two for every time the function is called with std::size(nums) > 2.

Use std::size_t for indices

You made index a std::int_fast32_t, but this has a different size (likely) and a different signedness than the result of std::size(nums). This means the compiler should have warned you about a comparison between signed and unsigned integers. While things work out here, since you know the size of the input array is constrained, it is best to use std::size_t here to avoid the compiler warning. Performance is likely not going to differ one bit, since index can be kept in a CPU register at all times.

There is no need to use std::to_string() when using << on a std::ostream

When writing to a std::ostream, operator<< will already cause the argument to be formatted, so there is no need to call std::to_string(). In fact, you can tell the stream to format a bool as text:

int main() {
 std::vector<int> nums = {3, 4, 2, 3};
 std::cout << std::boolalpha << Solution().checkPossibility(nums) << "\n";
}