Advanced Array Manipulation

Welcome to another pivotal lesson in your Kotlin interview preparation. In this lesson, we will concentrate on Advanced Array Manipulation Techniques, focusing on the representation and manipulation of arrays (Array) and lists (List) directly, without relying on high-level built-in functions. This topic is indispensable when preparing for technical interviews, as many problems involve performing manual operations on these data structures to optimize performance or demonstrate a deep understanding of memory and indices.

Take, for example, the logic required to rotate an array by k positions. While some languages offer shortcuts, understanding how to manipulate indices manually is a vital skill. To rotate an array to the right by k, the last k elements move to the front, and the remaining elements shift forward.

In Kotlin, we can achieve this by calculating the effective number of rotations (using the remainder operator % to handle cases where k is greater than the array size) and then building a new list by iterating through specific index ranges.

The code looks like this:

fun rotateArray(nums: List<Int>, k: Int): List<Int> {
    if (nums.isEmpty()) return nums
    
    val n = nums.size
    val effectiveK = k % n
    val rotated = mutableListOf<Int>()

    // Step 1: Add the last 'effectiveK' elements to the new list
    for (i in (n - effectiveK) until n) {
        rotated.add(nums[i])
    }

    // Step 2: Add the remaining elements from the beginning of the original list
    for (i in 0 until (n - effectiveK)) {
        rotated.add(nums[i])
    }

    return rotated
}

fun main() {
    val nums = listOf(1, 2, 3, 4, 5, 6, 7)
    val k = 3
    val result = rotateArray(nums, k)
    println(result)  // Output: [5, 6, 7, 1, 2, 3, 4]
}

In this example, when k = 3 and the list size is 7, n - effectiveK is 4.

1. The first loop picks elements from indices 4 through 6 (values 5, 6, 7) and adds them to our new list.
2. The second loop picks elements from indices 0 through 3 (values 1, 2, 3, 4) and appends them.

The result is the correctly rotated list: [5, 6, 7, 1, 2, 3, 4].

In technical interviews, you are often asked to perform these manipulations in-place to achieve $O(1)$ space complexity. Instead of creating a new list, you modify the original array directly.

A common strategy for in-place rotation is the Reversal Algorithm:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

Visualization ($k=3$):

• Original: [1, 2, 3, 4, 5, 6, 7]
• Reverse all: [7, 6, 5, 4, 3, 2, 1]
• Reverse first $k$ (3): [5, 6, 7, 4, 3, 2, 1]
• Reverse remaining $n-k$ (4): [5, 6, 7, 1, 2, 3, 4]

fun reverse(nums: IntArray, start: Int, end: Int) {
    var left = start
    var right = end
    while (left < right) {
        val temp = nums[left]
        nums[left] = nums[right]
        nums[right] = temp
        left++
        right--
    }
}

fun rotateInPlace(nums: IntArray, k: Int) {
    val n = nums.size
    if (n == 0) return
    val effectiveK = k % n
    
    reverse(nums, 0, n - 1)           // Reverse all
    reverse(nums, 0, effectiveK - 1)  // Reverse first k
    reverse(nums, effectiveK, n - 1)  // Reverse the rest
}

This approach is highly efficient as it avoids the memory overhead of creating a secondary data structure.