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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort Array by Moving Items to Empty Space

Number: 2489

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

You are given an integer array nums of size n that contains every integer from 0 to n-1 (inclusive). In this array the number 0 represents an empty space and every other number (from 1 to n-1) represents an item. In one operation you may move any item to the empty space. The array is considered sorted if the items (numbers 1 through n-1) are in ascending order and the empty space (0) is either at the beginning or at the end of the array. Return the minimum number of operations required to sort the array.

Key Insights

  • The only allowed operation is to move an item directly into the empty space, which “shifts” the empty space to the moved item’s location.
  • There are two possible target configurations: one with 0 at the beginning (target1: [0,1,2,…,n–1]) and one with 0 at the end (target2: [1,2,…,n–1,0]). We can compute the minimum moves required for both and take the minimum.
  • The transformation can be modeled as a permutation of indices. For each target configuration, define a mapping f on indices where for index i (with value v = nums[i]) the desired index is:
    • For target1 (empty at beginning): if v == 0 then expected index is 0, otherwise expected index is v.
    • For target2 (empty at end): if v == 0 then expected index is n–1, otherwise expected index is v–1.
  • The permutation can be decomposed into disjoint cycles. For each cycle:
    • If the cycle length is 1 (already in place), no move is needed.
    • If the cycle contains the position that must hold the empty space in the target configuration then the cost is (cycle length – 1).
    • Otherwise the cost is (cycle length + 1) because moving items into a cycle that does not contain the empty requires an extra move.
  • The final answer is the minimum total cost among the two target configurations.

Space and Time Complexity

Time Complexity: O(n) — we iterate through the array and each index is visited exactly once during cycle decomposition. Space Complexity: O(n) — additional arrays (e.g. visited marker and mapping) use linear extra space.

Solution

We solve the problem by “simulating” the sorting process indirectly via cycle decomposition of a permutation. For any chosen target configuration (empty at beginning or at end), we first build a mapping from each index i (the current position) to its expected position based on the target order. Then, we perform a cycle decomposition on this permutation. For each cycle: • If it is of length 1 (already correct) we do nothing. • If the cycle includes the target index for the empty space then we can fix it in (length – 1) moves. • Otherwise, fixing the cycle requires an extra move (i.e. cost = cycle length + 1). The answer is the minimum total moves computed between the two possible target “sorted” orders.

Code Solutions

# Python solution for "Sort Array by Moving Items to Empty Space"
def minMoves(nums):
    n = len(nums)
    
    # Helper function to compute cost given a target position for 0 (empty space)
    def compute_cost(blank_target):
        # Build the mapping f for each index i.
        # For target configuration:
        # If blank_target == 0, then for any item the expected index is its own value (0 is expected at index 0).
        # If blank_target == n-1, then for an item v (v != 0) expected index is v-1; for 0, expected index is n-1.
        mapping = [0] * n
        for i in range(n):
            if nums[i] == 0:
                mapping[i] = blank_target
            else:
                mapping[i] = nums[i] if blank_target == 0 else nums[i] - 1
        
        visited = [False] * n
        total_moves = 0
        
        # Process each index to decompose into cycles.
        for i in range(n):
            if visited[i]:
                continue
            cycle_length = 0
            cur = i
            contains_blank_target = False
            # Traverse the cycle
            while not visited[cur]:
                visited[cur] = True
                cycle_length += 1
                # Check if this index is the desired blank position
                if cur == blank_target:
                    contains_blank_target = True
                cur = mapping[cur]
            # For fixed point, no moves are needed.
            if cycle_length == 1:
                continue
            # If cycle already includes the blank target, cost is cycle_length - 1,
            # otherwise an extra move is needed to bring the empty space into the cycle.
            if contains_blank_target:
                total_moves += cycle_length - 1
            else:
                total_moves += cycle_length + 1
        return total_moves

    # Compute moves for both target configurations:
    cost1 = compute_cost(0)       # Target: [0,1,2,.., n-1]
    cost2 = compute_cost(n - 1)   # Target: [1,2,3,.., n-1,0]
    return min(cost1, cost2)


# Example usage:
#print(minMoves([4,2,0,3,1]))  # Expected output: 3
← Back to All Questions