Minimum Pair removal to sort an array
IntuitionApproachComplexity
Time complexity:
Best case (already sorted array): O(n log n)
Worst case (needs multiple iterations to sort): O(n^2 log n)
Space com
# Intuition
<!-- First I though to check the array is sorted or not, I created a function for that, and secondly if the array is not sorted we have to go to the function where it checks all the adjacent sums and returns minimum sum of adjacent pairs and its index, this helps in the final function to replace the values with its sum until the array becomes sorted. -->

# Approach
<!-- Split the total problem to small parts so that it is easy to analyse and get effective solution -->

# Complexity
- Time complexity:
- Best case (already sorted array): O(n log n)

Worst case (needs multiple iterations to sort): O(n^2 log n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n) because of the additional space used by the sorted array and the list of adjacent sums.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def adj_pair(self, arr):
        # Find the pair with the smallest sum of adjacent elements
        adj_sums = [arr[i] + arr[i+1] for i in range(len(arr)-1)]
        min_val = min(adj_sums)
        min_ind = adj_sums.index(min_val)
        min_pair = [arr[min_ind], arr[min_ind+1]]
        return min_pair, min_ind
    
    def check_arr(self, arr):
        # Check if the array is sorted in ascending order
        return arr == sorted(arr)
    
    def minimumPairRemoval(self, arr):
        output = 0
        while not self.check_arr(arr):
            output += 1
            # Find the pair with the smallest adjacent sum
            min_pair, min_ind = self.adj_pair(arr)
            sum_adj = sum(min_pair)
            # Replace the pair with the sum in the array
            arr = arr[:min_ind] + [sum_adj] + arr[min_ind+2:]
        return output

# Example usage:
solution = Solution()
result = solution.minimumPairRemoval([2, 2, -1, 3, -2, 2, 1, 1, 1, 0, -1])
print(result)  # Expected output: 9

```
['Python3']