leetcode

commit d8e6f259d79bd329253e723e9768120f68aa56fe
parent 4124df9850734fcc79b3473bc726a67b5b301e4f
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 21 Jan 2026 20:53:47 -0700

3507. minimum pair removal to sort array 1

Diffstat:
A
min_pair_removal_sort_arr1.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
A
min_pair_removal_sort_arr1.py
 | 
44
++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 88 insertions(+), 0 deletions(-)
diff --git a/min_pair_removal_sort_arr1.c b/min_pair_removal_sort_arr1.c
@@ -0,0 +1,44 @@
+// 3507. Minimum Pair Removal to Sort Array I
+#include "leetcode.h"
+
+/*
+ * given an array 'nums', you can 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 o make the array
+ * non-decreasing. an array is said to be non-decreasing if each element is
+ * great than or equal to its previous element (if it exists).
+ */
+
+bool sorted(int *nums, int n) {
+  for (int i = 1; i < n; i++)
+    if (nums[i] < nums[i - 1])
+      return false;
+  return true;
+}
+
+int minimumPairRemoval(int *nums, int numsSize) {
+  int ans = 0;
+  while (!sorted(nums, numsSize)) {
+    ans++;
+    int min_sum = INT_MAX, pos = -1;
+    for (int i = 1; i < numsSize; i++) {
+      int sum = nums[i - 1] + nums[i];
+      if (sum < min_sum) {
+        min_sum = sum;
+        pos = i;
+      }
+    }
+    nums[pos - 1] = min_sum;
+    for (int i = pos; i < numsSize - 1; i++)
+      nums[i] = nums[i + 1];
+    numsSize--;
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {5, 2, 3, 1}, n2[] = {1, 2, 2};
+  printf("%d\n", minimumPairRemoval(n1, ARRAY_SIZE(n1))); // expect: 2
+  printf("%d\n", minimumPairRemoval(n2, ARRAY_SIZE(n2))); // expect: 0
+}
diff --git a/min_pair_removal_sort_arr1.py b/min_pair_removal_sort_arr1.py
@@ -0,0 +1,44 @@
+# 3507. Minimum Pair Removal to Sort Array I
+
+"""
+given an array 'nums', you can 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 o make the array
+non-decreasing. an array is said to be non-decreasing if each element is
+great than or equal to its previous element (if it exists).
+"""
+
+
+class Solution(object):
+    def sorted(self, nums, n):
+        for i in range(1, n):
+            if nums[i] < nums[i - 1]:
+                return False
+        return True
+
+    def minimumPairRemoval(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        ans, n = 0, len(nums)
+        while not self.sorted(nums, n):
+            ans += 1
+            min_sum, pos = float("inf"), -1
+            for i in range(1, n):
+                total = nums[i - 1] + nums[i]
+                if total < min_sum:
+                    min_sum = total
+                    pos = i
+            nums[pos - 1] = min_sum
+            for i in range(pos, n - 1):
+                nums[i] = nums[i + 1]
+            n -= 1
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minimumPairRemoval(nums=[5, 2, 3, 1]))
+    print(obj.minimumPairRemoval(nums=[1, 2, 2]))