Largest with Same Parity Adjacent Swaps

Problem Overview

You may swap two neighbors only when they share the same parity.

Intuition

You may swap two neighbors only when they share the same parity. That means an even can bubble past other evens, and an odd past other odds, but neither can cross a value of the opposite parity. So the array breaks into maximal runs of equal parity, and inside each run every permutation is reachable. The lexicographically largest array is obtained by sorting every run in descending order and leaving the run boundaries fixed.

Algorithm

1Walk the array while the current run keeps the same parity bit.
2When the run ends, if it has more than one element, sort that subarray ascending and reverse it to get descending order.
3Start the next run at the first index with a different parity.
4Copy the finished array into a result list and return it.

Example Walkthrough

Input: arr = [1, 3, 5, 2, 4, 6]

1. The first run is the odds 1, 3, 5, which sort descending to 5, 3, 1.
2. The second run is the evens 2, 4, 6, which sort descending to 6, 4, 2.
3. The runs stay separated because an odd and an even cannot swap.

Output: [5, 3, 1, 6, 4, 2]

Common Pitfalls

• Use a bit test for parity. In Java, a negative odd number has remainder -1 under %, so comparing % 2 values can split one odd run.
• Values cannot jump over a different parity. Sorting the whole array would be wrong.
• A single-element run is already optimal; skip sorting it.
• Descending order inside each run is required for the lexicographically largest answer, not ascending.

Largest with Same Parity Adjacent Swaps.java

Java

// Approach: Adjacent swaps are allowed only between equal parity, so values
// cannot cross a parity change. The array splits into maximal same-parity
// runs, and each run may be permuted freely. For the lexicographically
// largest result, sort every run in descending order, then emit the array.
// Complexity: O(n log n) time, O(n) space for the result list.
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public ArrayList<Integer> lexicographicallyLargest(int[] arr) {
        int n = arr.length;
        int i = 0;
        while (i < n) {
            int j = i + 1;
            int parity = arr[i] & 1;
            while (j < n && (arr[j] & 1) == parity)
                j++;
            if (j - i > 1) {
                Arrays.sort(arr, i, j);
                for (int l = i, r = j - 1; l < r; l++, r--) {
                    int t = arr[l];
                    arr[l] = arr[r];
                    arr[r] = t;
                }
            }
            i = j;
        }

        ArrayList<Integer> res = new ArrayList<>(n);
        for (int x : arr)
            res.add(x);
        return res;
    }
}

Was this solution helpful?