Kotlin Built-In Time Complexity: The Interview Cheat Sheet

You switched to Kotlin because the syntax is nicer. Great call. The collections look clean. mutableListOf, sortedMapOf, ArrayDeque. None of them say new. But they're all Java underneath, and Java gotchas don't care what language you think you're writing in. This guide covers every collection you'll reach for in an interview, the exact complexity numbers, and the traps that have ended otherwise good interviews.

Java is a deadly laser aimed at your codebase. Kotlin is a blanket. Your codebase is still there.

Kotlin wraps Java beautifully. The underlying complexity is still very much there.

Kotlin Built-In Time Complexity: Full Reference Table

Structure	Access	Search	Insert (end)	Insert (mid)	Delete (end)	Delete (mid)
ArrayList	O(1)	O(n)	O(1) amort	O(n)	O(n)	O(n)
ArrayDeque	O(1)	O(n)	O(1) amort	O(n)	O(1)	O(n)
HashMap	O(1) avg	O(1) avg	O(1) avg	,	O(1) avg	,
LinkedHashMap	O(1) avg	O(1) avg	O(1) avg	,	O(1) avg	,
TreeMap	O(log n)	O(log n)	O(log n)	,	O(log n)	,
HashSet	,	O(1) avg	O(1) avg	,	O(1) avg	,
TreeSet	,	O(log n)	O(log n)	,	O(log n)	,
PriorityQueue	O(1) peek	O(n)	O(log n)	,	O(log n) poll	,

ArrayList: Your Default List

mutableListOf() gives you a MutableList<T> backed by Java's ArrayList. Random access is O(1); everything involving the middle of the list is O(n).

val list = mutableListOf(1, 2, 3)

list.add(4)          // O(1) amortized, appends to end
list.add(1, 99)      // O(n), shifts everything right of index 1
list[2]              // O(1), direct index access
list.removeAt(0)     // O(n), shifts everything left
list.remove(99)      // O(n), linear scan, then shift
list.contains(3)     // O(n), linear scan

The amortized O(1) for add at the end comes from the doubling strategy: when the backing array fills, copy everything into a 2× array. That amortization story applies here exactly as it does in Java.

One naming trap that looks innocent until it isn't: remove(element) removes by value, and removeAt(index) removes by position. In Java the compiler picks the right overload. In Kotlin you have to be explicit. On a List<Int>, list.remove(2) removes the first element with the value 2, not the element at index 2. Mix those up on a list of indices and you'll spend ten minutes convinced the list is somehow corrupted.

ArrayDeque: Stack, Queue, and Deque in One

Kotlin's kotlin.collections.ArrayDeque (stable since 1.4) is the right tool for any problem that needs both ends of a sequence. It is not Java's java.util.ArrayDeque. Kotlin's version implements MutableList, so you also get O(1) index access.

val deque = ArrayDeque<Int>()

deque.addLast(1)      // O(1) amortized, enqueue
deque.addFirst(0)     // O(1) amortized, prepend
deque.removeLast()    // O(1), pop from stack end
deque.removeFirst()   // O(1), dequeue from front
deque.first()         // O(1), peek front
deque.last()          // O(1), peek back
deque[2]              // O(1), index access via MutableList

Use ArrayDeque for BFS queues, monotonic stacks, and sliding window deques. It beats LinkedList on cache performance because it's a circular buffer instead of a pointer chain. For a stack: addLast/removeLast. For a queue: addLast/removeFirst. No extra imports, no second data structure.

HashMap vs TreeMap: O(1) or O(log n)?

The answer depends entirely on whether you need sorted keys.

val freq = HashMap<Char, Int>()

freq['a'] = (freq['a'] ?: 0) + 1        // O(1) avg

// idiomatic frequency counting
freq.getOrPut('a') { 0 }++              // O(1) avg, get or insert default, then increment
freq.getOrElse('z') { 0 }               // O(1) avg, read with fallback, no insert

HashMap is O(1) average for get, put, containsKey, and remove. Worst case is O(n) when everything hashes to the same bucket, which only happens with adversarial inputs or a genuinely broken hashCode(). The full analysis of why O(1) holds on average is worth one read.

TreeMap (via sortedMapOf() or a Java import) stores every key in a red-black tree. Everything is O(log n), and in exchange you get sorted iteration plus range queries.

