Arrays (1D)
Fixed-size container for elements of the same type.
Complexities: Access = O(1), Insert/Delete = O(n)
int[] arr = {1, 2, 3};
System.out.println(arr[1]); // 2
■ Use when:
- Fixed size known ahead of time
- Frequency arrays, prefix sums, DP tables
■ Typical Problems:
- Rotate Array
- Maximum Subarray (Kadane)
- Move Zeroes
Arrays (2D / Matrices)
Array of arrays, useful for grids and DP.
Complexities: Access = O(1), Traversal = O(n·m)
int[][] mat = new int[3][3];
mat[0][0] = 1;
■ Use when:
- Grid problems (Number of Islands, Flood Fill)
- 2D DP (Edit Distance, Minimum Path Sum)
- Matrix manipulation (rotate, transpose, spiral)
■ Typical Problems:
- Number of Islands
- Rotate Matrix
- Spiral Order Traversal
Strings & StringBuilder
String is immutable, StringBuilder is mutable and efficient for concatenation.
Complexities: String concat = O(n), StringBuilder append = O(1) amortized
StringBuilder sb = new StringBuilder();
sb.append("abc").append("def");
■ Use when:
- Use StringBuilder for heavy concatenation
- String for fixed text
■ Typical Problems:
- Valid Palindrome
- Reverse String
- Longest Common Prefix
ArrayList
Resizable array implementation of List.
Complexities: Access = O(1), Insert/Delete mid = O(n)
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
■ Use when:
- Need dynamic arrays
- Fast random access
■ Typical Problems:
- Pascal's Triangle
- Merge Intervals
LinkedList
Doubly linked list, supports O(1) insert/remove at ends.
Complexities: Access = O(n), Insert/Delete ends = O(1)
LinkedList<Integer> ll = new LinkedList<>();
ll.addFirst(1);
ll.addLast(2);
■ Use when:
- Rare in OAs
- Needed when frequent end operations
■ Typical Problems:
- Design Browser History
- LRU Cache (alt implementation)
HashSet
Unordered collection of unique elements.
Complexities: Add/Remove/Contains = O(1) avg
Set<Integer> set = new HashSet<>();
set.add(1);
set.contains(1);
■ Use when:
- Check duplicates
- Membership queries
■ Typical Problems:
- Contains Duplicate
- Intersection of Two Arrays
TreeSet
Sorted set implemented as a balanced BST.
Complexities: Add/Remove/Search = O(log n)
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);
ts.add(10);
■ Use when:
- Need sorted unique elements
- floor/ceiling queries
■ Typical Problems:
- Third Maximum Number
- Longest Consecutive Sequence
HashMap
Key → Value pairs with average O(1) operations.
Complexities: Get/Put/Remove = O(1) avg
Map<String,Integer> map = new HashMap<>();
map.put("a",1);
■ Use when:
- Frequency counting
- Complements (Two Sum)
- Prefix sums
■ Typical Problems:
- Two Sum
- Group Anagrams
- Subarray Sum Equals K
TreeMap
Sorted map based on balanced BST.
Complexities: Get/Put/Remove = O(log n)
TreeMap<Integer,String> tm = new TreeMap<>();
tm.put(1,"a");
■ Use when:
- Ordered map
- Range queries
- floor/ceiling keys
■ Typical Problems:
- My Calendar I
- Data Stream as Disjoint Intervals
ArrayDeque
Double-ended queue supporting stack and queue ops.
Complexities: Add/Remove at ends = O(1)
Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(1);
dq.addFirst(2);
■ Use when:
- BFS queues
- Stacks (push/pop)
- Sliding window problems
■ Typical Problems:
- Valid Parentheses
- Sliding Window Maximum
PriorityQueue (Heap)
Binary heap implementation, min-heap by default.
Complexities: Insert/Remove = O(log n), Peek = O(1)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(5);
■ Use when:
- Top-K problems
- Greedy scheduling
■ Typical Problems:
- Kth Largest Element
- Top K Frequent Elements
Adjacency List (Graph)
Graph representation as list of lists.
Complexities: Build = O(V+E), Traversal = O(V+E)
List<List<Integer>> g = new ArrayList<>();
for(int i=0;i<n;i++) g.add(new ArrayList<>());
■ Use when:
- Graph traversal BFS/DFS
- Connected components
■ Typical Problems:
- Number of Provinces
- Course Schedule
Union-Find (DSU)
Disjoint Set Union structure for connectivity.
Complexities: Find/Union ≈ O(1) with path compression
class DSU {
int[] parent;
DSU(int n){ parent = IntStream.range(0,n).toArray(); }
int find(int x){ return parent[x]==x?x:(parent[x]=find(parent[x])); }
void union(int a,int b){ parent[find(a)] = find(b); }
}
■ Use when:
- Connectivity queries
- Kruskal's MST
■ Typical Problems:
- Number of Connected Components
- Redundant Connection
Trie
Prefix tree for efficient string search.
Complexities: Insert/Search = O(L) where L = word length
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord;
}
■ Use when:
- Autocomplete
- Word search problems
■ Typical Problems:
- Implement Trie
- Word Search II
BitSet / Bitmask
Compact boolean set for state representation.
Complexities: Set/Test/Clear = O(1)
BitSet bs = new BitSet();
bs.set(1);
System.out.println(bs.get(1)); // true
■ Use when:
- State compression DP
- Subset generation
■ Typical Problems:
- Maximum AND Sum
- Generate Subsets
