What is the time complexity of Non-decreasing Array?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Non-decreasing Array?

This problem uses Array. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Non-decreasing Array?

Insight 1: The core idea is to iterate through the array and check for violations of the non-decreasing order (nums[i] > nums[i+1]). Insight 2: When a violation is found, we have two options: either modify nums[i] or nums[i+1] to resolve the violation. Choosing the correct one is crucial.

Which companies ask LeetCode 665. Non-decreasing Array in interviews?

This problem is frequently asked at Cashfree.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Non-decreasing Array - LeetCode 665 Solution

Q: How to solve Non-decreasing Array?

The provided solution iterates through the array, checking for instances where `nums[i] > nums[i+1]`. If such an instance is found, it increments the `modifications` counter. If the counter exceeds 1, it immediately returns `false`. The crucial part is deciding how to modify the array. The code checks if `i > 0` and `nums[i-1] > nums[i+1]`. If this condition is true, it means modifying `nums[i]` is not a good option as it will not solve the non-decreasing property with respect to the previous number `nums[i-1]`. Instead, we modify `nums[i+1]` to be equal to `nums[i]`. Otherwise, it means modifying `nums[i]` is the best choice, and sets it equal to `nums[i+1]`. Finally, if it iterates through the whole array without exceeding the one modification limit, it returns `true`.

Non-decreasing Array - Complete Solution Guide

Non-decreasing Array is LeetCode problem 665, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 ). 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 cannot get a non-decreasing array by modifying at most one e

Detailed Explanation

The problem asks us to determine if an array of integers can be made non-decreasing by modifying at most one element. A non-decreasing array is one where each element is less than or equal to the element that follows it (nums[i] <= nums[i+1] for all i). The input is an array of integers `nums`, and the output is a boolean value: `true` if the array can be made non-decreasing with at most one modification, and `false` otherwise. The constraints are that the array length is between 1 and 10,000, and the integer values are between -100,000 and 100,000.

Solution Approach

The provided solution iterates through the array, checking for instances where `nums[i] > nums[i+1]`. If such an instance is found, it increments the `modifications` counter. If the counter exceeds 1, it immediately returns `false`. The crucial part is deciding how to modify the array. The code checks if `i > 0` and `nums[i-1] > nums[i+1]`. If this condition is true, it means modifying `nums[i]` is not a good option as it will not solve the non-decreasing property with respect to the previous number `nums[i-1]`. Instead, we modify `nums[i+1]` to be equal to `nums[i]`. Otherwise, it means modifying `nums[i]` is the best choice, and sets it equal to `nums[i+1]`. Finally, if it iterates through the whole array without exceeding the one modification limit, it returns `true`.

Step-by-Step Algorithm

Step 1: Initialize a variable `modifications` to 0. This variable will track the number of modifications made to the array.
Step 2: Iterate through the array from index 0 to `len(nums) - 2`. In each iteration, compare `nums[i]` with `nums[i + 1]`.
Step 3: If `nums[i] > nums[i + 1]`, a violation of the non-decreasing order is found.
Step 4: Check if `modifications > 0`. If it is, it means we have already made one modification, and making another would exceed the limit, so return `false`.
Step 5: Increment `modifications` by 1.
Step 6: Determine which element to modify: `nums[i]` or `nums[i + 1]`. If `i > 0` and `nums[i - 1] > nums[i + 1]`, then modifying `nums[i]` to `nums[i+1]` is not feasible because it violates non-decreasing order between `nums[i-1]` and `nums[i]`. So set `nums[i + 1] = nums[i]`. Otherwise, set `nums[i] = nums[i + 1]`.
Step 7: After iterating through the entire array, if the number of `modifications` is at most 1, return `true`.

Key Insights

Insight 1: The core idea is to iterate through the array and check for violations of the non-decreasing order (nums[i] > nums[i+1]).
Insight 2: When a violation is found, we have two options: either modify nums[i] or nums[i+1] to resolve the violation. Choosing the correct one is crucial.
Insight 3: We need to keep track of the number of modifications made. If we encounter more than one violation, the array cannot be made non-decreasing with a single modification.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array.

Companies

Asked at: Cashfree.

Non-decreasing Array | LeetCode 665

Medium