val sorted = sortedMapOf("b" to 2, "a" to 1, "c" to 3)

sorted.firstKey()          // O(log n), minimum key
sorted.lastKey()           // O(log n), maximum key
sorted.headMap("b")        // O(log n) to create; O(1) to iterate next
sorted.floorKey("b")       // O(log n), greatest key <= "b"
sorted.ceilingKey("b")     // O(log n), smallest key >= "b"

Any problem that asks for "all keys in range [lo, hi]" or "nearest key to X" is a TreeMap problem. LinkedHashMap is HashMap with insertion-order iteration: put/get stay O(1) average with a small constant overhead to maintain the ordering list.

HashSet vs TreeSet: Same Story

val seen = HashSet<Int>()
seen.add(42)         // O(1) avg
seen.contains(42)    // O(1) avg
seen.remove(42)      // O(1) avg

val ordered = sortedSetOf(5, 2, 8, 1)  // TreeSet
ordered.first()      // O(log n), minimum
ordered.last()       // O(log n), maximum
ordered.headSet(5)   // O(log n), elements strictly < 5
ordered.floor(5)     // O(log n), greatest element <= 5

Default to HashSet for membership checks. Switch to TreeSet when the problem asks for min, max, nearest element, or a sorted range.

LinkedHashSet preserves insertion order with O(1) add/contains/remove. It iterates in the order elements were inserted, not natural sort order. Different from TreeSet. Easy to mix up when you're tired.

PriorityQueue: Min-Heap by Default, and That Will Surprise You

Kotlin has no native heap. You use java.util.PriorityQueue. It is a min-heap by default. The smallest element surfaces first. If you're coming from C++ where priority_queue is a max-heap by default, you will get this wrong on your first Kotlin interview and you'll remember it forever after.

import java.util.PriorityQueue

val minHeap = PriorityQueue<Int>()
minHeap.add(5)           // O(log n)
minHeap.peek()           // O(1), view minimum, no removal
minHeap.poll()           // O(log n), remove and return minimum

// Max-heap
val maxHeap = PriorityQueue<Int>(reverseOrder())
maxHeap.add(5)
maxHeap.poll()           // returns largest element first

// Custom comparator for pairs, sort by second element
val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
pq.add(Pair(1, 3))
pq.add(Pair(2, 1))
pq.poll()                // returns (2, 1), second = 1 is smallest

Two traps. First: remove(element) on a PriorityQueue is O(n), not O(log n). It does a linear scan to find the element. If you need fast decrease-key, use lazy deletion: push a new entry with the updated priority and skip stale entries when polling. Second: contains(element) is also O(n). Don't use a PriorityQueue as a membership set.

For custom types without Comparable, always pass a comparator. Forgetting one throws a ClassCastException at runtime, not compile time.

String Concatenation in a Loop Is O(n²)

Kotlin strings are Java strings: immutable, UTF-16 encoded, O(n) to construct.

val s = "hello"
s.length              // O(1), cached field
s[2]                  // O(1), direct char access
s.substring(1, 4)     // O(k), allocates a new string of length k
s.contains("ell")     // O(n·m), naive search
s + " world"          // O(n), allocates a new string

// Building strings iteratively
val sb = StringBuilder()
repeat(n) { sb.append('x') }  // O(1) amortized per append
sb.toString()                  // O(n), one final copy at the end

String concatenation inside a loop allocates a brand new string every iteration. That's O(n²) total. Use StringBuilder for anything iterative. Joining a known list is fine with joinToString, which builds the result in one pass:

listOf("a", "b", "c").joinToString(", ")  // O(n)

Functional Operations Are Not Free

Kotlin's collection extensions look zero-cost. They are not. Each eager operation allocates a new list.

val nums = listOf(1, 2, 3, 4, 5)

nums.filter { it > 2 }       // O(n) time, O(n) space, new list
nums.map { it * 2 }          // O(n) time, O(n) space, new list
nums.find { it > 2 }         // O(n) worst case, O(1) space, short-circuits
nums.any { it > 4 }          // O(n) worst case, O(1) space, short-circuits
nums.count { it > 2 }        // O(n), always a full scan
nums.sortedBy { it }         // O(n log n), returns a NEW sorted list, does not modify nums
nums.groupBy { it % 2 }      // O(n), HashMap<Int, List<Int>>

