Rearrange Array in alternating pattern of positive and negative elements in Kotlin

by

To rearrange an array in an alternating pattern of positive and negative elements, you can follow these steps:

  1. Separate the array into two sub-arrays, one containing only positive elements and the other containing only negative elements. You can do this by iterating through the array and checking whether each element is positive or negative.
  2. Sort both sub-arrays in descending order. This is important to ensure that the largest elements appear first in the resulting array, regardless of whether they are positive or negative.
  3. Merge the two sub-arrays into a single array, alternating between positive and negative elements. You can do this by iterating through the two sub-arrays simultaneously, starting with the larger sub-array. For each element in the larger sub-array, add it to the resulting array and then add the corresponding element from the smaller sub-array.

Here’s some sample code in Kotlin to implement this algorithm with The space complexity of the function is O(1):

Kotlin
fun rearrangeArrayInPlace(array: IntArray) {
    // Separate the array into two sub-arrays
    var positiveIndex = 0
    for (i in array.indices) {
        if (array[i] >= 0) {
            val temp = array[i]
            for (j in i downTo positiveIndex + 1) {
                array[j] = array[j - 1]
            }
            array[positiveIndex] = temp
            positiveIndex++
        }
    }
    // Rearrange the array in alternating pattern of positive and negative elements
    var negativeIndex = positiveIndex
    for (i in array.indices step 2) {
        if (negativeIndex < array.size) {
            val temp = array[i]
            array[i] = array[negativeIndex]
            array[negativeIndex] = temp
            negativeIndex++
        } else {
            break
        }
    }
}
fun main() {
    val array = intArrayOf(-2, 3, 4, -1, 6, -9, 8, -5)

    println("Original array: ${array.joinToString(", ")}")

    rearrangeArrayInPlace(array)

    println("Rearranged array: ${array.joinToString(", ")}")
}
  1. First, we define the rearrangeArrayInPlace function that takes an IntArray as input and returns nothing (i.e., it modifies the input array in place).
  2. Inside the function, we define a variable positiveIndex that represents the current index in the input array where we should insert the next positive element.
  3. We then loop through each element in the input array using the array.indices property, which returns a range of valid indices for the array.
  4. For each element, we check if it is positive or non-negative (i.e., greater than or equal to 0).
  5. If the element is positive, we swap it with the elements before it until we reach its correct position in the array. To do this, we use an inner loop that iterates over the indices from i down to positiveIndex + 1, and swaps each element with the one before it.
  6. After swapping all the necessary elements, we insert the current positive element at index positiveIndex, and increment positiveIndex to prepare for the next positive element.
  7. Once we have moved all the positive elements to the front of the array, we have two sub-arrays: one containing only positive elements, and one containing only negative elements.
  8. We then define a variable negativeIndex that represents the current index in the input array where we should insert the next negative element.
  9. We loop through the array again using the array.indices property, this time in steps of 2 (i.e., we only consider every other element).
  10. For each even index i, we check if there is still any remaining negative element in the array (i.e., if negativeIndex < array.size).
  11. If there is, we swap the element at index i with the element at index negativeIndex. This effectively moves the next negative element to its correct position in the array, immediately after the last positive element.
  12. After swapping the elements, we increment negativeIndex to prepare for the next negative element.
  13. If there are no more negative elements remaining in the array, we break out of the loop and return the rearranged array.

The time complexity of the rearrangeArrayInPlace function is O(n), where n is the length of the input array. This is because the function loops through the input array twice, once to separate the positive and negative elements, and once to rearrange the array in alternating pattern.

The space complexity of the function is O(1), which means that the amount of extra memory used by the function is constant and does not depend on the size of the input array. This is because the function does not use any extra data structures, and instead modifies the input array in place.

Leave a Comment