Non-decreasing Array - Practice Coding Problems

Non-decreasing Array - Problem

Array Medium

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one 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.

Input & Output

Example 1 — Single Violation

$ Input: nums = [4,2,3]

› Output: true

💡 Note: We can modify nums[0] = 2 to get [2,2,3] which is non-decreasing, or nums[1] = 4 to get [4,4,3] but that creates another violation. The first option works.

Example 2 — Multiple Violations

$ Input: nums = [4,2,1]

› Output: false

💡 Note: We have violations at indices 0->1 (4>2) and 1->2 (2>1). Since we can only modify one element, we cannot fix both violations.

Example 3 — Already Sorted

$ Input: nums = [1,2,3,4]

› Output: true

💡 Note: Array is already non-decreasing, no modifications needed.

Constraints

2 ≤ nums.length ≤ 10⁴
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,2,3] with violation at 4>2

Process

Identify violations and apply smart fixing

Output

Return true if fixable with ≤1 modification

Key Takeaway

🎯 Key Insight: Count violations first - if more than one, impossible to fix with single modification

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is that we can only have at most one violation to fix. The optimized approach counts violations in a single pass and applies smart context-aware fixing logic. Best approach uses Smart Violation Handling with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Smart Violation Handling	O(n)	O(1)	Count violations and apply smart fixing rules based on context
Brute Force	O(n²)	O(1)	Try modifying each element and check if array becomes non-decreasing

Smart Violation Handling — Algorithm Steps

Step 1: Count violations while traversing array
Step 2: If violations > 1, return false immediately
Step 3: For single violation, apply context-aware fixing logic

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Violations

Track violations while traversing

Context Analysis

Check neighbors to decide fixing strategy

Smart Fix

Apply optimal modification based on context

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int size) {
    int violations = 0;
    
    for (int i = 0; i < size - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            violations++;
            if (violations > 1) {
                return false;
            }
            
            // Smart fixing logic
            if (i == 0) {
                // First element violates, change it
                nums[i] = nums[i + 1];
            } else if (i == size - 2) {
                // Last pair violates, change second-to-last
                nums[i] = nums[i + 1];
            } else if (nums[i - 1] <= nums[i + 1]) {
                // Can fix by changing nums[i] to nums[i+1]
                nums[i] = nums[i + 1];
            } else if (nums[i] <= nums[i + 2]) {
                // Can fix by changing nums[i+1] to nums[i]
                nums[i + 1] = nums[i];
            } else {
                // Neither fix works
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    bool result = solution(nums, size);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to count violations and apply fixes

✓ Linear Growth

Space Complexity

O(1)

Only using counter and index variables

✓ Linear Space

180.0K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Smart Violation Handling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler