Array

Array merupakan struktur data paling mendasar yang menyimpan elemen-elemen dengan tipe data sama dalam lokasi memori yang berurutan. Bayangkan array seperti deretan kotak penyimpanan yang bersebelahan, di mana setiap kotak memiliki nomor indeks mulai dari nol. Ketika Anda perlu mengakses elemen tertentu, Anda bisa langsung melompat ke posisi tersebut tanpa harus melewati elemen lainnya.

String pada dasarnya adalah array dari karakter, meskipun dalam Go string bersifat immutable yang artinya tidak bisa diubah setelah dibuat. Operasi pada string sering melibatkan pembuatan string baru daripada memodifikasi yang sudah ada.

Kompleksitas Operasi

Memahami kompleksitas waktu sangat penting karena ini menentukan seberapa efisien kode Anda ketika data bertambah besar. Untuk array, akses berdasarkan indeks memiliki kompleksitas O(1) atau waktu konstan karena komputer bisa langsung menghitung alamat memori dari indeks tersebut. Pencarian elemen tertentu memerlukan O(n) karena dalam kasus terburuk Anda harus memeriksa semua elemen. Penyisipan atau penghapusan di tengah array juga O(n) karena elemen-elemen setelahnya harus digeser.

Contoh Implementasi: Two Pointers Technique

Teknik two pointers sangat berguna untuk masalah yang melibatkan pencarian pasangan atau pemrosesan dari dua arah. Mari kita lihat implementasi untuk menemukan apakah ada dua angka dalam array yang dijumlahkan menghasilkan target tertentu.

go

package main

import (
    "fmt"
    "sort"
)

// TwoSum mencari dua angka dalam array yang jika dijumlahkan sama dengan target
// Kompleksitas Waktu: O(n log n) untuk sorting + O(n) untuk two pointers = O(n log n)
// Kompleksitas Ruang: O(1) jika tidak menghitung space untuk sorting
func TwoSum(nums []int, target int) []int {
    // Pertama kita sort array agar bisa menggunakan two pointers
    // Ini memungkinkan kita untuk bergerak dengan logika: jika sum terlalu besar,
    // gerakkan pointer kanan ke kiri; jika terlalu kecil, gerakkan pointer kiri ke kanan
    sort.Ints(nums)
    
    left := 0
    right := len(nums) - 1
    
    // Loop selama pointer belum bertemu
    for left < right {
        currentSum := nums[left] + nums[right]
        
        if currentSum == target {
            // Kita menemukan pasangan yang tepat
            return []int{nums[left], nums[right]}
        } else if currentSum < target {
            // Sum terlalu kecil, perlu angka yang lebih besar
            // Karena array sudah sorted, gerakkan pointer kiri ke kanan
            left++
        } else {
            // Sum terlalu besar, perlu angka yang lebih kecil
            // Gerakkan pointer kanan ke kiri
            right--
        }
    }
    
    // Tidak ada pasangan yang ditemukan
    return []int{}
}

// IsPalindrome memeriksa apakah string adalah palindrome
// Kompleksitas Waktu: O(n) karena kita hanya perlu memeriksa setengah string
// Kompleksitas Ruang: O(1) karena hanya menggunakan dua pointer
func IsPalindrome(s string) bool {
    left := 0
    right := len(s) - 1
    
    // Bandingkan karakter dari kedua ujung bergerak ke tengah
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    
    return true
}

Studi Kasus: Mencari Subarray dengan Sum Maksimum (Kadane's Algorithm)

Permasalahan ini muncul dalam banyak skenario nyata, misalnya mencari periode waktu dengan profit tertinggi dalam trading saham. Kadane's algorithm adalah solusi elegant yang menggunakan dynamic programming.

// MaxSubarraySum mencari sum maksimum dari subarray yang berurutan
// Kompleksitas Waktu: O(n) - satu kali pass melalui array
// Kompleksitas Ruang: O(1) - hanya menggunakan beberapa variabel
func MaxSubarraySum(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    // maxSoFar menyimpan maximum sum yang pernah ditemukan
    // maxEndingHere menyimpan maximum sum yang berakhir di posisi saat ini
    maxSoFar := nums[0]
    maxEndingHere := nums[0]
    
    // Intuisi: di setiap posisi, kita memutuskan apakah lebih baik
    // melanjutkan subarray yang ada atau memulai yang baru dari posisi ini
    for i := 1; i < len(nums); i++ {
        // Apakah lebih baik menambah nums[i] ke subarray yang ada,
        // atau memulai subarray baru dari nums[i]?
        maxEndingHere = max(nums[i], maxEndingHere+nums[i])
        
        // Update maximum global jika kita menemukan yang lebih besar
        maxSoFar = max(maxSoFar, maxEndingHere)
    }
    
    return maxSoFar
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // Test Two Sum
    nums := []int{2, 7, 11, 15}
    target := 9
    result := TwoSum(nums, target)
    fmt.Printf("Two Sum: %v\n", result) // Output: [2 7]
    
    // Test Palindrome
    fmt.Printf("Is 'racecar' palindrome? %v\n", IsPalindrome("racecar")) // true
    fmt.Printf("Is 'hello' palindrome? %v\n", IsPalindrome("hello"))     // false
    
    // Test Max Subarray
    nums2 := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    fmt.Printf("Max Subarray Sum: %d\n", MaxSubarraySum(nums2)) // Output: 6 ([4,-1,2,1])
}

Penjelasan Kompleksitas Kadane's Algorithm

Kadane's algorithm sangat efisien karena hanya memerlukan satu pass melalui array, menghasilkan kompleksitas waktu O(n). Dibandingkan dengan pendekatan brute force yang memeriksa semua kemungkinan subarray dengan kompleksitas O(n²) atau O(n³), ini adalah peningkatan yang sangat signifikan. Kompleksitas ruang O(1) berarti algoritma ini hanya menggunakan jumlah memori tetap terlepas dari ukuran input, karena kita hanya perlu melacak dua variabel.