Minimum Pair Removal to Sort Array II

• 1. Initialize operations = 0 and convert the input array nums into a java.util.List<Long> to handle large numbers and potential overflows.
• 2. Start an infinite loop that will be broken once the list is sorted.
• 3. Inside the loop, first check if the current list is sorted in non-decreasing order. If it is, break the loop.
• 4. If not sorted, iterate through all adjacent pairs in the list to find the one with the minimum sum. Keep track of this minimum sum and the index of the first element of the pair (minIndex).
• 5. Perform the merge operation: calculate the sum of the elements at minIndex and minIndex + 1. Update the element at minIndex with this sum and remove the element at minIndex + 1.
• 6. Increment the operations counter.
• 7. Once the loop terminates, return the total operations count.

The brute-force simulation is the most straightforward way to solve the problem. We use a List<Long> to store the numbers, which allows for dynamic resizing and prevents integer overflow when summing up large numbers.

The simulation proceeds in a loop. In each iteration, we first need to determine if we should stop. This is done by a helper function isSorted, which traverses the list to check if list[i] >= list[i-1] for all i. If the list is sorted, we exit the loop.

If the list is not yet sorted, we proceed with one operation. We iterate through all adjacent pairs from the beginning of the list, calculating their sum and keeping track of the minimum sum found so far, along with the index of that pair. The problem specifies that if there's a tie in sums, the leftmost pair should be chosen, which is naturally handled by a simple linear scan from left to right.

After finding the pair (list[minIndex], list[minIndex+1]) with the minimum sum, we replace them with their sum. In an ArrayList, this involves updating the value at minIndex and removing the element at minIndex+1. Each such merge constitutes one operation, so we increment our counter.

This cycle of checking, finding the minimum, and merging continues until the list is non-decreasing.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int minOperations(int[] nums) {6        if (nums.length <= 1) {7            return 0;8        }9 10        List<Long> currentNums = new ArrayList<>();11        for (int num : nums) {12            currentNums.add((long) num);13        }14 15        int operations = 0;16        while (true) {17            if (isSorted(currentNums)) {18                break;19            }20 21            long minSum = Long.MAX_VALUE;22            int minIndex = -1;23 24            for (int i = 0; i < currentNums.size() - 1; i++) {25                long currentSum = currentNums.get(i) + currentNums.get(i + 1);26                if (currentSum < minSum) {27                    minSum = currentSum;28                    minIndex = i;29                }30            }31 32            long val1 = currentNums.get(minIndex);33            long val2 = currentNums.get(minIndex + 1);34            currentNums.set(minIndex, val1 + val2);35            currentNums.remove(minIndex + 1);36            operations++;37        }38 39        return operations;40    }41 42    private boolean isSorted(List<Long> nums) {43        for (int i = 1; i < nums.size(); i++) {44            if (nums.get(i) < nums.get(i - 1)) {45                return false;46            }47        }48        return true;49    }50}

• 1. Initialization:
  • Create a Doubly Linked List (DLL) from nums, where each node stores its value and a unique ID (its original index). Add sentinel head and tail nodes.
  • Create a Min-Priority Queue to store Pair objects. A Pair contains a sum and a reference to the first Node of the pair.
  • Populate the PQ with all initial adjacent pairs from the DLL.
  • Compute the initial number of inversions (where node.val > node.next.val).
• 2. Simulation Loop: Continue as long as inversions > 0.
  • a. Extract the Pair with the minimum sum from the PQ.
  • b. Staleness Check: Verify the extracted pair is still valid. A pair is stale if its nodes have been removed or if their values have changed such that their current sum doesn't match the sum stored in the Pair. If stale, discard and continue to the next pair in the PQ.
  • c. Merge: If the pair (u, v) is valid:
    • Increment operations count.
    • Update the inversions count: decrement for inversions removed by the merge, and increment for any new inversions created.
    • Update the DLL: set u.val = u.val + v.val, and bypass v by setting u.next = v.next. Mark v as removed.
    • Update the PQ: Add new pairs formed by the updated node u and its new neighbors (u.prev, u.next).
• 3. Termination: When the loop finishes (inversions is 0), return the total operations.

