Remove One Element to Make the Array Strictly Increasing

Easy
1111.

Remove One Element to Make the Array Strictly Increasing

Remove One Element to Make the Array Strictly Increasing is an easy coding problem on arrays and greedy, asked in Amazon and Google interviews.

Return true if deleting exactly one element of nums leaves an array that is strictly increasing — every element smaller than the one after it. Otherwise return false.

If nums is already strictly increasing the answer is true, since deleting any element keeps it that way.

Example 1

Input
nums = [3,8,5,9]
Output
true
Explanation
Deleting 8 leaves [3,5,9].

Example 2

Input
nums = [4,6,2,5]
Output
false
Explanation
Every single deletion still leaves a descent.

Example 3

Input
nums = [7,7]
Output
true
Explanation
Deleting either 7 leaves [7].

Constraints

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canBeIncreasing = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove One Element to Make the Array Strictly Increasing Solution

Remove One Element to Make the Array Strictly Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Remove One Element to Make the Array Strictly Increasing is an easy coding problem on arrays and greedy, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return true if deleting exactly one element of nums leaves an array that is strictly increasing — every element smaller than the one after it. Otherwise return false.

If nums is already strictly increasing the answer is true, since deleting any element keeps it that way.

Example 1

Input: nums = [3,8,5,9]
Output: true
Explanation: Deleting 8 leaves [3,5,9].

Example 2

Input: nums = [4,6,2,5]
Output: false
Explanation: Every single deletion still leaves a descent.

Example 3

Input: nums = [7,7]
Output: true
Explanation: Deleting either 7 leaves [7].

Constraints

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

Hints for Remove One Element to Make the Array Strictly Increasing

  1. Hint 1

    Walk left to right and look for the first place where nums[i - 1] >= nums[i].

  2. Hint 2

    At such a conflict you must delete one of the two. Two conflicts that need two deletions mean false.

  3. Hint 3

    Prefer deleting nums[i - 1] (it keeps the last kept value small) — but only if nums[i - 2] < nums[i]; otherwise delete nums[i].

How to solve Remove One Element to Make the Array Strictly Increasing

Scan once, remembering the last value kept. The first conflict forces a deletion, and the better choice is the one that leaves the smaller last value, as long as it keeps the prefix increasing.

Approach

  1. Set prev = nums[0] and removed = false.
  2. For each i >= 1: if nums[i] > prev, set prev = nums[i] and continue.
  3. Otherwise, if removed is already true, return false; set removed = true.
  4. If i == 1 or nums[i - 2] < nums[i], delete nums[i - 1] by setting prev = nums[i]; else delete nums[i] by leaving prev unchanged.
  5. Return true after the scan.

Why it works

Before the first conflict nothing has been deleted, so the kept prefix is nums[0..i-1] and the element before nums[i - 1] is nums[i - 2]. Deleting nums[i - 1] is allowed only if nums[i - 2] < nums[i], and when it is allowed it leaves the last kept value nums[i] <= nums[i - 1], which can only make the rest easier. Any later conflict needs a second deletion, so it means false.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Strictly increasing: equal neighbours are a conflict.
  • Deleting nums[i - 1] without checking nums[i - 2] < nums[i] wrongly accepts [5,6,1,2]; always deleting nums[i] instead wrongly rejects [1,9,3,4], where 9 is the one to drop.
  • Do not modify the input array in languages where it is shared with the caller — track prev instead.

Reference solution

Python

from typing import List

def canBeIncreasing(nums: List[int]) -> bool:
    prev = nums[0]
    removed = False
    for i in range(1, len(nums)):
        if nums[i] > prev:
            prev = nums[i]
            continue
        if removed:
            return False
        removed = True
        if i == 1 or nums[i - 2] < nums[i]:
            prev = nums[i]
    return True

Java

public static boolean canBeIncreasing(int[] nums) {
    int prev = nums[0];
    boolean removed = false;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > prev) {
            prev = nums[i];
            continue;
        }
        if (removed) return false;
        removed = true;
        if (i == 1 || nums[i - 2] < nums[i]) prev = nums[i];
    }
    return true;
}

C++

bool canBeIncreasing(vector<int>& nums) {
    int prev = nums[0];
    bool removed = false;
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] > prev) {
            prev = nums[i];
            continue;
        }
        if (removed) return false;
        removed = true;
        if (i == 1 || nums[i - 2] < nums[i]) prev = nums[i];
    }
    return true;
}

JavaScript

var canBeIncreasing = function(nums) {
    var prev = nums[0], removed = false;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] > prev) {
            prev = nums[i];
            continue;
        }
        if (removed) return false;
        removed = true;
        if (i === 1 || nums[i - 2] < nums[i]) prev = nums[i];
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms