Given an integer array arr[] of size n, the task is to check if the given array can be made strictly increasing after removing at most one element from the array. Return true if it is possible to make the given array strictly increasing else return false. Note: If the given array is already strictly increasing then simply return true.
- A strictly increasing array means that for every nums[i] and nums[i + 1], the relationship nums[i] < nums[i + 1] holds.
Example:
Input: arr[] = {1, 2, 12, 5, 7}
Output: true
Explanation: By removing 12 from index 2, the array becomes {1, 2, 5, 7}
which is strictly increasing.
Input: arr[] = {1, 4, 5, 3, 2}
Output: false
Explanation: By removing any element of the array it is not possible to make
it strictly increasing.
Input: arr[] = {1, 2, 2, 5, 5}
Output: false
This problem can be solved using multiple approaches and here we are going to understand each of them one by one starting from brute force to optimized one.
Approach 1: Brute Force.
In this approach, we are going to remove each element one by one and then we will check if the resulting array is strictly increasing or not.
Step-by-step explanation:
Step 1: Define a helper function to check if the given array is strictly increasing or not. Return true if the array is strictly increasing, otherwise false.
Step 2: Iterate through the array and simulate removing each element one by one.
Step 3: For each removed element, check if the resulting array is strictly increasing using the helper function.
Step 4: Push the removed element back inside the array if the condition is not satisfied.
Step 5: If any array condition is strictly increasing, we return true, indicating that the array can be made strictly increasing by removing one element.
Step 6: If no such array condition is found even after trying to remove each element, we return false.
Below is the C++ code implementation of the above approach:
//C++ Brute Force Approach to check strictly increasing array #include<iostream> #include <vector> using namespace std; //helper function to check if the array is //strictly increasing or not bool isStrictlyIncreasing(vector<int>& nums) { int n = nums.size(); bool isIncreasing = true; for (int i = 1; i < n; i++) { if (nums[i] <= nums[i - 1]) { isIncreasing = false; break; } } return isIncreasing; } bool canBeIncreasing(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { int removedElement = nums[i]; // Simulate removing the element nums.erase(nums.begin() + i); //calling helper function to check if (isStrictlyIncreasing(nums)) { return true; } // Put back the removed element nums.insert(nums.begin() + i, removedElement); } return false; } int main(){ vector<int> nums{1, 2, 12, 5, 7}; if(canBeIncreasing(nums)) cout<<"True"; else cout<<"False"; return 0; }
True
Time Complexity: The time complexity of this approach is O(n^2), where n is the number of elements in the array. For each element, we check if the resulting array is strictly increasing, which takes O(n) time. As we do this for each element, the overall time complexity becomes O(n^2).
Space Complexity: The space complexity is O(1) as we use only a constant amount of extra space for variables, and we modify the input array in place without using any additional data structures.
Approach 2: Optimized Approach.
Using the brute force approach we are getting a time complexity of O(n^2) but we can easily optimize the above approach and solve in O(n) time complexity.
Step-by-step explanation:
Step 1: Initialize a variable count to keep track of the number of elements that violate the strictly increasing condition.
Step 2: Iterate through the array from index 1 to the end. If the current element is less than or equal to the previous element, it means it violates the strictly increasing condition.
Step 3: Increment the count and check if it becomes greater than 1. If yes, it means we need to remove more than one element to make the array strictly increasing, so we return false.
Step 4: If the count is 1, it means we found one violating element. We then try removing it and checking if the array becomes strictly increasing.
Step 5: To remove the violating element, we have two choices:
- If the current element is greater than the element before the previous element (nums[i] > nums[i - 2]), we remove the current element by setting it equal to the previous element.
- Otherwise, we remove the previous element by setting it equal to the current element.
Step 6: Continue iterating through the array, and if we find any more violating elements, we return false.
Step 7: If we successfully iterate through the entire array without finding any more violating elements, it means we can make the array strictly increasing by removing exactly one element, so we return true.
C++ code implementation of the above approach:
//C++ Optimized Approach to check strictly increasing array #include<iostream> #include <vector> using namespace std; //function to check strictly increasing bool canBeIncreasing(vector<int>& nums) { int n = nums.size(); // Count of violating elements int count = 0; for (int i = 1; i < n; i++) { if (nums[i] <= nums[i - 1]) { count++; if (count > 1) { return false; } // Check if removing the current element makes
//the array strictly increasing if (i == 1 || nums[i] > nums[i - 2]) { nums[i - 1] = nums[i]; } else { nums[i] = nums[i - 1]; } } } return true; } int main(){ vector<int> nums{1, 2, 12, 5, 7}; if(canBeIncreasing(nums)) cout<<"True"; else cout<<"False"; return 0; }
Output:
True
Time Complexity: The time complexity of this solution is O(n), where n is the number of elements in the array. We iterate through the array only once.
Space Complexity: The space complexity is O(1) as we use only a constant amount of extra space for variables.
Trends is an amazing magazine Blogger theme that is easy to customize and change to fit your needs.