minimum-deletions-to-make-array-beautiful
Intuition\n Describe your first thoughts on how to solve this problem. \n- involves iterating through the input vector, checking adjacent elements for duplicate
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- involves iterating through the input vector, checking adjacent elements for duplicates, and incrementing a deletion counter when necessary.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- OPTIMAL APPROACH:\nThe optimal force approach involves iterating through the input vector, checking adjacent elements for duplicates, and incrementing a deletion counter when necessary. This requires O(n) time, where n is the number of elements in the vector. However, due to the shifting of indices after deletions, the effective complexity could be worse.\n\n- BRUTE Approach:\nThe brute approach employs an unordered map to count occurrences of unique elements. It calculates deletions based on odd occurrence counts, eliminating the need for index adjustments. This solution has a linear O(n) time complexity for counting and requires O(u) space, where u is the number of unique elements in the vector. It is more efficient and avoids unnecessary index manipulations.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- 1\n\n# Code\n```\nclass Solution {\npublic:\n    int minDeletion(vector<int>& nums) {\n\n        int cnt=0;  // Initialize a counter variable to keep track of deletions.\n\n        // Loop through the vector until the second-to-last element.\n        for(int i=0;i<nums.size()-1;i++)\n        {\n            // Check if the current index minus the count of deletions is even and\n            // if the current element is the same as the next element.\n            if((i-cnt)%2==0 && nums[i]==nums[i+1])\n            {\n                cnt++;  // Increment the counter to indicate a deletion.\n            }\n        }\n\n        // Check if the final count of elements after deletions is odd.\n        // If it is odd, it means one more deletion is needed to make it even.\n        if((nums.size()-cnt)%2)\n        {\n            cnt++;  // Increment the counter.\n        }\n\n        return cnt;  // Return the total count of deletions needed.\n    }\n};\n\n```
['Array', 'Ordered Map', 'C++']