Remove One Element to Make the Array Strictly Increasing solution and explanation
9 more videos on this problem
1909. Remove One Element to Make the Array Strictly Increasing - Leetcode Biweekly Contest 55Haridas Dutt · 7:43 · 7K views
1909. Remove One Element to Make the Array Strictly Increasing (Leetcode Easy)Programming Live with Larry · 4:59 · 3K views
Leetcode 1909 - Remove One Element to Make the Array Strictly IncreasingCoder in Process · 13:25 · 2K views
LeetCode 1909. Remove One Element to Make the Array Strictly IncreasingSakura Programming · 4:14 · 2K views
Leetcode |Easy |1909. Remove One Element to Make the Array Strictly Increasing|Time: O(N)|JavascriptSoftware Interviews Prep · 10:04 · 611 views
1909. Remove One Element to Make the Array Strictly Increasing | IN JAVA #leetcode #javaLearn2Master · 11:52 · 520 views
L-8 | Remove One Element to Make the Array Strictly Increasing | LeetCode - 1909 | Aditya GoyalAditya Goyal · 24:06 · 437 views
LeetCode 1909 | Remove One Element to Make the Array Strictly Increasing | Array | Debug | JavaSleepy Cracker · 6:49 · 427 views
Remove One Element to Make the Array Strictly Increasing #javainterview #javaprogramming #leetcodeCodeVia · 3:41 · 386 views
LeetCode 1909: Remove One Element to Make the Array Strictly IncreasingAriesh Codes · 14:02 · 333 views
The problem
Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true.
The array nums is strictly increasing if nums[i - 1] < nums[i] for each index (1 <= i < nums.length).
Example 1:
Input: nums = [1,2,10,5,7] Output: true Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7]. [1,2,5,7] is strictly increasing, so return true.
Example 2:
Input: nums = [2,3,1,2] Output: false Explanation: [3,1,2] is the result of removing the element at index 0. [2,1,2] is the result of removing the element at index 1. [2,3,2] is the result of removing the element at index 2. [2,3,1] is the result of removing the element at index 3. No resulting array is strictly increasing, so return false.
Example 3:
Input: nums = [1,1,1] Output: false Explanation: The result of removing any element is [1,1]. [1,1] is not strictly increasing, so return false.
Constraints:
2 <= nums.length <= 10001 <= nums[i] <= 1000
Approach overview
Problem Overview: Given an integer array, determine whether removing exactly one element (or possibly none) can make the sequence strictly increasing. The final array must satisfy nums[i] < nums[i+1] for every adjacent pair.
Approach 1: Simulated Removal (O(n^2) time, O(1) space)
The straightforward method tries removing each index and checks whether the remaining array is strictly increasing. For every position i, skip that element and iterate through the rest while verifying nums[j] < nums[j+1]. If any simulated removal produces a valid sequence, return true. This approach is easy to reason about and useful for verifying correctness, but it scans the array repeatedly, which leads to quadratic time complexity.
Approach 2: Direct Iteration and Check (O(n) time, O(1) space)
A single pass greedy check is enough. Iterate through the array and count violations where nums[i] <= nums[i-1]. A strictly increasing array can have at most one such violation if removing one element fixes it. When a violation appears, decide which element to logically remove: either the previous element or the current one. Compare nums[i] with nums[i-2] to determine if removing the previous element keeps the sequence valid; otherwise treat the current element as removed. If more than one violation occurs, forming a strictly increasing sequence with one removal is impossible.
This greedy observation works because only local comparisons determine whether the increasing property breaks. Once you encounter more than one invalid pair, no single deletion can repair the entire sequence.
Recommended for interviews: The direct iteration approach is the expected solution. It runs in O(n) time with O(1) extra space and shows you understand greedy reasoning on arrays. Simulated removal is acceptable as a first thought, but interviewers usually expect the linear scan optimization.
Problems like this commonly appear in array and greedy pattern discussions, where a single pass detects structural violations. Similar logic also appears in some two pointers style validation problems.
Approach 1: Direct Iteration and Check
This approach involves iterating through the array to find any violation of the strictly increasing condition. If a violation is found, we check if removing either of the elements involved in this violation (the current one or the previous one) resolves the issue. We maintain a count of such violations and decide the result based on this count.
def canBeIncreasing(nums):
violations = 0
for i in range(1, len(nums)):
if nums[i - 1] >= nums[i]:
violations += 1
if violations > 1:
return False
if i > 1 and nums[i - 2] >= nums[i] and (i + 1 < len(nums) and nums[i - 1] >= nums[i + 1]):
return False
return Trueclass Solution {
public boolean canBeIncreasing(int[] nums) {
int violations = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] >= nums[i]) {
violations++;
if (violations > 1) return false;
if (i > 1 && nums[i - 2] >= nums[i] && nums[i - 1] >= nums[i + 1])
return false;
}
}
return true;
}
}#include <vector>
using namespace std;
bool canBeIncreasing(vector<int>& nums) {
int violations = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] >= nums[i]) {
violations++;
if (violations > 1) return false;
if (i > 1 && nums[i - 2] >= nums[i] && nums[i - 1] >= nums[i + 1])
return false;
}
}
return true;
}function canBeIncreasing(nums) {
let violations = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i - 1] >= nums[i]) {
violations++;
if (violations > 1) return false;
if (i > 1 && nums[i - 2] >= nums[i] && nums[i - 1] >= (nums[i + 1] || Infinity))
return false;
}
}
return true;
}#include <stdbool.h>
bool canBeIncreasing(int* nums, int numsSize) {
int violations = 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i - 1] >= nums[i]) {
violations++;
if (violations > 1) return false;
if (i > 1 && nums[i - 2] >= nums[i] && nums[i - 1] >= nums[i + 1])
return false;
}
}
return true;
}public class Solution {
public bool CanBeIncreasing(int[] nums) {
int violations = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i - 1] >= nums[i]) {
violations++;
if (violations > 1) return false;
if (i > 1 && nums[i - 2] >= nums[i] && (i + 1 < nums.Length && nums[i - 1] >= nums[i + 1]))
return false;
}
}
return true;
}
}Using list iteration, this checks for and counts violations. An explicit check for prior and posterior neighbors ensures the feasibility of making the array strictly increasing through a single removal.
Time complexity: O(n). Space complexity: O(1) due to basic counter usage.
Approach 2: Simulated Removal
By simulating the removal of each element one by one, we can explicitly check if the array becomes strictly increasing with that removal. This involves a straightforward check but iterated for each index.
def is_strictly_increasing(nums, skip):
for i in range(1, len(nums)):
if i == skip:
continue
prev = i - 2 if i - 1 == skip else i - 1
if prev >= 0 and nums[prev] >= nums[i]:
return False
return True
def canBeIncreasing(nums):
for i in range(len(nums)):
if is_strictly_increasing(nums, i):
return True
return Falseclass Solution {
private boolean isStrictlyIncreasing(int[] nums, int skip) {
for (int i = 1; i < nums.length; i++) {
if (i == skip) continue;
int prev = (i - 1 == skip) ? (i - 2) : (i - 1);
if (prev >= 0 && nums[prev] >= nums[i])
return false;
}
return true;
}
public boolean canBeIncreasing(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (isStrictlyIncreasing(nums, i))
return true;
}
return false;
}
}#include <vector>
#include <algorithm>
using namespace std;
bool isStrictlyIncreasing(const vector<int>& nums, int skip) {
for (int i = 1; i < nums.size(); i++) {
if (i == skip) continue;
int previous = (i - 1 == skip) ? (i - 2) : (i - 1);
if (previous >= 0 && nums[previous] >= nums[i])
return false;
}
return true;
}
bool canBeIncreasing(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
if (isStrictlyIncreasing(nums, i))
return true;
}
return false;
}function isStrictlyIncreasing(nums, skip) {
for (let i = 1; i < nums.length; i++) {
if (i === skip) continue;
let previous = (i - 1 === skip) ? (i - 2) : (i - 1);
if (previous >= 0 && nums[previous] >= nums[i]) {
return false;
}
}
return true;
}
function canBeIncreasing(nums) {
for (let i = 0; i < nums.length; i++) {
if (isStrictlyIncreasing(nums, i)) {
return true;
}
}
return false;
}#include <stdbool.h>
bool isStrictlyIncreasing(int* nums, int size, int skip) {
for (int i = 1; i < size; i++) {
if (i == skip) continue;
int previous = (i - 1 == skip) ? (i - 2) : (i - 1);
if (previous >= 0 && nums[previous] >= nums[i])
return false;
}
return true;
}
bool canBeIncreasing(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
if (isStrictlyIncreasing(nums, numsSize, i))
return true;
}
return false;
}public class Solution {
private bool IsStrictlyIncreasing(int[] nums, int skip) {
for (int i = 1; i < nums.Length; i++) {
if (i == skip) continue;
int prev = (i - 1 == skip) ? (i - 2) : (i - 1);
if (prev >= 0 && nums[prev] >= nums[i])
return false;
}
return true;
}
public bool CanBeIncreasing(int[] nums) {
for (int i = 0; i < nums.Length; i++) {
if (IsStrictlyIncreasing(nums, i))
return true;
}
return false;
}
}This solution thoroughly tests each element as a removal candidate and ensures that strict increasing conditions are maintained via intelligent index tracking and condition branching.
Time complexity: O(n^2); Space complexity: O(1).
Approach 3: Traversal
We can traverse the array to find the first position i where nums[i] < nums[i+1] is not satisfied. Then, we check if the array is strictly increasing after removing either i or i+1. If it is, we return true; otherwise, we return false.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function canBeIncreasing(nums: number[]): boolean {
const n = nums.length;
const check = (k: number): boolean => {
let pre = 0;
for (let i = 0; i < n; ++i) {
if (i === k) {
continue;
}
if (pre >= nums[i]) {
return false;
}
pre = nums[i];
}
return true;
};
let i = 0;
while (i + 1 < n && nums[i] < nums[i + 1]) {
++i;
}
return check(i) || check(i + 1);
}func canBeIncreasing(nums []int) bool {
check := func(k int) bool {
pre := 0
for i, x := range nums {
if i == k {
continue
}
if pre >= x {
return false
}
pre = x
}
return true
}
i := 0
for i+1 < len(nums) && nums[i] < nums[i+1] {
i++
}
return check(i) || check(i+1)
}impl Solution {
pub fn can_be_increasing(nums: Vec<i32>) -> bool {
let check = |k: usize| -> bool {
let mut pre = 0;
for (i, &x) in nums.iter().enumerate() {
if i == k {
continue;
}
if pre >= x {
return false;
}
pre = x;
}
true
};
let mut i = 0;
while i + 1 < nums.len() && nums[i] < nums[i + 1] {
i += 1;
}
check(i) || check(i + 1)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct Iteration and Check | Time complexity: O(n). Space complexity: O(1) due to basic counter usage. |
| Simulated Removal | Time complexity: O(n^2); Space complexity: O(1). |
| Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Removal | O(n^2) | O(1) | Good for initial reasoning or brute-force validation of the rule |
| Direct Iteration and Check (Greedy) | O(n) | O(1) | Optimal approach for interviews and production code |
Frequently asked questions
Is Remove One Element to Make the Array Strictly Increasing easy or hard?
The problem is classified as Easy, but many developers struggle with the edge cases. Correctly deciding which element to remove when a violation occurs requires careful comparison with earlier values. Once the greedy insight is clear, the implementation is short and efficient.
Remove One Element to Make the Array Strictly Increasing Python/Java solution
Both Python and Java implementations follow the same linear scan strategy. Iterate once, count violations where nums[i] <= nums[i-1], and adjust logically by skipping either the previous or current element. The algorithm keeps O(n) time and O(1) space regardless of language.
How to solve Remove One Element to Make the Array Strictly Increasing in O(n)?
Traverse the array and track positions where nums[i] <= nums[i-1]. If more than one such violation appears, return false. For the first violation, check whether removing nums[i-1] or nums[i] preserves the order by comparing with nums[i-2]. This greedy decision allows the problem to be solved in a single pass.
What is the best approach for Remove One Element to Make the Array Strictly Increasing?
The best approach is a greedy single-pass scan. Iterate through the array and detect violations where nums[i] <= nums[i-1]. Allow at most one violation and decide whether removing the current or previous element maintains the increasing property. This solution runs in O(n) time and O(1) space.
Is Remove One Element to Make the Array Strictly Increasing asked at Google/Amazon/Meta?
Array validation and greedy correction problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests edge case reasoning, single-pass array processing, and the ability to minimize modifications while preserving ordering constraints.
What data structure is used in Remove One Element to Make the Array Strictly Increasing?
The problem mainly uses a simple array traversal with constant extra variables. No advanced data structures are required. The logic relies on comparisons between adjacent elements and greedy decision making.
What is the time complexity of Remove One Element to Make the Array Strictly Increasing?
The optimal algorithm runs in O(n) time because it scans the array once while tracking violations of the strictly increasing condition. Space complexity is O(1) since only a few variables are used. A brute-force simulated removal approach takes O(n^2) time.