Foundations: Big O & Arrays in Java

Big O Notation

Complexity	Name	Example
O(1)	Constant	Array access by index
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Single loop through array
O(n log n)	Linearithmic	Merge Sort, Arrays.sort()
O(n^2)	Quadratic	Nested loops (Brute Force)
O(2^n)	Exponential	Recursive subsets
O(n!)	Factorial	Permutations

---

Java Array & ArrayList Internals

Memory Allocation

• In Java, an ArrayList grows dynamically (usually 1.5x), which is an O(1) amortized operation for add().
• Primitive arrays (int[]) are fixed-size and stored contiguously in memory - faster cache performance.

Senior Interview Tip

• String Immutability: String concatenation in a loop creates new objects each time -> O(n^2). Always use StringBuilder.
• Autoboxing Cost: ArrayList<Integer> boxes every int -> overhead. Use int[] when possible.

---

Essential Practice Problems

Problem	Difficulty	Key Learning
LC 1929: Concatenation of Array	Easy	Basic array manipulation
LC 121: Best Time to Buy/Sell Stock	Easy	One-pass min tracking
LC 238: Product of Array Except Self	Medium	Prefix/suffix without division
LC 41: First Missing Positive	Hard	In-place index marking

---

Java Collections Cheat Sheet

// HashMap - O(1) average lookup
Map<String, Integer> map = new HashMap<>();
map.getOrDefault(key, 0);           // avoid null checks
map.computeIfAbsent(key, k -> new ArrayList<>());  // lazy init

// ArrayDeque - preferred over Stack
Deque<Integer> stack = new ArrayDeque<>();  // faster than Stack class
stack.push(val);
stack.pop();

// PriorityQueue - min-heap by default
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// LinkedList as Queue
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);    // add
queue.poll();         // remove