2
\$\begingroup\$

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;
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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";
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.