Problem Description

You are given an array nums consisting of integers between 1 and 3, and a binary array locked of the same size.

We consider nums sortable if it can be sorted using adjacent swaps, where a swap between two indices i and i + 1 is allowed if nums[i] - nums[i + 1] == 1 and locked[i] == 0.

In one operation, you can unlock any index i by setting locked[i] to 0.

Return the minimum number of operations needed to make nums sortable. If it is not possible to make nums sortable, return -1.

Intuition

To solve this problem, we need to determine how the array nums can be sorted given the constraints on swaps dictated by the locked array. The core idea is that nums is sortable if we can rearrange it such that every occurrence of the number 3 comes after every occurrence of the number 1.

We identify the first occurrence of the number 2 (first2) and 3 (first3), and the last occurrence of the number 1 (last1) and 2 (last2). The key observation is that if first3 is less than last1, then the numbers are not in the correct order to be sorted—3s are incorrectly placed before 1s—and hence sorting is impossible without swaps.

The main technique used to arrive at a solution involves counting operations. Specifically, we require every index in the range [first2, last1) or [first3, last2) in the locked array to be unlocked (locked[i] == 0) to allow sorting swaps. Thus, we count all positions in these ranges that are locked, indicating the minimum number of operations needed to unlock these positions.

Solution Approach

To implement the solution, follow these steps:

1. Initialization:

   • Start by determining the length of the nums array, denoted as n.
   • Initialize first2 and first3 to n (signifying unrealistic high index positions) and last1 and last2 to -1 (indicating nonexistent low index positions).

2. Identify Critical Indices:

   • Traverse through the nums array and for each index i with value x:
     • If x == 1, update last1 to i (mark the last occurrence of 1).
     • If x == 2, update both first2 to the minimum of current first2 and i, and last2 to i (track boundaries for 2).
     • If x == 3, update first3 to the minimum of current first3 and i (mark the initial occurrence of 3).

3. Check Sortability Condition:

   • If first3 < last1, it indicates that at least one 3 is incorrectly before a 1, making sorting impossible under given constraints. Thus, return -1.

4. Count Required Unlocks:

   • Traverse the locked array and calculate how many indices fall within the ranges [first2, last1) or [first3, last2) that are locked. This determines the number of unlock operations needed.
   • For each index i in locked, if it is locked and falls within either of these critical ranges, increment a counter.

5. Return the Count:

   • The counter gives the minimum number of unlock operations needed to allow nums to become sortable under the specified conditions.

The solution uses a simple traversal of arrays and manipulation of indices, resulting in a time complexity of O(n), where n is the length of the input arrays.

Example Walkthrough

Consider the following example to understand the solution approach:

Inputs:

• nums = [2, 3, 1, 2, 3]
• locked = [0, 1, 1, 0, 1]

Step-by-Step Solution:

1. Initialization:

   • n = 5 (length of the array).
   • Initialize first2 and first3 to 5 (an index beyond the array length).
   • Initialize last1 and last2 to -1 (nonexistent index).

2. Identify Critical Indices:

   • Traverse nums:
     • For i = 0, nums[0] = 2:
       • first2 = min(5, 0) = 0
       • last2 = 0
     • For i = 1, nums[1] = 3:
       • first3 = min(5, 1) = 1
     • For i = 2, nums[2] = 1:
       • last1 = 2
     • For i = 3, nums[3] = 2:
       • last2 = 3
     • For i = 4, nums[4] = 3:
       • first3 remains 1

3. Check Sortability Condition:

   • Since first3 (1) < last1 (2), the 3 at index 1 comes before the 1 at index 2, indicating sorting is currently impossible without unlocking.

4. Count Required Unlocks:

   • Traverse the locked array and check indices in the critical ranges:
     • Range [first2, last1) is [0, 2) → indices 0 and 1.
     • Range [first3, last2) is [1, 3) → indices 1 and 2.
   • Check locked statuses:
     • i = 0: locked[0] = 0 (already unlocked).
     • i = 1: locked[1] = 1 (locked in the range), increment counter to 1.
     • i = 2: locked[2] = 1 (locked in the range), increment counter to 2.

5. Return the Count:

   • A minimum of 2 unlocking operations is necessary to make nums sortable.

In this walk-through, unlocking indices 1 and 2 allows adjacent swaps to eventually position all 3s after all 1s, fulfilling the sorting condition.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the algorithm iterates through the nums array and the locked array each once. Specifically, the first loop traverses the nums array to determine positions related to elements 1, 2, and 3, while the second loop calculates the sum based on the locked array. Each of these operations takes linear time proportional to the size of the arrays.

The space complexity is O(1), as the algorithm uses a constant amount of extra space regardless of the size of the input arrays. The variables first2, first3, last1, and last2 are used to store index positions and do not scale with the input size.

Learn more about how to find time and space complexity quickly.