Remove One Element to Make the Array Strictly Increasing

🏠 ⬅️ ➡️

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 <= 1000
  • 1 <= nums[i] <= 1000
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: nums(4)

    nums = [1, 2, 10, 5, 7]
    write(*, '(L1)') canBeIncreasing([1, 2, 10, 5, 7])
    nums = [2, 3, 1, 2]
    write(*, '(L1)') canBeIncreasing([2, 3, 1, 2])
    nums = [1, 1, 1]
    write(*, '(L1)') canBeIncreasing([1, 1, 1])

contains

    logical function canBeIncreasing(nums)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: i

        canBeIncreasing = .true.
        do i = 2, size(nums)
            if (nums(i - 1) >= nums(i)) then
                canBeIncreasing = .false.
                exit
            end if
        end do
    end function canBeIncreasing
end program main
❌ Compiled
❌ Executed
❌ Correct 
module strict_increasing
implicit none
contains

function can_be_strictly_increasing(nums) result(output)
integer, intent(in) :: nums(:)
logical :: output
integer :: i

output = .true.

do i = 2, size(nums)
    if (nums(i) <= nums(i-1)) then
        output = .false.
        exit
    end if
end do

if (output) then
    do i = 1, size(nums)-1
        if (nums(i) >= nums(i+1)) then
            output = .false.
            exit
        end if
    end do
end if

end function can_be_strictly_increasing

end module strict_increasing

program test_strict_increasing
use strict_increasing
implicit none

integer, parameter :: nums1(4) = [1, 2, 10, 5, 7]
integer, parameter :: nums2(4) = [2, 3, 1, 2]
integer, parameter :: nums3(3) = [1, 1, 1]

write (*,*) can_be_strictly_increasing(nums1)
write (*,*) can_be_strictly_increasing(nums2)
write (*,*) can_be_strictly_increasing(nums3)

end program test_strict_increasing
🌐 Data from online sources 
def canBeIncreasing(nums):
    count = 0
    for i in range(1, len(nums)):
        if nums[i - 1] >= nums[i]:
            count += 1
            if count > 1: return False
            if i > 1 and nums[i - 2] >= nums[i] and i < len(nums) - 1 and nums[i - 1] >= nums[i + 1]: return False
    return True

We start by initializing a counter variable count to keep track of the number of non-increasing sequences we find in the array nums. We iterate through the array starting from index 1 till the end of the array, and at each index, we check if the current element is greater than or equal to the previous element. If we find such elements, we increment the count by 1. We return false if count is greater than 1, as we can only remove exactly one element.

We also need to handle a special case: if removing the current element doesn't make the subarray strictly increasing, we return false. This happens if the element before the previous element is greater than or equal to the current element and the previous element is greater than or equal to the next element.

If we pass through the array without finding either of these conditions, we return true.

🌐 Data from online sources 
bool canBeIncreasing(vector<int>& nums) {
    int count = 0;
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i - 1] >= nums[i]) {
            count++;
            if (count > 1) return false;
            if (i > 1 && nums[i - 2] >= nums[i] && i < nums.size() - 1 && nums[i - 1] >= nums[i + 1]) return false;
        }
    }
    return true;
}

We start by initializing a counter variable count to keep track of the number of non-increasing sequences we find in the array nums. We iterate through the array starting from index 1 till the end of the array, and at each index, we check if the current element is greater than or equal to the previous element. If we find such elements, we increment the count by 1. We return false if count is greater than 1, as we can only remove exactly one element.

We also need to handle a special case: if removing the current element doesn't make the subarray strictly increasing, we return false. This happens if the element before the previous element is greater than or equal to the current element and the previous element is greater than or equal to the next element.

If we pass through the array without finding either of these conditions, we return true.