🌱 Keegan's Digital Garden

2009. Minimum Number of Operations to Make Array Contiguous

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- removing duplicates by inserting each unique element into a ordered hashset, incrementing our operations counter each time an element is NOT placed in the set 
- we should be able to take the largest and smallest value in the hashset and check if its valid (abs(maxElement, minElement) == size of hashset-1 
- if its not equal, then do *something*

🤔What Did I Struggle With?

expanding and reducing the window size

💡 Explanation of Solution

- Remove duplicates and sort the unique elements using a `set`.
- Use a sliding window:
    - Start with two pointers, `i` and `j`.
    - Expand the window by moving `j` to include elements in a valid range (`nums[j] < nums[i] + n`).
    - Compute the length of the valid subarray as `j - i`.
    - Minimize operations by calculating `n - (j - i)`, where `n` is the original array size.
- The result is the smallest number of operations required to make the array contiguous.

⌛ Complexity Analysis

Time Complexity: O(n log n) due to sorting and sliding window traversal.
Space Complexity: O(n) for storing unique elements.

💻 Implementation of Solution

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int ans = n;
        
        // std::set automatically sorts
        set<int> unique(nums.begin(), nums.end());
        vector<int> newNums;
        for (int num : unique) {
            newNums.push_back(num);
        }
        
        int j = 0;
        for (int i = 0; i < newNums.size(); i++) {
            while (j < newNums.size() && newNums[j] < newNums[i] + n) {
                j++;
            }
            
            int count = j - i;
            ans = min(ans, n - count);
        }
        
        return ans;
    }
};

Graph View