Java Built-in Time Complexity: The Interview Cheat Sheet

You open LeetCode, write a clean Java solution, and freeze when the interviewer asks "what's the complexity of that contains call?" Most engineers guess O(log n). Sometimes it's O(n). That wrong answer doesn't just cost you a point on complexity analysis. It signals that you picked a data structure you don't actually understand. This is the Java built-in time complexity reference that covers every collection you'll reach for in an interview.

Three Families, One Decision

Java gives you three families of collections.

Hash-backed (HashMap, HashSet, ArrayDeque, ArrayList): O(1) per operation on average, O(n) in the degenerate case.

Tree-backed (TreeMap, TreeSet): O(log n) guaranteed, ordered, supports range queries.

Linear structures (LinkedList, PriorityQueue): some operations are cheap, some are embarrassingly slow, and the gotchas live in the slow ones.

When you see O(1) average, that means amortized constant under a good hash distribution. Java 8 treeifies collision chains at 8 entries, so HashMap degrades to O(log n) not O(n) in practice. At interview level, "O(1)" is the right answer.

ArrayList: Mostly Fine, One Trap

Operation	Complexity
`get(i)`	O(1)
`set(i, e)`	O(1)
`add(e)` (end)	O(1) amortized
`add(i, e)` (middle)	O(n)
`remove(i)`	O(n)
`remove(Object)`	O(n)
`contains(o)`	O(n)
`size()`	O(1)
`clear()`	O(n)

The amortized O(1) for end-append comes from doubling. Java's ArrayList grows by 50% per resize, but the geometric series still gives O(1) amortized. See how dynamic arrays work for the derivation.

clear() is O(n) because it null-references every slot. Don't assume O(1) just because "clearing" sounds cheap.

LinkedList gives O(1) addFirst/addLast/removeFirst/removeLast, but O(n) get(i) because it walks the chain. For most interview patterns, ArrayDeque beats LinkedList for both ends due to cache locality. The performance difference is measurable.

HashMap and Friends

Operation	HashMap	LinkedHashMap	TreeMap
`get`	O(1) avg	O(1) avg	O(log n)
`put`	O(1) avg	O(1) avg	O(log n)
`remove`	O(1) avg	O(1) avg	O(log n)
`containsKey`	O(1) avg	O(1) avg	O(log n)
`containsValue`	O(n)	O(n)	O(n)
`firstKey`/`lastKey`	N/A	N/A	O(log n)
`floorKey`/`ceilingKey`	N/A	N/A	O(log n)

containsValue is O(n) for all three. There's no inverse index. Call it in a loop and your algorithm is secretly O(n²).

LinkedHashMap is HashMap plus a doubly-linked list stitching entries in insertion order. Every put/remove updates two extra pointers. The complexity stays O(1), but use it when you need LRU cache semantics: access-order mode is one constructor flag away.

TreeMap is the most underused tool in Java interview prep. "Find the largest key smaller than X" is floorKey(X), and it's O(log n). Reach for it whenever you need ordered access instead of sorting the whole collection.

HashSet and TreeSet

Both are backed by their Map counterparts (the value is a dummy PRESENT object), so complexity is identical:

Operation	HashSet	TreeSet
`add`	O(1) avg	O(log n)
`contains`	O(1) avg	O(log n)
`remove`	O(1) avg	O(log n)
`first`/`last`	N/A	O(log n)
`floor`/`ceiling`	N/A	O(log n)

TreeSet exposes headSet(e), tailSet(e), and subSet(lo, hi) as live views in O(1). Iterating k elements costs O(k).

PriorityQueue: The One That Bites

Operation	Complexity
`offer`/`add`	O(log n)
`poll`	O(log n)
`peek`	O(1)
`contains`	O(n)
`remove(Object)`	O(n)
`size`	O(1)

contains and remove(Object) are both O(n). The heap stores elements sorted by priority, not by value. Finding a specific object requires a linear scan. Call pq.contains(x) inside a loop and you've written an O(n²) algorithm without a single nested loop in sight. The interviewer will notice before you do.

The fix: maintain a separate HashSet for O(1) membership, or use lazy deletion (push a new entry, mark old ones invalid, skip them on pop).

PriorityQueue is a min-heap by default. For a max-heap:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// or
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

That second form has an overflow bug. If b is Integer.MIN_VALUE and a is positive, b - a wraps to a large positive, reversing the comparison. Always use Integer.compare(b, a), not b - a.

ArrayDeque: Retire Stack Already

Use this over Stack and LinkedList when you need a deque.

Operation	Complexity
`addFirst`/`addLast`	O(1) amortized
`removeFirst`/`removeLast`	O(1)
`peekFirst`/`peekLast`	O(1)
`contains`	O(n)
`size`	O(1)

