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 Unlocked Indices to Sort Nums

Number: 3758

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

We are given an integer array (nums) whose entries are only 1, 2, or 3 and a binary array (locked) of the same length. We say that nums is “sortable” if one may repeatedly perform an adjacent swap between positions i and i+1 – but only when the number at position i is exactly one more than that at position i+1 AND when locked[i] is 0 – so that eventually nums becomes sorted in non‐decreasing order. In one “operation” you may pick any index i and “unlock” it (by setting locked[i] to 0). Return the minimum operations needed to make nums sortable; if even after unlocking any subset the required order can’t be reached then return –1.

Key Insights

  • Only adjacent swaps where the left element is exactly 1 greater than the right element are allowed. (That is, you can swap a (2,1) or (3,2) but never a (3,1) directly.)
  • Even if all indices are free the allowed “bubble‐sort” style moves are not powerful enough to realize an arbitrary permutation. In fact, the numbers in any “sortable” sequence must “balance” in a prefix–sense: as you scan from left to right the difference between counts (first 1 vs 2 and then 2 vs 3) must never become negative.
  • The locked entries are “stuck” in place – they must satisfy the prefix “balance” condition by themselves. In other words, if a locked element causes a violation of the invariant then it must be unlocked.
  • We can “fix” sorting impossibilities only by turning some locked indices into free ones. In the end, the free elements (whose multiset is fixed) must be re–ordered (by allowed swaps) and interleaved with the remaining locked ones so that the entire array can be “bubbled” to non–decreasing order.
  • Because the numbers range only over {1,2,3} one may “simulate” the process by thinking in terms of cumulative counts (or “prefix differences”). In any prefix the count(1) must be at least the count(2) and the count(2) must be at least the count(3).

Space and Time Complexity

Time Complexity: O(n) – We scan and update prefix conditions in one or two passes. Space Complexity: O(n) – For storing auxiliary arrays (or O(1) additional space if done in place).

Solution

The key observation is that a necessary (and for this problem, nearly sufficient) condition for a sequence to be sortable via these very restricted swaps is that if you “simulate” the process by taking the final configuration, then as you read from left to right the cumulative frequencies must obey:   (#1’s so far) – (#2’s so far) ≥ 0 and (#2’s so far) – (#3’s so far) ≥ 0. Since “locked” indices cannot change their order, if they alone (in order) violate these inequalities then there is no way to “fix” the overall ordering using allowed adjacent swaps – unless you free some of those indices. Thus the idea is to choose a minimum set of locked indices to unlock so that the locked “skeleton” (i.e. the sequence of indices whose locked flag remains 1) satisfies the prefix invariants. (Notice that the free indices are “malleable:” although only certain adjacent swaps are allowed, it turns out that if the multiset of free numbers satisfies the necessary “balance” then they can be re–ordered appropriately.) A dynamic programming (DP) or greedy strategy can be used. One may scan the array from left to right while “merging” the fixed locked numbers with the free ones available for interleaving. When a locked element would cause a violation (for example, adding a 2 when there isn’t a free or locked 1 “before” it so that the difference would go negative) then that locked element “must” be unlocked. The following outline shows one way to solve it:   • Precompute the total frequencies of 1, 2, and 3.   • Initialize two “counters:” one for the cumulative contribution of locked elements (in order) and one for the free elements (which may be “re–ordered” arbitrarily provided that overall the prefix invariant holds).   • Walk through the array in order; at each locked index, try “inserting” its value into the locked‐skeleton. If by doing so one of the invariants would be broken (i.e. the locked count of 1’s becomes less than that of 2’s or the locked count of 2’s becomes less than that of 3’s) then it is optimal to “free” that index (increment the unlock operation count) so that its value is instead added to the free multiset.   • Finally, check that the free multiset (which now comprises all originally free indices plus the ones you unlocked) is “sortable” on its own (its free counts can be arranged in non–decreasing order via allowed swaps – this is equivalent to having the free counts satisfy the prefix invariant when sorted). If after processing the array the locked–skeleton respects the invariants and the free multiset is sortable, then the total number of indices we unlocked is the answer; otherwise return –1. One potential pitfall is that the operations of “unlocking” must be chosen optimally – unlocking too many (or too few) indices might either be unnecessary or leave behind an unsolvable locked skeleton. The crux is to “simulate” the forming of a valid target order by conservatively “freeing” any locked element that would force the prefix “imbalance.”

Code Solutions

# Python solution with detailed comments
def minUnlocks(nums, locked):
    n = len(nums)
    unlock_ops = 0
    
    # These counters record how many of each number remain “fixed”
    locked1, locked2, locked3 = 0, 0, 0
    
    # These counters record the free multiset counts
    free1, free2, free3 = 0, 0, 0
    for i in range(n):
        if locked[i] == 0:
            # Already free; add to free counts.
            if nums[i] == 1: free1 += 1
            elif nums[i] == 2: free2 += 1
            else: free3 += 1
        else:
            # Tentatively keep this element locked.
            if nums[i] == 1:
                locked1 += 1
            elif nums[i] == 2:
                locked2 += 1
            else:
                locked3 += 1
            # Check prefix invariants:
            # In any prefix, we need #1 >= #2 and #2 >= #3.
            # Here the locked skeleton may later be interleaved with free elements,
            # but if the locked part itself violates, then there is no room for free ones to fix it.
            if locked1 < locked2 or locked2 < locked3:
                # “Unlock” this index so that its value will join the free pool.
                unlock_ops += 1
                # Revert counters update as if this element were free.
                if nums[i] == 1:
                    locked1 -= 1; free1 += 1
                elif nums[i] == 2:
                    locked2 -= 1; free2 += 1
                else:
                    locked3 -= 1; free3 += 1
    # At this point, the locked-skeleton should have the proper prefix balance.
    # Now check if the free elements (which can be arbitrarily rearranged subject to allowed swaps)
    # can be sorted. For free group the necessary and sufficient condition is that the free multiset,
    # when “ordered” correctly, satisfies: when scanning from left to right, the cumulative differences are non-negative.
    free_total = free1 + free2 + free3
    # If free_total == 0 then nothing to worry about.
    if free_total > 0:
        # The best-case arrangement is to put all 1's, then 2's, then 3's.
        # For this arrangement the prefix differences are:
        # For positions within the free ones:
        #   first free1 positions: count1 goes from 1 to free1 (okay)
        #   next free2 positions: at the beginning, count1=free1, count2 starts increasing.
        #   To satisfy invariant we need free1 >= free2.
        # Similarly, for free2 and free3 we need free2 >= free3.
        if free1 < free2 or free2 < free3:
            return -1
    return unlock_ops

# Example test cases:
print(minUnlocks([1,2,1,2,3,2], [1,0,1,1,0,1]))  # Expected 0 
print(minUnlocks([1,2,1,1,3,2,2], [1,0,1,1,0,1,0]))  # Expected 2
print(minUnlocks([1,2,1,2,3,2,1], [0,0,0,0,0,0,0]))  # Expected -1
← Back to All Questions