Array

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public boolean checkPossibility(int[] nums) {
        int modifications = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (modifications > 0) {
                    return false;
                }
                modifications++;
                if (i > 0 && nums[i - 1] > nums[i + 1]) {
                    nums[i + 1] = nums[i];
                } else {
                    nums[i] = nums[i + 1];
                }
            }
        }
        return true;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 665: Non-decreasing Array - Detailed explanation and solution approaches.

Topics

Array

Companies

Cashfree

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:665

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize a variable `modifications` to 0. This variable will track the number of modifications made to the array.
2
Step 2: Iterate through the array from index 0 to `len(nums) - 2`. In each iteration, compare `nums[i]` with `nums[i + 1]`.
3
Step 3: If `nums[i] > nums[i + 1]`, a violation of the non-decreasing order is found.
4
Step 4: Check if `modifications > 0`. If it is, it means we have already made one modification, and making another would exceed the limit, so return `false`.
5
Step 5: Increment `modifications` by 1.
6
Step 6: Determine which element to modify: `nums[i]` or `nums[i + 1]`. If `i > 0` and `nums[i - 1] > nums[i + 1]`, then modifying `nums[i]` to `nums[i+1]` is not feasible because it violates non-decreasing order between `nums[i-1]` and `nums[i]`. So set `nums[i + 1] = nums[i]`. Otherwise, set `nums[i] = nums[i + 1]`.
7
Step 7: After iterating through the entire array, if the number of `modifications` is at most 1, return `true`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because we iterate through the array once. The space complexity is O(1) because we only use a constant amount of extra space for variables like `modifications` and the loop counter `i`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Creating a copy and sorting

Create a copy of the array, sort it, and compare the original and sorted arrays. Count the number of differences. If the difference is at most 2, it's possible to make the array non-decreasing with one modification.

Time: O(n log n)Space: O(n)

Trade-offs: This approach is less efficient in terms of time complexity due to sorting. It also uses extra space to store the sorted array. However, it can be easier to understand for beginners. The main solution's O(n) time complexity is preferred.

✨

Key Insights

1Insight 1: The core idea is to iterate through the array and check for violations of the non-decreasing order (nums[i] > nums[i+1]).
2Insight 2: When a violation is found, we have two options: either modify nums[i] or nums[i+1] to resolve the violation. Choosing the correct one is crucial.
3Insight 3: We need to keep track of the number of modifications made. If we encounter more than one violation, the array cannot be made non-decreasing with a single modification.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Empty array or array with a single element. The loop doesn't run and it returns true, which is correct as these are considered non-decreasing.
Edge case 2: Array that is already non-decreasing. The `if` condition is never met, and the function returns `true` after the loop, which is correct.
Edge case 3: Array with a single decreasing pair in the beginning like [3,1,2]. In the first iteration, modifications=1, and i=0, nums[i-1] doesn't exist, so the else is executed, and nums[0] is set to 1 making it [1,1,2], which is valid.
Edge case 4: Array with a single decreasing pair in the end like [1,2,0]. In the second iteration, modifications=1, and i=1, nums[0] = 1, and nums[2] = 0, so nums[0]>nums[2], so nums[2] becomes 2 resulting in [1,2,2] which is correct.
Edge case 5: Array with multiple decreasing pairs but can be fixed with one modification, for example [5, -1, 0, 2, 3] . After first modification it becomes [-1, -1, 0, 2, 3] , which is valid non-decreasing array.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the edge case where the violation occurs at the beginning of the array correctly. The `i > 0` check is crucial.

✗Common mistake 2: Incorrectly deciding which element to modify (`nums[i]` or `nums[i + 1]`). The logic to compare `nums[i - 1]` and `nums[i + 1]` is essential to make the right choice.

✗Common mistake 3: Returning `false` prematurely without considering the possibility that the array can be made non-decreasing after the current modification.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data analysis. Ensuring that a dataset is mostly sorted is a common requirement. This algorithm could be used to quickly check if a dataset is nearly sorted and can be made fully sorted with minimal effort.

🏦Real-world scenario 2: Database indexing. Maintaining sorted indices is important for efficient query processing. This algorithm could be used to detect and correct minor inconsistencies in an index with minimal restructuring.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 4, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Non-decreasing Array"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?