2091. Removing Minimum and Maximum From Array

📝 Problem Details

• Title: 2091. Removing Minimum and Maximum From Array
• Link: https://leetcode.com/problems/removing-minimum-and-maximum-from-array/
• Difficulty: Medium
• Tags/Categories: Arrays Greedy

💭What Were My Initial Thoughts?

- two pointers maybe
- decision needs to be made on which direction we choose our deletion of elements from 

🤔What Did I Struggle With?

breaking down the decision tree isnt options that can be greedily chosen

💡 Explanation of Solution

1. iterate through nums to find minimum and maximum
	- find the minimum and maximum elements
	- store their value and their respective indexes

2. calculate minimum deletions based on three possible scenarios
	1. remove both elements from the left
	2. remove both elements from the right
	3. remove one element from the left and one from the right

3. take the minimum value based on the 3 possible options

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
 
public:
    int minimumDeletions(vector<int>& nums) {
        int n = nums.size();  
 
        // Initialize min and max values and their indices
        pair<int, int> minValue = {-1, INT_MAX};
        pair<int, int> maxValue = {-1, INT_MIN};
  
        // Find minimum and maximum elements and their indices
        for (int i = 0; i < n; i++) {
            if (nums[i] < minValue.second)
                minValue = {i, nums[i]};
 
            if (nums[i] > maxValue.second)
                maxValue = {i, nums[i]};
        }
 
        int minIndex = minValue.first;
        int maxIndex = maxValue.first;
  
        // Calculate all options
        // Option 1: Remove both from the left
        int option1 = max(minIndex, maxIndex) + 1;
  
        // Option 2: Remove both from the right
        int option2 = max(n - minIndex, n - maxIndex);
  
        // Option 3: One from left, one from right
        int option3a = minIndex + 1 + (n - maxIndex);
        int option3b = maxIndex + 1 + (n - minIndex);
 
        // Return the minimum of all options
        return min({option1, option2, option3a, option3b}); // C++11 or later
    }
};