Minimum unlocked indices to sort nums

impl Solution {
  pub fn min_unlocked_indices(nums: Vec<i32>, locked: Vec<i32>) -> i32 {
    let n = nums.len();
    // Only values 1,2,3. Sorted = all 1s, then all 2s, then all 3s.
    // Count occurrences
    let mut c1 = 0usize;
    let mut c2 = 0usize;
    let mut c3 = 0usize;
    for &x in &nums {
      match x {
        1 => c1 += 1,
        2 => c2 += 1,
        3 => c3 += 1,
        _ => {}
      }
    }
    // The sorted array: [1..c1, 2..c1+c2, 3..c1+c2+c3]
    // Adjacent swap only allowed if nums[i] - nums[i+1] == 1 and locked[i] == 0
    // This means we can only swap (2,1) or (3,2) pairs at unlocked positions.
    // This is like bubble sort but restricted: 
    //   - A 2 can pass left through 1s (by swapping 2,1 -> 1,2 when unlocked)
    //   - A 3 can pass left through 2s (by swapping 3,2 -> 2,3 when unlocked)
    //   - But a 3 cannot directly pass through a 1 (3-1=2≠1)
    //
    // For the array to be sortable:
    // 1) All 1s must end up in positions [0..c1), all 2s in [c1..c1+c2), all 3s in [c1+c2..n).
    // 2) A 3 cannot pass through a 1 at all (even with unlocking). So the relative order of 1s and 3s is fixed.
    //    If any 3 appears before a 1 in the original array and there's no way to move it, 
    //    actually a 3 can never swap with a 1 since 3-1=2≠1. So a 3 can never pass a 1.
    //    This means: for every 1, all 3s must come after it in the original array.
    //    Equivalently, the last 3 that appears before any 1 makes it impossible.
    //    More precisely: if there's a 3 at position i and a 1 at position j > i, we need the 3 to move past the 1.
    //    But 3 can only swap with 2. So 3 can move right through 2s, and 1 can move... wait.
    //    Actually swaps are: if nums[i]-nums[i+1]==1, swap them. So (2,1)->(1,2) and (3,2)->(2,3).
    //    A 3 can move RIGHT by swapping with a 2 to its right? No: nums[i]-nums[i+1]=3-2=1, so (3,2) can swap to (2,3). 
    //    That moves 3 right and 2 left. Similarly (2,1) swaps to (1,2), moving 2 right and 1 left.
    //    
    //    So 1s can only move LEFT (or stay), 3s can only move RIGHT (or stay), 2s can move both ways.
    //    Wait no: (2,1) at positions (i,i+1) means nums[i]=2, nums[i+1]=1. After swap: nums[i]=1, nums[i+1]=2.
    //    So 2 moves right, 1 moves left.
    //    (3,2): 3 moves right, 2 moves left.
    //    
    //    Actually 1 can only move left, 3 can only move right, 2 moves based on neighbors.
    //    But we need 1s to be at the front (move left is fine) and 3s at the end (move right is fine).
    //    The problem is 1s moving left past other 1s (no swap), or 3 trying to pass 1 (impossible).
    //    
    //    Key constraint: if a 3 is to the left of a 1 in the original array, it's impossible 
    //    because 3 can only move right (further away from 1's destination) and 1 can only move left.
    //    They'd need to swap, but 3-1=2≠1.
    //    
    //    So first check: no 3 should appear before any 1 in positions that would make it impossible.
    //    Actually: once a 3 is to the left of a 1, they can never swap order. So in the sorted array,
    //    all 1s come before all 3s. This means in the original array, every 1 must come before every 3.
    //    If any 3 appears before any 1, return -1.
    
    // Check feasibility: every 3 must come after every 1
    if c1 > 0 && c3 > 0 {
      let last_pos_of_1 = nums.iter().rposition(|&x| x == 1).unwrap();
      let first_pos_of_3 = nums.iter().position(|&x| x == 3).unwrap();
      if first_pos_of_3 < last_pos_of_1 {
        // There's a 3 before a 1, but we need to check more carefully.
        // Actually any 3 before any 1 is problematic.
        // If there exists i < j with nums[i]=3 and nums[j]=1, impossible.
        // first_pos_of_3 < last_pos_of_1 means exactly this.
        return -1;
      }
    }

    // Now we know all 1s come before all 3s. 
    // The positions 0..c1 should have 1s, c1..c1+c2 should have 2s, c1+c2..n should have 3s.
    // 
    // Elements out of place:
    // - 2s in the first c1 positions need to move right (swap with 1s on their right using (2,1) swap)
    // - 1s in positions c1..c1+c2 need to move left (swap with 2s on their left)
    // Both achieve the same: each misplaced 2 in [0,c1) swaps right with 1s.
    // 
    // Similarly, 3s in [c1,c1+c2) need to move right (swap with 2s), and 2s in [c1+c2,n) need to move left.
    //
    // For a swap at position i to happen, locked[i] must be 0 (or we unlock it).
    // We need to count the minimum unlocks needed.
    //
    // The swaps needed form a bubble-sort-like sequence:
    // Region [0, c1): should be all 1s. Currently has some 1s and 2s.
    // A 2 at position p needs to bubble right past all 1s to its right until it exits region [0,c1).
    // Each swap of (2,1) at position i requires locked[i]=0.
    // 
    // Similarly in region [c1, c1+c2): should be all 2s. Has some 2s and 3s.
    // A 3 needs to bubble right past 2s.
    //
    // Let me think about which positions need to be unlocked.
    // For the boundary at c1: all 2s in [0,c1) need to pass position c1-1 going right.
    // Actually each 2 in [0,c1) needs to swap with each 1 to its right, at each intermediate position.
    // 
    // Hmm, this is getting complex. Let me think differently.
    //
    // Consider the problem in two parts:
    // Part A: Sort 1s and 2s (ignore 3s for now, they're already after all 1s).
    //   In the region [0, c1+c2), we have 1s and 2s (and no 3s since all 3s are after all 1s,
    //   and since c1+c2 covers the first c1+c2 positions... wait, 3s could be mixed with 2s).
    //   Actually no, 3s in [c1, c1+c2) are out of place and need to move to [c1+c2, n).
    
    // Let me take a simpler approach. The answer is the number of locked positions that
    // need swaps. A position i needs a swap if it's on the "boundary" between misplaced elements.
    // 
    // For each position i where nums[i] > sorted[i], we need to perform swaps.
    // Let me think about what positions are "critical".
    //
    // Actually, the minimum unlocks = number of locked positions in the "swap zone".
    // A position i needs to be unlockable (locked[i]=0) if a swap (nums[i],nums[i+1]) is needed.
    //
    // Let me just simulate: identify which positions need a swap to occur at them.
    // Position i needs a swap if and only if some element needs to pass through it.
    //
    // For 2s moving past 1s:
    // In the first c1+c2 positions, 2s that are to the left of 1s need to bubble past them.
    // The swap at position i happens when a 2 is at position i and a 1 is at position i+1.
    //
    // For 3s moving past 2s:
    // In positions c1..n, 3s that are to the left of 2s need to bubble past them.
    //
    // The positions that need to be unlocked are those where a swap must occur and they're currently locked.
    //
    // A key insight: a position i must allow a swap if there are elements that need to cross it.
    // For the 1-2 boundary: position i (0 <= i < c1+c2-1) needs a swap if there's a 2 at or before i
    // that needs to go past i, and a 1 at or after i+1 that needs to go before i+1.
    // This is equivalent to: among positions 0..=i in the 1-2 region, the number of 2s exceeds
    // what should be there (0 for i < c1, i-c1+1 for i >= c1).
    //
    // Hmm, let me think about it more carefully with a different approach.
    //
    // Actually for bubble sort with adjacent swaps, each inversion must be fixed by a swap at the
    // position of the inversion. The minimum number of unlocks is the number of positions where
    // a swap is needed but the position is locked.
    //
    // For the 1-2 sort: Consider positions 0..c1+c2 (in the original array, ignoring 3s).
    // Element needs to be 1 in positions 0..c1 and 2 in positions c1..c1+c2.
    // A position i where nums[i]=2 and there exists j > i with nums[j]=1 (both in 1-2 region)
    // means we need swaps at all positions between them.
    //
    // Actually, let me simplify. For each pair of adjacent positions (i, i+1):
    // - If in the end, after sorting, position i should have value a and position i+1 should have value b
    //   where a > b (inversion in target), that can't happen since target is sorted.
    // - We need elements to be able to pass through position i.
    //
    // Let me just count: for each position i, is a swap needed at position i?
    // A swap is needed at position i if the number of "wrong" elements (elements that need to cross
    // position i going right or left) is > 0.
    //
    // prefix_wrong[i] for 1-2: count of 2s in positions 0..=i minus expected count of 2s in 0..=i.
    // If prefix_wrong[i] > 0, position i needs a swap (for bubble sort of 1s and 2s).
    //
    // Similarly for 2-3 sort.
    //
    // Let me implement this approach.
    
    let sorted: Vec<i32> = {
      let mut s = vec![0i32; n];
      for i in 0..c1 { s[i] = 1; }
      for i in c1..c1+c2 { s[i] = 2; }
      for i in c1+c2..n { s[i] = 3; }
      s
    };
    
    // For each position i (0..n-1), check if a swap needs to cross this boundary.
    // A boundary is crossed if a "misplaced" element needs to go past it.
    // 
    // Count of element x in positions 0..=i in nums vs sorted.
    // If more 2s than expected in [0..=i] relative to sorted, those 2s need to cross right.
    // The number crossing boundary i is: excess_2_left[i] = count_2_nums[0..=i] - count_2_sorted[0..=i]
    // Similarly for 3s.
    // If excess > 0, a swap is needed at position i (element moving right).
    // 
    // For (2,1) swaps: excess of 2 in [0..=i] means a 2 needs to cross boundary i going right.
    // For (3,2) swaps: excess of 3 in [0..=i] means a 3 needs to cross boundary i going right.
    // 
    // Position i needs to be unlocked if locked[i]==1 and (swap needed).
    // But the swap type matters: (2,1) swap only at boundary where a 2 is crossing a 1.
    // (3,2) swap only where a 3 is crossing a 2.
    
    let mut ans = 0i32;
    let mut excess2 = 0i32; // excess of 2s in nums[0..=i] compared to sorted[0..=i]
    let mut excess3 = 0i32; // excess of 3s
    
    for i in 0..n-1 {
      if nums[i] == 2 { excess2 += 1; }
      if sorted[i] == 2 { excess2 -= 1; }
      if nums[i] == 3 { excess3 += 1; }
      if sorted[i] == 3 { excess3 -= 1; }
      
      // If excess2 > 0: a 2 needs to cross boundary i going right (swap with 1).
      // If excess3 > 0: a 3 needs to cross boundary i going right (swap with 2).
      // Either way, position i needs to allow a swap.
      if (excess2 > 0 || excess3 > 0) && locked[i] == 1 {
        ans += 1;
      }
    }
    
    ans
  }
}