Chain three transforms together and you've allocated three intermediate collections. The time complexity looks fine. The space complexity is a different story.

Homer Simpson looking buff labeled "O(1) time complexity" in the top panel; Homer looking overweight with Marge looking alarmed in the bottom panel labeled "O(n^2) space complexity"

Functional chaining in Kotlin: your time is O(n), your allocations are not.

Use asSequence() to make the chain lazy and defer all allocation to the final collect:

nums.asSequence()
    .filter { it > 2 }
    .map { it * 2 }
    .toList()                // one allocation at the end, not per intermediate step

In an interview, this rarely changes your asymptotic class. Mentioning it unprompted shows you understand the real cost model, which scores on the "tradeoff communication" dimension.

Sorting: `sortedBy` vs `sortBy` Is Not Cosmetic

val mutable = mutableListOf(3, 1, 2)
mutable.sort()                          // O(n log n) in-place, stable (Timsort)
mutable.sortBy { -it }                  // descending, in-place
mutable.sortWith(compareBy { it % 3 }) // custom Comparator, in-place

val immutable = listOf(3, 1, 2)
immutable.sorted()                      // O(n log n), returns NEW list
immutable.sortedBy { -it }             // descending, new list

One non-obvious trap: IntArray.sort() uses Java's dual-pivot quicksort, which is unstable. MutableList<Int>.sort() uses Timsort, which is stable. If you're sorting objects and stability matters, use the list sort.

binarySearch on a sorted list is O(log n):

val sorted = mutableListOf(1, 3, 5, 7)
sorted.binarySearch(5)     // returns index 2
sorted.binarySearch(4)     // returns negative insertion point

Five Traps That Bite Candidates

removeAt vs remove look identical. list.remove(2) removes the first element equal to the integer 2. list.removeAt(2) removes the element at index 2. On a list of indices, these do opposite things. The compiler will not warn you. You will find out at runtime, probably under pressure.

IntArray vs Array<Int>. IntArray is a primitive int[]. Array<Int> is a boxed Integer[]. In tight loops over large arrays, the boxing overhead is real. Default to IntArray when the element type is a primitive.

PriorityQueue remove(element) is O(n). Looks like a heap operation. Is a linear scan. Do not call it inside a loop expecting logarithmic behavior. Use lazy deletion instead: push updated entries, skip stale ones on poll.

sortedBy does not sort in place. On a List, sortedBy returns a new sorted list and leaves the original untouched. On a MutableList, the in-place method is sortBy. Two names, one mutates, one doesn't. Easy to mix up at minute twenty of a forty-five-minute interview.

getOrPut vs getOrElse. getOrPut(key) { default } inserts the default if the key is absent. getOrElse(key) { default } returns the default without inserting. Use getOrPut for frequency maps. Use getOrElse for safe reads where inserting a default would be wrong.

The Hard Part Is Saying It While You Type

Knowing the table is step one. The harder part is explaining your choice of HashMap vs TreeMap while you type, without going silent. The Java built-in time complexity guide covers the underlying JVM collections in more depth. The Kotlin for coding interviews guide covers the broader idioms.

SpaceComplexity runs voice-based mock interviews with rubric feedback across communication, problem-solving, and technical dimensions. The goal is to reach a point where "I'll use a TreeMap here because I need sorted key order and floor/ceiling queries" comes out automatically, without breaking your coding flow.

Key Takeaways

ArrayList: O(1) get and amortized append, O(n) for inserts/deletes anywhere else
ArrayDeque (kotlin.collections): O(1) at both ends plus O(1) index access via MutableList
HashMap/HashSet: O(1) average; contains and remove(element) on PriorityQueue are O(n)
TreeMap/TreeSet: O(log n) for everything; use when you need sorted order, min/max, or range queries
PriorityQueue: O(log n) add/poll, O(1) peek, O(n) for contains and remove-by-value; min-heap by default
String is immutable; StringBuilder.append is O(1) amortized, avoid + in loops
Functional ops (filter, map) each allocate a new list; chain with asSequence() to defer
sortedBy returns a new list; sortBy sorts in place, they are different methods