Advanced List Manipulation

In this practice-oriented lesson, we're building on the foundations from Unit 1 to tackle even more sophisticated Advanced List Manipulation. Having explored fundamental array operations, we'll now focus on algorithmic patterns like the Two-Pointer Technique. Mastering these techniques allows you to navigate and transform Kotlin lists and arrays with optimal time complexity, a skill that is essential for high-level technical interviews.

Let's refine our skills with a classic problem: merging two arrays that are already sorted in ascending order into a single sorted array.

While a naive approach might involve concatenating and re-sorting, the efficient solution uses the Two-Pointer Technique. We maintain a pointer for each array, compare the elements, and move the pointers forward based on which value is smaller. This allows us to merge the arrays in $O(n + m)$ time.

Here is how we can implement this in Kotlin:

fun mergeSortedArrays(arr1: IntArray, arr2: IntArray): IntArray {
    val merged = IntArray(arr1.size + arr2.size)
    var i = 0 // Pointer for arr1
    var j = 0 // Pointer for arr2
    var k = 0 // Pointer for the result array

    // Compare elements from both arrays and add the smaller one
    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] <= arr2[j]) {
            merged[k] = arr1[i]
            i++
        } else {
            merged[k] = arr2[j]
            j++
        }
        k++
    }

    // If arr1 has remaining elements, add them
    while (i < arr1.size) {
        merged[k] = arr1[i]
        i++
        k++
    }

    // If arr2 has remaining elements, add them
    while (j < arr2.size) {
        merged[k] = arr2[j]
        j++
        k++
    }

    return merged
}

fun main() {
    val array1 = intArrayOf(1, 3, 5, 7)
    val array2 = intArrayOf(2, 4, 6, 8)
    
    val result = mergeSortedArrays(array1, array2)
    
    // Printing the result
    println(result.joinToString(" ")) 
    // Output: 1 2 3 4 5 6 7 8 
}

Expanding your toolkit with these advanced patterns is key to becoming proficient in Kotlin and acing your technical interviews. Now that we've transitioned from basic manipulation to structured algorithmic strategies, it's time to dive into the exercises. Focus on understanding the "why" behind the movement of the pointers. Let's proceed to the practice!