✅C++ | O(N) To O(1) Space
Solution 1: Using Stack
Time Complexity   : O(N)
Space Complexity : O(N).
Solution 2 : Optimal in Space
Time Complexity   : O(N)
Space Complexity : O(1)
If U li
# Solution 1: Using **Stack**

``` C++ []
class Solution
{
	public:
		int minDeletion(vector<int>& nums) 
		{
			int del = 0, i = 0, n = nums.size();

			stack<pair<int, int>> st;  // pair stores prev value and index after shifting

			while(i < n)
			{
				if(!st.empty())
				{
					// index is even and prev and curr value same
					// increment deletion and pop prev element
					if(st.top().second % 2 == 0 && st.top().first == nums[i])
					{
						del++;
						st.pop();
					}
				}

				st.push({nums[i], i - del});
				i++;
			}
			// if size is odd , increment del by 1
			return del + (st.size() % 2) ;
		}
};
```
- Time Complexity   : O(N)
- Space Complexity : O(N).


---




# Solution 2 : Optimal in Space

``` C++ []
class Solution
{
	public:
		int minDeletion(vector<int> &nums) 
		{
			int del = 0, n = nums.size();
			
			for (int i = 0; i < n - 1; i++)
			{
				if ((i - del) % 2 == 0 && nums[i] == nums[i + 1])
					del++;
			}
			
			return del + (n - del) % 2;
		}
};
```

- Time Complexity   : O(N)
- Space Complexity : **O(1)**

# If U like solution please UPVOTE 
💻 If there are any suggestions/questions in my post, comment below 👇
['C']