Q1. Minimum Adjacent Swaps to Alternate Parity Attempted Medium 4 pt. You are given an…
- User
Q1. Minimum Adjacent Swaps to Alternate Parity Attempted Medium 4 pt. You are given an array nums of distinct integers.
In one operation, you can swap any two adjacent elements in the array.
An arrangement of the array is considered valid if the parity of adjacent elements alternates, meaning every pair of neighboring elements consists of one even and one odd number.
Return the minimum number of adjacent swaps required to transform nums into any valid arrangement.
If it is impossible to rearrange nums such that no two adjacent elements have the same parity, return -1.
Example 1:
Input: nums = [2,4,6,5,7]
Output: 3
Explanation:
Swapping 5 and 6, the array becomes [2,4,5,6,7]
Swapping 5 and 4, the array becomes [2,5,4,6,7]
Swapping 6 and 7, the array becomes [2,5,4,7,6]. The array is now a valid arrangement. Thus, the answer is 3.
Example 2:
Input: nums = [2,4,5,7]
Output: 1
Explanation:
By swapping 4 and 5, the array becomes [2,5,4,7], which is a valid arrangement. Thus, the answer is 1.
Example 3:
Input: nums = [1,2,3]
Output: 0
Explanation:
The array is already a valid arrangement. Thus, no operations are needed.
Example 4:
Input: nums = [4,5,6,8]
Output: -1
Explanation:
No valid arrangement is possible. Thus, the answer is -1.
Constraints:
1 <= nums.length <= 105 1 <= nums[i] <= 109 All elements in nums are distinct.
Assistant
To solve this problem, we need to find the minimum number of adjacent swaps to arrange the array
numssuch that the parities of adjacent elements alternate (Even-Odd-Even-Odd... or Odd-Even-Odd-Even...).The core idea relies on two key insights:
-
Feasibility Check: For an alternating parity arrangement to be possible, the number of even elements (
E) and odd elements (O) in the array must be very close.- If the total length
Nis even, thenEmust equalO. - If the total length
Nis odd, then|E - O|must be exactly 1. - If
|E - O| > 1, it's impossible to form a valid arrangement, so we return -1.
- If the total length
-
Minimum Adjacent Swaps as Inversions: The minimum number of adjacent swaps required to transform one permutation into another is equal to the number of inversions between the two permutations. In our case, we don't permute arbitrary elements to arbitrary positions. Instead, we want to move all even numbers to specific "even-parity" slots and all odd numbers to specific "odd-parity" slots, while maintaining the relative order of even numbers among themselves and odd numbers among themselves.
For example, if
nums = [2,4,6,5,7]:- Even numbers are 2, 4, 6, originally at indices 0, 1, 2.
- Odd numbers are 5, 7, originally at indices 3, 4.
If we want a final arrangement like
E O E O E(e.g.,[2,5,4,7,6]):- The 1st even number (2) goes to target index 0.
- The 1st odd number (5) goes to target index 1.
- The 2nd even number (4) goes to target index 2.
- The 2nd odd number (7) goes to target index 3.
- The 3rd even number (6) goes to target index 4.
This means:
- Element at original index 0 (value 2) wants to go to target index 0.
- Element at original index 1 (value 4) wants to go to target index 2.
- Element at original index 2 (value 6) wants to go to target index 4.
- Element at original index 3 (value 5) wants to go to target index 1.
- Element at original index 4 (value 7) wants to go to target index 3.
Let's create an array
PwhereP[original_index] = target_index. For our example,P = [0, 2, 4, 1, 3]. The problem then becomes finding the minimum adjacent swaps to sort the arrayPinto[0, 1, 2, 3, 4]. This is precisely the number of inversions inP.An inversion in
Pis a pair(P[i], P[j])such thati < jbutP[i] > P[j]. ForP = [0, 2, 4, 1, 3]:- (2, 1):
P[1]=2,P[3]=1.1 < 3but2 > 1. - (4, 1):
P[2]=4,P[3]=1.2 < 3but4 > 1. - (4, 3):
P[2]=4,P[4]=3.2 < 4but4 > 3. Total inversions = 3, which matches the example output.
Algorithm Steps:
-
Separate Indices by Parity:
- Iterate through
numsand store the original indices of even numbers ineven_original_indicesand odd numbers inodd_original_indices. These lists will naturally be sorted.
- Iterate through
-
Count Parities and Check Feasibility:
- Get
even_count = len(even_original_indices)andodd_count = len(odd_original_indices). - If
abs(even_count - odd_count) > 1, return -1.
- Get
-
Define a Helper Function
calculate_swaps_for_target(start_with_even): This function will calculate the inversions for a specific target arrangement.- Initialize
target_positions = [0] * n, wherenis the length ofnums. This array will storetarget_positions[original_index] = final_index. - Use two pointers,
e_ptrforeven_original_indicesando_ptrforodd_original_indices. - Iterate
ifrom0ton-1(representing the desired final index in the alternating array):- If
start_with_evenis true:- If
iis even, this slot should contain an even number. So,target_positions[even_original_indices[e_ptr]] = i, ande_ptrincrements. - If
iis odd, this slot should contain an odd number. So,target_positions[odd_original_indices[o_ptr]] = i, ando_ptrincrements.
- If
- If
start_with_evenis false (meaning start with odd):- If
iis even, this slot should contain an odd number. So,target_positions[odd_original_indices[o_ptr]] = i, ando_ptrincrements. - If
iis odd, this slot should contain an even number. So,target_positions[even_original_indices[e_ptr]] = i, ande_ptrincrements.
- If
- If
- After populating
target_positions, calculate the number of inversions in it. This can be done efficiently using a Fenwick Tree (BIT).
- Initialize
-
Fenwick Tree (BIT) for Inversion Counting:
- Initialize a Fenwick Tree of size
n(maximum possible target index). - Initialize
inversions = 0. - For
jfrom0ton-1:- Get
current_target_idx = target_positions[j]. - The number of elements already processed (original indices
0toj-1) whose target position is greater thancurrent_target_idxcontributes to inversions. This isft.query(n-1) - ft.query(current_target_idx). Add this toinversions. - Update the BIT at
current_target_idxby 1 to mark it as processed:ft.update(current_target_idx, 1).
- Get
- Return
inversions.
- Initialize a Fenwick Tree of size
-
Main Logic for Determining Minimum Swaps:
- Initialize
min_swaps = infinity. - If
even_count == odd_count:- Both
start_with_evenandstart_with_oddarrangements are possible. Calculate swaps for both and take the minimum:min_swaps = min(calculate_swaps_for_target(True), calculate_swaps_for_target(False)).
- Both
- If
even_count == odd_count + 1:- Only
start_with_evenarrangement is possible:min_swaps = calculate_swaps_for_target(True).
- Only
- If
odd_count == even_count + 1:- Only
start_with_oddarrangement is possible:min_swaps = calculate_swaps_for_target(False).
- Only
- Return
min_swaps.
- Initialize
Complexity:
- Time Complexity:
O(N log N)because separating indices isO(N), and calculating inversions using a Fenwick Tree takesO(N log N). In the worst case, we run the inversion calculation twice. - Space Complexity:
O(N)for storing original indices,target_positions, and the Fenwick Tree.
Fenwick Tree (BIT) Class: A Fenwick tree allows for efficient prefix sum queries and point updates.
update(index, val): Addsvalto the element atindex.O(log N).query(index): Returns the sum of elements from0toindex.O(log N). (Note: Fenwick trees are typically 1-indexed, so we convert 0-based input indices.)
import math class FenwickTree: def __init__(self, size): # The tree size needs to be 1 more than the maximum index # since Fenwick tree uses 1-based indexing internally. # Max index for values (0 to n-1) is n-1, so tree size should be n. self.tree = [0] * (size + 1) self.size = size def update(self, index, val): # Convert 0-based index to 1-based for BIT operations index += 1 while index <= self.size: self.tree[index] += val index += index & (-index) def query(self, index): # Convert 0-based index to 1-based for BIT operations index += 1 s = 0 while index > 0: s += self.tree[index] index -= index & (-index) return s class Solution: def minSwaps(self, nums: list[int]) -> int: n = len(nums) even_original_indices = [] odd_original_indices = [] # Step 1: Separate original indices based on parity for i in range(n): if nums[i] % 2 == 0: even_original_indices.append(i) else: odd_original_indices.append(i) even_count = len(even_original_indices) odd_count = len(odd_original_indices) # Step 2: Check feasibility if abs(even_count - odd_count) > 1: return -1 def calculate_swaps_for_target(start_with_even: bool) -> int: # target_positions[original_index] = final_index target_positions = [0] * n e_ptr = 0 # Pointer for even_original_indices o_ptr = 0 # Pointer for odd_original_indices # Determine the desired final position for each element based on its original index for i in range(n): # i represents the current final desired index (0 to n-1) if start_with_even: if i % 2 == 0: # This target position (i) should hold an even number target_positions[even_original_indices[e_ptr]] = i e_ptr += 1 else: # This target position (i) should hold an odd number target_positions[odd_original_indices[o_ptr]] = i o_ptr += 1 else: # The arrangement must start with an odd number if i % 2 == 0: # This target position (i) should hold an odd number target_positions[odd_original_indices[o_ptr]] = i o_ptr += 1 else: # This target position (i) should hold an even number target_positions[even_original_indices[e_ptr]] = i e_ptr += 1 # Step 3: Calculate inversions in `target_positions` using a Fenwick Tree # The number of adjacent swaps to sort a permutation is its number of inversions. # target_positions[k] means the element originally at index k wants to move to target_positions[k]. # We are calculating inversions on this array. ft = FenwickTree(n) # BIT for indices 0 to n-1 inversions = 0 for j in range(n): # Iterate through original indices (j) current_target_idx = target_positions[j] # Count elements that have already been processed (original index < j) # and have a target position greater than current_target_idx. # These are inversions. # ft.query(n-1) gives total count of elements processed so far. # ft.query(current_target_idx) gives count of elements processed so far # whose target position is <= current_target_idx. # Their difference is the count of elements processed so far # whose target position is > current_target_idx. inversions += ft.query(n - 1) - ft.query(current_target_idx) # Mark current_target_idx as seen/processed in the BIT ft.update(current_target_idx, 1) return inversions min_swaps = math.inf # Step 4: Determine which target arrangement(s) to calculate swaps for if even_count == odd_count: # N is even, both E O E O... and O E O E... are possible min_swaps = min(calculate_swaps_for_target(True), calculate_swaps_for_target(False)) elif even_count == odd_count + 1: # N is odd, and there's one more even number. Must start with Even (E O E O E...). min_swaps = calculate_swaps_for_target(True) else: # odd_count == even_count + 1 # N is odd, and there's one more odd number. Must start with Odd (O E O E O...). min_swaps = calculate_swaps_for_target(False) return min_swaps-
- User
in java
Assistant
Okay, here's the Java equivalent of the Python solution, implementing the Fenwick Tree (BIT) for efficient inversion counting.
import java.util.ArrayList; import java.util.List; import java.lang.Math; // For Math.abs and Math.min // Fenwick Tree (Binary Indexed Tree) implementation class FenwickTree { private int[] tree; private int size; public FenwickTree(int size) { // The tree size needs to be 1 more than the maximum index // since Fenwick tree uses 1-based indexing internally. // Max index for values (0 to n-1) is n-1, so tree array size should be n + 1. this.size = size; this.tree = new int[size + 1]; } // Adds 'val' to the element at 'index' (0-based) public void update(int index, int val) { // Convert 0-based index to 1-based for BIT operations index += 1; while (index <= size) { tree[index] += val; index += index & (-index); // Move to the next relevant node } } // Returns the prefix sum up to 'index' (0-based), inclusive public int query(int index) { // Convert 0-based index to 1-based for BIT operations index += 1; int sum = 0; while (index > 0) { sum += tree[index]; index -= index & (-index); // Move to the parent node } return sum; } } class Solution { public long minSwaps(int[] nums) { int n = nums.length; List<Integer> evenOriginalIndices = new ArrayList<>(); List<Integer> oddOriginalIndices = new ArrayList<>(); // Step 1: Separate original indices based on parity for (int i = 0; i < n; i++) { if (nums[i] % 2 == 0) { evenOriginalIndices.add(i); } else { oddOriginalIndices.add(i); } } int evenCount = evenOriginalIndices.size(); int oddCount = oddOriginalIndices.size(); // Step 2: Check feasibility if (Math.abs(evenCount - oddCount) > 1) { return -1; } // Helper function to calculate swaps for a specific target arrangement // (starting with even or starting with odd) long resultSwaps = Long.MAX_VALUE; if (evenCount == oddCount) { // N is even, both E O E O... and O E O E... are possible resultSwaps = Math.min(calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, true), calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, false)); } else if (evenCount == oddCount + 1) { // N is odd, and there's one more even number. Must start with Even (E O E O E...). resultSwaps = calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, true); } else { // oddCount == evenCount + 1 // N is odd, and there's one more odd number. Must start with Odd (O E O E O...). resultSwaps = calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, false); } return resultSwaps; } private long calculateSwapsForTarget(int n, List<Integer> evenOriginalIndices, List<Integer> oddOriginalIndices, boolean startWithEven) { // targetPositions[original_index] = final_index_in_alternating_array int[] targetPositions = new int[n]; int ePtr = 0; // Pointer for even_original_indices int oPtr = 0; // Pointer for odd_original_indices // Determine the desired final position for each element based on its original index for (int i = 0; i < n; i++) { // i represents the current final desired index (0 to n-1) if (startWithEven) { if (i % 2 == 0) { // This target position (i) should hold an even number targetPositions[evenOriginalIndices.get(ePtr)] = i; ePtr++; } else { // This target position (i) should hold an odd number targetPositions[oddOriginalIndices.get(oPtr)] = i; oPtr++; } } else { // The arrangement must start with an odd number if (i % 2 == 0) { // This target position (i) should hold an odd number targetPositions[oddOriginalIndices.get(oPtr)] = i; oPtr++; } else { // This target position (i) should hold an even number targetPositions[evenOriginalIndices.get(ePtr)] = i; ePtr++; } } } // Calculate inversions in `targetPositions` using a Fenwick Tree // The minimum number of adjacent swaps to sort a permutation is its number of inversions. // We have `targetPositions[original_index] = final_index`. // We are calculating inversions on this array `targetPositions`. // An inversion (i, j) means original index i < original index j, but // targetPositions[i] > targetPositions[j]. This means element originally at `i` // needs to jump over element originally at `j` (or vice-versa). FenwickTree ft = new FenwickTree(n); // BIT for indices 0 to n-1 long inversions = 0; // Use long for inversions as it can exceed int max (N=10^5 => ~5*10^9) // Iterate through elements by their ORIGINAL indices (0 to n-1) for (int j = 0; j < n; j++) { int currentTargetIdx = targetPositions[j]; // Query for how many elements already processed (original index < j) // have a target position GREATER than currentTargetIdx. // ft.query(n - 1) gives the total count of elements processed so far. // ft.query(currentTargetIdx) gives the count of elements processed so far // whose target position is <= currentTargetIdx. // Their difference is the count of elements processed so far // whose target position is > currentTargetIdx. These are inversions. inversions += ft.query(n - 1) - ft.query(currentTargetIdx); // Mark currentTargetIdx as seen/processed in the BIT ft.update(currentTargetIdx, 1); } return inversions; } }- User
remove all the comments
Assistant
import java.util.ArrayList; import java.util.List; import java.lang.Math; class FenwickTree { private int[] tree; private int size; public FenwickTree(int size) { this.size = size; this.tree = new int[size + 1]; } public void update(int index, int val) { index += 1; while (index <= size) { tree[index] += val; index += index & (-index); } } public int query(int index) { index += 1; int sum = 0; while (index > 0) { sum += tree[index]; index -= index & (-index); } return sum; } } class Solution { public long minSwaps(int[] nums) { int n = nums.length; List<Integer> evenOriginalIndices = new ArrayList<>(); List<Integer> oddOriginalIndices = new ArrayList<>(); for (int i = 0; i < n; i++) { if (nums[i] % 2 == 0) { evenOriginalIndices.add(i); } else { oddOriginalIndices.add(i); } } int evenCount = evenOriginalIndices.size(); int oddCount = oddOriginalIndices.size(); if (Math.abs(evenCount - oddCount) > 1) { return -1; } long resultSwaps = Long.MAX_VALUE; if (evenCount == oddCount) { resultSwaps = Math.min(calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, true), calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, false)); } else if (evenCount == oddCount + 1) { resultSwaps = calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, true); } else { resultSwaps = calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, false); } return resultSwaps; } private long calculateSwapsForTarget(int n, List<Integer> evenOriginalIndices, List<Integer> oddOriginalIndices, boolean startWithEven) { int[] targetPositions = new int[n]; int ePtr = 0; int oPtr = 0; for (int i = 0; i < n; i++) { if (startWithEven) { if (i % 2 == 0) { targetPositions[evenOriginalIndices.get(ePtr)] = i; ePtr++; } else { targetPositions[oddOriginalIndices.get(oPtr)] = i; oPtr++; } } else { if (i % 2 == 0) { targetPositions[oddOriginalIndices.get(oPtr)] = i; oPtr++; } else { targetPositions[evenOriginalIndices.get(ePtr)] = i; ePtr++; } } } FenwickTree ft = new FenwickTree(n); long inversions = 0; for (int j = 0; j < n; j++) { int currentTargetIdx = targetPositions[j]; inversions += ft.query(n - 1) - ft.query(currentTargetIdx); ft.update(currentTargetIdx, 1); } return inversions; } }- User
time limit exceed for 1st one
Assistant
If the Fenwick Tree (BIT) solution is causing a Time Limit Exceeded (TLE), it often points to a slightly higher constant factor in its operations compared to other
O(N log N)algorithms, or it might be interacting unfavorably with the specific test environment's CPU/memory caches.A common alternative for counting inversions with
O(N log N)complexity is using a Merge Sort based approach. This method inherently counts inversions as it merges sorted subarrays.Here's the Java solution utilizing Merge Sort for inversion counting. This should address the TLE if the constant factor was the issue.
import java.util.ArrayList; import java.util.List; import java.lang.Math; class Solution { public long minSwaps(int[] nums) { int n = nums.length; List<Integer> evenOriginalIndices = new ArrayList<>(); List<Integer> oddOriginalIndices = new ArrayList<>(); // Step 1: Separate original indices based on parity for (int i = 0; i < n; i++) { if (nums[i] % 2 == 0) { evenOriginalIndices.add(i); } else { oddOriginalIndices.add(i); } } int evenCount = evenOriginalIndices.size(); int oddCount = oddOriginalIndices.size(); // Step 2: Check feasibility // If the absolute difference between even and odd counts is greater than 1, // it's impossible to form an alternating sequence. if (Math.abs(evenCount - oddCount) > 1) { return -1; } long resultSwaps = Long.MAX_VALUE; // Step 3: Determine which target arrangement(s) to calculate swaps for // If N is even, counts must be equal. Both start with Even or start with Odd are possible. if (evenCount == oddCount) { resultSwaps = Math.min(calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, true), calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, false)); } // If N is odd and there's one more even number, it must start with Even (E O E O E...). else if (evenCount == oddCount + 1) { resultSwaps = calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, true); } // If N is odd and there's one more odd number, it must start with Odd (O E O E O...). else { // oddCount == evenCount + 1 resultSwaps = calculateSwapsForTarget(n, evenOriginalIndices, oddOriginalIndices, false); } return resultSwaps; } // Helper function to calculate swaps for a specific target arrangement // This function constructs the 'targetPositions' array and then counts inversions in it. private long calculateSwapsForTarget(int n, List<Integer> evenOriginalIndices, List<Integer> oddOriginalIndices, boolean startWithEven) { // targetPositions[original_index] = final_index_in_alternating_array // This array defines where each element (identified by its original index) wants to go. int[] targetPositions = new int[n]; int ePtr = 0; // Pointer for even_original_indices int oPtr = 0; // Pointer for odd_original_indices // Populate targetPositions based on the desired alternating pattern for (int i = 0; i < n; i++) { // 'i' represents the current final desired index (0 to n-1) if (startWithEven) { if (i % 2 == 0) { // This target position (i) should hold an even number targetPositions[evenOriginalIndices.get(ePtr)] = i; ePtr++; } else { // This target position (i) should hold an odd number targetPositions[oddOriginalIndices.get(oPtr)] = i; oPtr++; } } else { // The arrangement must start with an odd number if (i % 2 == 0) { // This target position (i) should hold an odd number targetPositions[oddOriginalIndices.get(oPtr)] = i; oPtr++; } else { // This target position (i) should hold an even number targetPositions[evenOriginalIndices.get(ePtr)] = i; ePtr++; } } } // Step 4: Calculate inversions in `targetPositions` using Merge Sort. // The minimum number of adjacent swaps to sort a permutation is its number of inversions. return mergeSortAndCountInversions(targetPositions); } // --- Merge Sort based Inversion Counting --- // Public wrapper to start the merge sort process private long mergeSortAndCountInversions(int[] arr) { // Create a temporary array required for merge sort to avoid re-allocations int[] temp = new int[arr.length]; return _mergeSort(arr, temp, 0, arr.length - 1); } // Recursive helper for merge sort private long _mergeSort(int[] arr, int[] temp, int left, int right) { long invCount = 0; if (left < right) { int mid = left + (right - left) / 2; // Calculate mid-point to prevent overflow invCount += _mergeSort(arr, temp, left, mid); // Count inversions in left half invCount += _mergeSort(arr, temp, mid + 1, right); // Count inversions in right half invCount += merge(arr, temp, left, mid, right); // Count inversions during merge } return invCount; } // Merges two sorted subarrays and counts inversions between them private long merge(int[] arr, int[] temp, int left, int mid, int right) { long invCount = 0; // Copy elements from original array to temp array for merging for (int i = left; i <= right; i++) { temp[i] = arr[i]; } int i = left; // Pointer for the left subarray (in temp) int j = mid + 1; // Pointer for the right subarray (in temp) int k = left; // Pointer for the merged array (in arr) while (i <= mid && j <= right) { if (temp[i] <= temp[j]) { // If element from left half is smaller or equal, no inversion with right half element arr[k++] = temp[i++]; } else { // If element from right half is smaller, it means temp[j] forms an inversion // with temp[i] and all remaining elements in the left subarray (from i to mid). arr[k++] = temp[j++]; invCount += (mid - i + 1); // Increment inversion count } } // Copy any remaining elements from the left subarray (if the right subarray was exhausted) while (i <= mid) { arr[k++] = temp[i++]; } // Copy any remaining elements from the right subarray (if the left subarray was exhausted) // These elements are already in their correct sorted relative positions and don't form new inversions. while (j <= right) { arr[k++] = temp[j++]; } return invCount; } }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.