Time vs Space Complexity — Find the Bug¶

func removeDuplicates(arr []int) []int {
    result := []int{} // BUG: this is O(n) space, not O(1)
    seen := map[int]bool{}
    for _, v := range arr {
        if !seen[v] {
            seen[v] = true
            result = append(result, v)
        }
    }
    return result
    // Comment says: "O(n) time, O(1) space" — WRONG!
}

// O(n) time, O(n) space — corrected comment
func removeDuplicates(arr []int) []int {
    result := []int{}
    seen := map[int]bool{}
    for _, v := range arr {
        if !seen[v] {
            seen[v] = true
            result = append(result, v)
        }
    }
    return result
}

// True O(1) auxiliary space version (modifies input, requires sorted)
func removeDuplicatesInPlace(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    writeIdx := 1
    for i := 1; i < len(arr); i++ {
        if arr[i] != arr[i-1] {
            arr[writeIdx] = arr[i]
            writeIdx++
        }
    }
    return writeIdx
}

// Comment: O(n) time, O(1) space — WRONG!
func sum(arr []int, i int) int {
    if i == len(arr) {
        return 0
    }
    return arr[i] + sum(arr, i+1) // BUG: O(n) stack frames
}

// O(n) time, O(1) space — iterative version
func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

func buildString(n int) string {
    s := ""
    for i := 0; i < n; i++ {
        s += "a" // BUG: creates new string each time → O(n²) time AND space
    }
    return s
}

import "strings"

func buildString(n int) string {
    var sb strings.Builder
    sb.Grow(n)
    for i := 0; i < n; i++ {
        sb.WriteByte('a')
    }
    return sb.String() // O(n) time and space
}

// Comment: O(n²) — WRONG!
func process(n int) {
    for i := 0; i < n; i++ { // O(n)
        fmt.Println(i)
    }
    for j := 0; j < n; j++ { // O(n)
        fmt.Println(j)
    }
    // Total: O(n) + O(n) = O(2n) = O(n), NOT O(n²)
}

// O(n) time — two sequential loops
func process(n int) {
    for i := 0; i < n; i++ {
        fmt.Println(i)
    }
    for j := 0; j < n; j++ {
        fmt.Println(j)
    }
}

// "Guaranteed O(1) lookup" — WRONG in worst case
func findElement(data map[int]bool, target int) bool {
    return data[target] // Usually O(1), but O(n) worst case with hash collisions
}

// O(1) average, O(n) worst case — corrected comment
func findElement(data map[int]bool, target int) bool {
    return data[target]
}

var cache = map[string][]byte{} // BUG: grows forever!

func getData(key string) []byte {
    if val, ok := cache[key]; ok {
        return val
    }
    val := fetchFromDB(key) // expensive
    cache[key] = val        // BUG: never evicts → memory grows without bound
    return val
}

import (
    "container/list"
    "sync"
)

type BoundedCache struct {
    mu       sync.Mutex
    capacity int
    cache    map[string]*list.Element
    order    *list.List
}

func (c *BoundedCache) Get(key string) ([]byte, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if elem, ok := c.cache[key]; ok {
        c.order.MoveToFront(elem)
        return elem.Value.([]byte), true
    }
    return nil, false
}

func processQueue(items []int) {
    for len(items) > 0 {
        item := items[0]
        items = items[1:] // BUG: doesn't free memory — underlying array persists
        process(item)
        // Memory: O(n) even though slice shrinks
        // Time per dequeue: O(1), but total GC pressure: O(n)
    }
}

func processQueue(items []int) {
    for _, item := range items { // iterate without modifying
        process(item)
    }
}
// Or use a proper queue with index:
func processQueueIdx(items []int) {
    for i := 0; i < len(items); i++ {
        process(items[i])
    }
}

// "O(log n) time, O(log n) space" — WRONG for iterative
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
    // This is iterative → O(1) space, NOT O(log n)
}

// "O(n) time" — WRONG!
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2) // BUG: O(2^n) time!
}

// O(n) time, O(1) space — iterative
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

import "sort"

// "O(n log n) is the best we can do" — WRONG!
func contains(arr []int, target int) bool {
    sort.Ints(arr) // O(n log n) time, O(log n) space
    idx := sort.SearchInts(arr, target)
    return idx < len(arr) && arr[idx] == target
}

// O(n) time, O(1) space — simple linear scan
func contains(arr []int, target int) bool {
    for _, v := range arr {
        if v == target {
            return true
        }
    }
    return false
}

// Or O(1) amortized with hash set if queried multiple times

func midpoint(left, right int) int {
    return (left + right) / 2 // BUG: overflow if left + right > MaxInt
}

func midpoint(left, right int) int {
    return left + (right-left)/2 // safe: no overflow
}

func firstHalf(arr []int) []int {
    return arr[:len(arr)/2] // BUG claim: "O(n/2) new space"
    // Reality: Go slices share underlying array — O(1) extra space
    // BUT: prevents GC of full array — effective O(n) memory retention
}