LeetCode 665: Non-decreasing Array (C)

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

// Since the relevant headers are already included on the LeetCode platform,
// the headers can be removed;
#include <stdio.h>
#include <stdbool.h>

static const bool checkPossibility(
    int *nums,
    const int nums_size
) {

    if (nums_size < 3) {
        return true;
    }

    int max_changes = 0;

    for (int index = 1; index < nums_size - 1; ++index) {
        if (!(nums[index] >= nums[index - 1] && nums[index + 1] >= nums[index])) {
            if (nums[index + 1] >= nums[index - 1]) {
                ++max_changes;
                nums[index] = nums[index - 1];

            } else {
                if (nums[index] < nums[index - 1] && nums[index + 1] < nums[index]) {
                    return false;

                } else if (nums[index] <= nums[index + 1]) {
                    nums[index - 1] = nums[index];

                    if (!(index - 1) || nums[index - 2] <= nums[index - 1]) {
                        ++max_changes;

                    } else {
                        return false;
                    }

                } else {
                    nums[index + 1] = nums[index];
                    ++max_changes;
                }
            }
        }

    }


    return max_changes < 2;
}

int main() {

    static const int nums_size = 3;
    int nums_array[nums_size] = {4, 2, 1};
    int (*nums)[nums_size] = &nums_array;

    fputs(checkPossibility(*nums, nums_size) ? "true" : "false", stdout);

    return 0;
}

Answer 1

Simplify the logic

Why does this solution look more complicated than the C++ version you posted? It seems like you can use exactly the same logic as in the C++ version.

Don't return const values

Declaring the return value to be const is not doing anything unless you return a pointer.

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 nums_size > 2.

Simplify your main()

You do a lot of unnecessary things in main():

• There's no need to have a constant for the array up front, as you can use sizeof to get the size of the array, and divide it by the size of one element to get the number of elements.
• There is no need to declare a pointer to the array, the array itself can be used as a pointer.
• puts() is like fputs(), but always writes to stdout, and adds a newline for you.
• The return 0 is not necessary in main().

So you can simplify it as follows:

int main() {
    int array[] = {4, 2, 1};
    puts(checkPossibility(array, sizeof array / sizeof *array) ? "true" : "false");
}

Answer 2

The code mutates an array. It is not good.

The code does too much. You may return false as soon as max_changes reaches 2 (no need to examine the rest).

More functions please. It is very hard to follow the complicated decision making. Consider

int find_first_violation(int * nums, int size)
{
    int i = 0;
    for (; i < size; i++) {
        if (nums[i] < nums[i-1]) {
            break;
        }
    }
    return i;
}

Then the business logic would be:

    int violation = find_first_violation(nums, size);

    if (violation == size) {
        // array is already non-decreasing
        return true;
    }
    if (violation == size - 1) {
        // easily fixable: increase nums[size - 1]
        return true;
    }

    // Now fix the violation
    // violation == 1 is fixable by decreasing nums[0]. No action needed.
    // Otherwise, we only care about the case where nums[violation] is too
    // small - less than two preceding numbers. It is only fixable by
    // increasing it, effectively setting it equal to nums[violation - 1].

    if ((violation > 1) && (nums[violation] < nums[violation - 2])) {
        nums[violation] = nums[violation - 1];
    }

    // Finally, the core argument to have more functions: there
    // must be no more violations.

    return find_first_violation(nums + violation, size - violation) == size - violation;

Of course the first two conditions can be combined into violation >= size - 1. Of course increasing of nums[violation] can be virtual, without mutating the array (if nums[violation - 1] > nums[violation + 1] we may immediately return false;).