Time vs Space Complexity — Optimize¶

// O(n²) time, O(1) space
func hasDuplicate(arr []int) bool {
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i] == arr[j] {
                return true
            }
        }
    }
    return false
}

// O(n) time, O(n) space — hash set
func hasDuplicate(arr []int) bool {
    seen := make(map[int]bool, len(arr))
    for _, v := range arr {
        if seen[v] {
            return true
        }
        seen[v] = true
    }
    return false
}

// O(n²) time, O(1) space
func twoSum(nums []int, target int) (int, int) {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return i, j
            }
        }
    }
    return -1, -1
}

// O(n) time, O(n) space
func twoSum(nums []int, target int) (int, int) {
    seen := make(map[int]int)
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return j, i
        }
        seen[v] = i
    }
    return -1, -1
}

// O(2^n) time, O(n) space (call stack)
func fib(n int) int {
    if n <= 1 { return n }
    return fib(n-1) + fib(n-2)
}

// O(n) time, O(1) space
func fib(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
}

// O(n) per query, O(1) space
func rangeSum(arr []int, left, right int) int {
    sum := 0
    for i := left; i <= right; i++ {
        sum += arr[i]
    }
    return sum
}

// O(n) build, O(1) per query, O(n) space
func buildPrefix(arr []int) []int {
    prefix := make([]int, len(arr)+1)
    for i, v := range arr {
        prefix[i+1] = prefix[i] + v
    }
    return prefix
}

func rangeSum(prefix []int, left, right int) int {
    return prefix[right+1] - prefix[left]
}

// O(n) per dequeue (slice copy)
type SlowQueue struct {
    data []int
}

func (q *SlowQueue) Enqueue(val int) { q.data = append(q.data, val) }
func (q *SlowQueue) Dequeue() int {
    val := q.data[0]
    q.data = q.data[1:] // O(n) — underlying array not reclaimed
    return val
}

// O(1) per dequeue — circular buffer
type FastQueue struct {
    data       []int
    head, tail int
    size, cap  int
}

func NewFastQueue(cap int) *FastQueue {
    return &FastQueue{data: make([]int, cap), cap: cap}
}

func (q *FastQueue) Enqueue(val int) {
    q.data[q.tail] = val
    q.tail = (q.tail + 1) % q.cap
    q.size++
}

func (q *FastQueue) Dequeue() int {
    val := q.data[q.head]
    q.head = (q.head + 1) % q.cap
    q.size--
    return val
}

// O(n²) time
func repeat(ch byte, n int) string {
    s := ""
    for i := 0; i < n; i++ {
        s += string(ch) // new string each iteration
    }
    return s
}

// O(n) time
import "strings"

func repeat(ch byte, n int) string {
    var sb strings.Builder
    sb.Grow(n)
    for i := 0; i < n; i++ {
        sb.WriteByte(ch)
    }
    return sb.String()
}

import "sort"

// O(n log n) time, O(n) space
func findMinMax(arr []int) (int, int) {
    sorted := make([]int, len(arr))
    copy(sorted, arr)
    sort.Ints(sorted)
    return sorted[0], sorted[len(sorted)-1]
}

// O(n) time, O(1) space
func findMinMax(arr []int) (int, int) {
    mn, mx := arr[0], arr[0]
    for _, v := range arr[1:] {
        if v < mn { mn = v }
        if v > mx { mx = v }
    }
    return mn, mx
}

// O(n²) time, O(n) space
func frequency(arr []int) map[int]int {
    freq := map[int]int{}
    for _, v := range arr {
        count := 0
        for _, w := range arr {
            if w == v { count++ }
        }
        freq[v] = count
    }
    return freq
}

// O(n) time, O(n) space
func frequency(arr []int) map[int]int {
    freq := make(map[int]int, len(arr))
    for _, v := range arr {
        freq[v]++
    }
    return freq
}

import "sort"

// O(n log n) time, O(n) space
func isSorted(arr []int) bool {
    sorted := make([]int, len(arr))
    copy(sorted, arr)
    sort.Ints(sorted)
    for i := range arr {
        if arr[i] != sorted[i] { return false }
    }
    return true
}

// O(n) time, O(1) space
func isSorted(arr []int) bool {
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i-1] { return false }
    }
    return true
}

// O(n) time, O(n) space (stack)
func factorial(n int) int {
    if n <= 1 { return 1 }
    return n * factorial(n-1)
}

// O(n) time, O(1) space
func factorial(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}