Marc Lester Tan

Here’s another easy-level LC problem. My initial solution uses two pointers: One to keep track of the index of the next even number and another for odd number.

I go through each element and if it’s an even index with an odd number, we’ll try to find the closest even number and swap them. Same thing goes with the odd index. I didn’t like the code as it is too messy and difficult to understand.

class Solution {
    fun sortArrayByParityII(A: IntArray): IntArray {
        val isEven: (Int) -> Boolean = { it % 2 == 0 }
        var evenIndex = 0
        var oddIndex = 0
        A.mapIndexed { index, i -> 
            when(isEven(index)){
                true -> if(!isEven(i)) {
                    // find the next even
                    oddIndex = index
                    for(subIndex in index until A.size){
                        if(isEven(A[subIndex])) {
                            evenIndex = subIndex
                            break
                        }
                    }
                    
                    // swap
                    val temp = A[evenIndex]
                    A[evenIndex] = A[index]
                    A[index] = temp
                } else evenIndex = index
                
                else -> if(isEven(i)) {
                    // find the next odd
                    evenIndex = index
                    for(subIndex in index until A.size){
                        if(!isEven(A[subIndex])) {
                            oddIndex = subIndex
                            break
                        }
                    }
                    
                    // swap
                    val temp = A[oddIndex]
                    A[oddIndex] = A[index]
                    A[index] = temp
                }else oddIndex = index
            }
            
        }
    
        return A
    }
}

Runtime: 340 ms, faster than 15.79% of Kotlin online submissions for Sort Array By Parity II.
Memory Usage: 39.5 MB, less than 100.00% of Kotlin online submissions for Sort Array By Parity II.

Then I figured out another solution in which we have to pass through each element and group them by their parity.

val grouped = A.groupBy { it % 2 == 0 }

This will give you a map with two entries: false key contains list of odd numbers and true key contains list of even numbers. According to the problem:

A.length % 2 == 0

So we’re sure that our array will always be divided into equal number of odd and even numbers. With this, we can say that in order to arrange the numbers into alternating parity, all we have to do is loop through N/2 or just the size of all even numbers and then assign the odd and even numbers accordingly.

class Solution {
    fun sortArrayByParityII(A: IntArray): IntArray {
        val grouped = A.groupBy { it % 2 == 0 }
        var evenList = grouped[true]
        var oddList = grouped[false]
        
        Pair(evenList, oddList).let {
            val evenList = it.first!!
            val oddList = it.second!!
            var arrayIndex = 0
            for(index in 0 until evenList.size){
                A[arrayIndex++] = evenList[index]
                A[arrayIndex++] = oddList[index]
            }
        }
        
        return A
    }
}

Code is a lot cleaner and easier to understand. Plus, it’s also a bit faster than my original implementation.

Runtime: 264 ms, faster than 57.89% of Kotlin online submissions for Sort Array By Parity II.
Memory Usage: 39.2 MB, less than 100.00% of Kotlin online submissions for Sort Array By Parity II.