Remove One Element to Make the Array Strictly Increasing Solution

by

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.

Example 4:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is already strictly increasing, so return true.

Constraints:

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

Program:

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int n=nums.size();
        int chances=1; //  i have  only one chance to remove a number
        int i=0;
        while(i<nums.size()-1){
            if(nums[i]>=nums[i+1]){
                if(chances==0)return false;
                if(i==0){
                    nums[i]=nums[i+1]-1;
                }
                else{
                    if(nums[i+1]>nums[i-1])nums[i]=nums[i-1];
                    else nums[i+1]=nums[i];
                }
                chances--;
            }
            i++;
        }
        return true;
    }
};

Approach:

While travesring through the array Ill keep checking the strictly increasing  sequence for the condition
and when the condition doesn't satisfy the condition A[i] < A[i+1]:
Then we know for sure that we have to remove either of these two 
here comes the main part i.e, which one to remove when you have a chance to remove both:
then it's always better to remove the first one.
You'll better understand it when you draw them as a graph on the paper

credit : here

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment