[Python] Optimizing LeetCode's "Minimum Pair Removal to Sort Array II" Solution to Prevent...

I am working on the LeetCode problem 3510. Minimum Pair Removal to Sort Array II:

Given an array nums, perform the following operation any number of times:

• Select the adjacent pair with the minimum sum in nums. If multiple such pairs exist, choose the leftmost one.
• Replace the pair with their sum.

Return the minimum number of operations needed to make the array non-decreasing.

An array is considered non-decreasing if each element is greater than or equal to its previous element (if it exists).

Example 1:


Input: nums = [5,2,3,1]

Output: 2

Explanation:

• The pair (3,1) has the minimum sum of 4. After replacement, nums = [5,2,4].
• The pair (2,4) has the minimum sum of 6. After replacement, nums = [5,6].

The array nums became non-decreasing in two operations.

Example 2:


Input: nums = [1,2,2]

Output: 0

Explanation:

The array nums is already sorted.

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums <= 109
  

​

My Attempt:


I have implemented the following solution:

class Solution:
def minimumPairRemoval(self, nums: List[int]) -> int:
op = 0

def is_sorted(arr):
for i in range(len(arr) - 1):
if arr > arr[i + 1]:
return False
return True

while not is_sorted(nums):
d = {}
i = 0
while i < len(nums) - 1:
d = nums + nums[i + 1]
i += 1
min_key = min(d, key=d.get)
nums.insert(min_key + 2, d[min_key])
del nums[min_key:min_key + 2]
op += 1

return op

Issue:


While this code passes 667 out of 680 test cases, it encounters a Time Limit Exceeded (TLE) error on the remaining cases. The current time complexity is O(n²), which is inefficient for larger inputs. I am seeking assistance in optimizing this code without altering its core logic.

Request:


How can this code be optimized to improve its efficiency and avoid the TLE error, while maintaining the same logic?

Continue reading...