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