Backed by a circular array, so adjacent elements share cache lines. Java's Stack extends Vector, which is synchronized and adds overhead you don't need. If an interviewer sees you write new Stack<>(), they'll quietly question what decade you learned Java in. Use ArrayDeque.

Sorting: The Stability Trap Nobody Warns You About

Method	Complexity	Stable?	Algorithm
`Arrays.sort(int[])`	O(n log n)	No	Dual-pivot quicksort
`Arrays.sort(Integer[])`	O(n log n)	Yes	Timsort
`Collections.sort(List)`	O(n log n)	Yes	Timsort
`Arrays.binarySearch`	O(log n)	N/A	Binary search

Arrays.sort on a primitive array is not stable. Box to Integer[] first if you need stability. This isn't trivia: if you sort by one key and then by another expecting preserved relative order, int[] silently breaks it.

Arrays.sort is in-place. Clone first if you need the original: int[] copy = arr.clone().

Arrays.binarySearch requires a sorted array. Call it on an unsorted array and it returns garbage. No exception thrown. No warning. Just quietly wrong answers.

Strings Cost More Than You Think

Operation	String	StringBuilder
`charAt(i)`	O(1)	O(1)
`length()`	O(1)	O(1)
`substring(i, j)`	O(n)	N/A
`equals`	O(n)	N/A
`indexOf(String)`	O(n·m)	O(n·m)
`append`	N/A	O(1) amortized
`insert(i, s)`	N/A	O(n)
`delete(i, j)`	N/A	O(n)
`reverse()`	N/A	O(n)
`toString()`	O(1)	O(n)

String.substring copies characters. Since Java 7 update 6, there is no shared backing array. Every call allocates a new char array of size j - i. In Java 6 it was O(1) but caused a famous memory leak: the substring held a reference to the full backing array.

String concatenation with + in a loop is O(n²) because each + allocates a new String. Use StringBuilder.append() instead. O(1) amortized per call, O(n) to finalize with toString().

The Traps That End Interviews

1. List<Integer> remove ambiguity. list.remove(0) removes by index (O(n) shift). list.remove(Integer.valueOf(0)) removes by value (O(n) scan). Overload resolution happens at compile time on argument type. On a List<Integer>, calling remove(0) gives you index removal, not value removal. This is the kind of bug that compiles fine, runs, and produces wrong output at exactly the wrong moment.

2. Integer == outside the cache range. Integer caches values from -128 to 127. Integer a = 200; Integer b = 200; a == b is false. When comparing boxed integers from a map or priority queue, use .equals(). Using == on Integer objects is a bug that only shows up at runtime with large inputs. Interviewers test this deliberately.

3. HashMap iteration cost. keySet(), values(), and entrySet() return live views in O(1). Iterating is O(n + capacity), where capacity is the internal table size, not the entry count. After many removes, capacity stays large. The precise cost is O(n + capacity), not O(n). At interview scale this rarely matters, but if someone asks you to be precise about iteration cost, now you know.

Java Built-in Time Complexity: Quick Reference

Structure	Get	Add	Remove	Search	Notes
`ArrayList`	O(1)	O(1) amortized	O(n)	O(n)	Best for random access
`LinkedList`	O(n)	O(1) ends	O(1) ends	O(n)	Use `ArrayDeque` instead
`ArrayDeque`	O(1) ends	O(1) amortized	O(1) ends	O(n)	Stack and queue
`HashMap`	O(1) avg	O(1) avg	O(1) avg	O(1) avg	No order
`LinkedHashMap`	O(1) avg	O(1) avg	O(1) avg	O(1) avg	Insertion/access order
`TreeMap`	O(log n)	O(log n)	O(log n)	O(log n)	Sorted, range ops
`HashSet`	N/A	O(1) avg	O(1) avg	O(1) avg
`TreeSet`	N/A	O(log n)	O(log n)	O(log n)	Sorted
`PriorityQueue`	O(1) peek	O(log n)	O(log n) poll	O(n)	Min-heap default
`String`	O(1)	N/A	N/A	O(n·m)	Immutable, `substring` O(n)
`StringBuilder`	O(1)	O(1)	O(n)	O(n·m)	Mutable

Say the Complexity Out Loud

When you pick a data structure, narrate it. "I'll use a TreeMap here so I can do floor lookups in O(log n)" tells the interviewer you know what you're paying for. Reaching for HashMap and then needing sorted access codes you into a corner.

If you want to practice explaining these decisions under real pressure, SpaceComplexity runs voice-based mock interviews where an AI interviewer probes your complexity reasoning in real time. Reading this table once is not the same as defending it when someone asks "but what's the worst case on that contains call?"