The O(n) Club: Non-decreasing Array — Change Once Or Never

The O(n) Club: Non-decreasing Array — Change Once Or Never

⚡ TL;DR

This LeetCode classic asks: Can you rescue your out-of-order array by changing just one number? Brute force is slow, but works (kind of). Here’s the bad way:

// Try changing each number and checking—please don’t run in production!
public boolean checkPossibility(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int old = nums[i];
        nums[i] = i == 0 ? Integer.MIN_VALUE : nums[i - 1];
        if (isNonDecreasing(nums)) return true;
        nums[i] = old;
    }
    return false;
}
private boolean isNonDecreasing(int[] nums) {
    for (int i = 1; i < nums.length; i++)
        if (nums[i - 1] > nums[i]) return false;
    return true;
}

🧠 How Devs Usually Mess This Up

Most people spot a dip—say, nums[i] is bigger than nums[i+1]—and whack nums[i] into line. Congrats, you may have just ruined every pair before i. Sometimes, fixing the wrong guy just shifts the chaos downstream, or—bonus points—you run out of your “one fix” coupon before you even hit the second problem.

🔍 What’s Actually Going On

Picture a row of robots at a factory. Each should be the same height, or taller than the previous. When one suddenly shrinks, you can either stretch him up (change nums[i+1]) or compress the hulking neighbor (change nums[i]). But watch out—fiddle with the wrong one and the next robot riot starts. The trick: if the violation happens at the start or the guy two steps back is smaller, you can squash nums[i]. Otherwise, jack up nums[i+1] for everyone to get along. Hit two dips? Sorry, out of spare parts.

🛠️ PseudoCode

• Let count = 0 (number of changes used)
• Loop from to nums.length - 2:
• If nums[i] > nums[i+1]:
• Increment count
• If count > 1, return false immediately
• If at start (i == 0) or nums[i-1] <= nums[i+1]:
• Bump down nums[i] to nums[i+1]
• Else:
• Bump up nums[i+1] to nums[i]
• Survived? Return true

// Java-friendlier pseudocode
count = 0
for i = 0 to nums.length - 2:
    if nums[i] > nums[i+1]:
        count++
        if count > 1:
            return false
        if i == 0 or nums[i-1] <= nums[i+1]:
            nums[i] = nums[i+1]
        else:
            nums[i+1] = nums[i]
return true

💻 The Code

public boolean checkPossibility(int[] nums) {
    int tweaks = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] > nums[i+1]) {
            if (++tweaks > 1) return false;
            if (i == 0 || nums[i-1] <= nums[i+1]) {
                nums[i] = nums[i+1]; // Lower current
            } else {
                nums[i+1] = nums[i]; // Raise next
            }
        }
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Arrays like [3, 4, 2, 3] are trolls. No single change will fix the mess; know when to walk away.
• Your fix must not break stuff earlier in the array. If in doubt, check the neighbor’s neighbor.
• Only one modification. If you need a sequel, the answer is always “nope.”
• This solution is O(n) in time and O(1) in space, as nature intended.

🧠 Interviewer Brain-Tattoo

Arrays are forgiving, but only once. Blow your single chance and enjoy the eternal shame of extra bug tickets.