To overcome the O(N^2) complexity of the naive simulation, we need to speed up two key steps: finding the minimum sum pair and checking for the sorted condition.

• Finding Minimum Sum Pair: A min-priority queue (min-heap) is perfect for this. We store objects representing each adjacent pair's sum and a reference to the pair's first node. This lets us retrieve the minimum sum pair in O(log N) time.

• Efficient Merging: An ArrayList is slow for removals in the middle. A doubly linked list (DLL) is ideal here. Each number is a node in the DLL. Merging a pair (u, v) involves updating u.val, changing u.next to point to v.next, and updating the back-pointer of v.next. This is an O(1) operation.

• Checking Sorted Condition: Linearly scanning the list in each step is too slow. Instead, we can maintain a counter for the number of inversions (places where node.val > node.next.val). We initialize this count once. After each merge, we only need to check the newly formed adjacent pairs to update the inversion count in O(1) time. The simulation runs until inversions becomes 0.

• Handling Stale Data: When we merge a pair, the pairs involving its neighbors become invalid. Instead of trying to find and remove these from the priority queue (which is inefficient), we simply add the new pairs. When we extract a pair from the PQ, we perform a staleness check. A pair is stale if one of its nodes has been removed or if the sum of the current values of its nodes doesn't match the sum stored in the PQ. We discard stale pairs and process the next one.

1import java.util.PriorityQueue;2 3class Solution {4    static class Node {5        long val;6        Node prev, next;7        int id; // Unique identifier for the node, e.g., original index8        Node(long val, int id) {9            this.val = val;10            this.id = id;11        }12    }13 14    static class Pair implements Comparable<Pair> {15        long sum;16        Node node; // The first node of the pair17        18        Pair(long sum, Node node) {19            this.sum = sum;20            this.node = node;21        }22 23        @Override24        public int compareTo(Pair other) {25            if (this.sum != other.sum) {26                return Long.compare(this.sum, other.sum);27            }28            // Tie-breaking: choose the leftmost pair29            return Integer.compare(this.node.id, other.node.id);30        }31    }32 33    public int minOperations(int[] nums) {34        if (nums.length <= 1) return 0;35 36        Node head = new Node(0, -1);37        Node tail = new Node(0, nums.length);38        Node curr = head;39        40        int inversions = 0;41        Node[] nodes = new Node[nums.length];42        for (int i = 0; i < nums.length; i++) {43            nodes[i] = new Node(nums[i], i);44            curr.next = nodes[i];45            nodes[i].prev = curr;46            curr = nodes[i];47            if (i > 0 && nodes[i-1].val > nodes[i].val) {48                inversions++;49            }50        }51        curr.next = tail;52        tail.prev = curr;53 54        PriorityQueue<Pair> pq = new PriorityQueue<>();55        for (int i = 0; i < nums.length - 1; i++) {56            pq.add(new Pair(nodes[i].val + nodes[i+1].val, nodes[i]));57        }58 59        int operations = 0;60        boolean[] removed = new boolean[nums.length];61 62        while (inversions > 0 && !pq.isEmpty()) {63            Pair p = pq.poll();64            Node u = p.node;65            66            if (removed[u.id] || u.next == tail) continue;67            68            Node v = u.next;69            if (removed[v.id]) continue;70 71            // Stale pair check72            if (u.val + v.val != p.sum) continue;73 74            operations++;75 76            // Update inversions before merge77            if (u.prev != head && u.prev.val > u.val) inversions--;78            if (u.val > v.val) inversions--;79            if (v.next != tail && v.val > v.next.val) inversions--;80 81            // Perform merge82            u.val += v.val;83            removed[v.id] = true;84            u.next = v.next;85            v.next.prev = u;86 87            // Update inversions after merge88            if (u.prev != head && u.prev.val > u.val) inversions++;89            if (u.next != tail && u.val > u.next.val) inversions++;90 91            // Add new pairs to PQ92            if (u.prev != head) {93                pq.add(new Pair(u.prev.val + u.val, u.prev));94            }95            if (u.next != tail) {96                pq.add(new Pair(u.val + u.next.val, u));97            }98        }99 100        return operations;101    }102}