We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Pair Removal to Sort Array II

Number: 3772

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array nums, you are allowed to repeatedly perform the following operation:

  • Select the adjacent pair with the minimum sum (if there is more than one such pair, choose the leftmost one).
  • Replace that pair with a single element equal to their sum.

Return the minimum number of operations required so that the resulting array becomes non-decreasing (each element is greater than or equal to the one before it).

Key Insights

  • The order in which pairs are merged is completely predetermined by the rule (always pick the adjacent pair with the smallest sum, with a leftmost tie-break).
  • Merging two adjacent elements decreases the array’s length by one. However, the merge can “fix” inversions (places where the order is decreasing) while potentially creating new adjacent pairs.
  • A simulation that repeatedly merges the correct pair until the array is sorted is needed.
  • To efficiently choose the adjacent pair with the minimum sum at every step, a min-heap (priority queue) is ideal.
  • Maintaining the list in a doubly linked list structure allows efficient merging and neighbor updates.
  • After every merge the “sorted” status of the resulting neighbors can change; careful local updates (or tracking the count of inversions) can help to decide when to stop.

Space and Time Complexity

Time Complexity: O(n log n) in the worst-case (each merge operation uses heap operations that take O(log n) time and there are O(n) merges). Space Complexity: O(n) (for storing the list nodes and priority queue).

Solution

To solve the problem we simulate the merging process with the following main steps:

  1. Represent the array as a doubly linked list so that when two adjacent nodes are merged, the left and right neighbors can be quickly updated.
  2. Use a priority queue to maintain every pair of adjacent nodes. Each pair is stored with its sum along with pointers (or indices) to the nodes. A secondary “serial” value may be used for tie‐breaking.
  3. Initially scan the linked list to add every adjacent pair to the heap.
  4. Repeatedly do:
    • Pop the pair with the smallest sum from the heap.
    • If the pair is no longer valid (i.e. one of the nodes has already been merged), skip it.
    • Merge the two nodes into a new node having a value equal to their sum.
    • Update the doubly linked list by “removing” the merged nodes and inserting the new node in their place.
    • For the two new adjacent relations formed (with the left neighbor and with the right neighbor), compute the new sums and add them to the heap.
  5. Continue this process until the remaining list is non-decreasing.
  6. Return the count of merge operations performed.

This approach ensures we always merge the same adjacent pair as defined by the problem and use efficient data structures to manage the many updates.

Code Solutions

# Define a Node in the doubly linked list
class Node:
    def __init__(self, value):
        self.value = value       # The number stored in this node
        self.prev = None         # Pointer to previous node
        self.next = None         # Pointer to next node
        self.valid = True        # Flag to check if this node is still active

import heapq

def minimumPairRemovalToSort(nums):
    # Create linked list nodes for all numbers.
    nodes = [Node(val) for val in nums]
    n = len(nodes)
    if n <= 1:
        return 0

    # Link all nodes
    for i in range(1, n):
        nodes[i].prev = nodes[i - 1]
        nodes[i - 1].next = nodes[i]

    # Priority queue for adjacent pairs: (pair_sum, serial, left_node, right_node)
    heap = []
    serial = 0  # Use serial to break ties and maintain uniqueness

    # Helper to push a valid pair into the heap
    def push_pair(left_node, right_node):
        nonlocal serial
        if left_node and right_node:
            pair_sum = left_node.value + right_node.value
            heapq.heappush(heap, (pair_sum, serial, left_node, right_node))
            serial += 1

    # Initialize the heap with all adjacent pairs.
    cur = nodes[0]
    while cur and cur.next:
        push_pair(cur, cur.next)
        cur = cur.next

    # Function to check if the current list is non-decreasing.
    def is_sorted(head):
        cur = head
        while cur and cur.next:
            if cur.value > cur.next.value:
                return False
            cur = cur.next
        return True

    # Determine the head of the list.
    head = nodes[0]

    operations = 0
    # Continue while the list is not non-decreasing.
    while not is_sorted(head):
        # Get the minimum-sum adjacent pair.
        pair_sum, _, left_node, right_node = heapq.heappop(heap)
        # If either node has been merged, skip this pair.
        if not left_node.valid or not right_node.valid:
            continue

        # Merge left_node and right_node into a new node.
        new_val = left_node.value + right_node.value
        new_node = Node(new_val)

        # Merge the neighbors by linking new_node to left_node.prev and right_node.next.
        new_node.prev = left_node.prev
        new_node.next = right_node.next

        if new_node.prev:
            new_node.prev.next = new_node
        else:
            head = new_node  # new_node becomes the head if no previous exists
        if new_node.next:
            new_node.next.prev = new_node

        # Mark the merged nodes as invalid.
        left_node.valid = False
        right_node.valid = False

        # Increment count of operations.
        operations += 1

        # Push new adjacent pairs for new_node.
        if new_node.prev:
            push_pair(new_node.prev, new_node)
        if new_node.next:
            push_pair(new_node, new_node.next)

    return operations

# Example usage:
example_nums = [5, 2, 3, 1]
print(minimumPairRemovalToSort(example_nums))  # Expected output: 2
← Back to All Questions