HashMap vs TreeMap vs Sorting: Choosing the Right Tool in DSA

Default to a HashMap for every coding interview problem unless the input data requires ordered iteration, range queries, or dynamic floor and ceiling checks. If you need to find elements smaller or larger than a target value in logarithmic time, switch to a TreeMap or a sorted array immediately.

Two Sum and Frequency Counts

Take Two Sum. You receive an array of integers like [2, 7, 11, 15] and a target sum of 9. You need to find if any two numbers add up to that target.

Using a HashMap gives you O(1) average time complexity for both insertions and lookups. You iterate through the array once, calculate the complement for 2 which is 7, and check if 7 already exists in your map. It does not, so you store 2 with its index 0 and move to 7. The lookup takes constant time.

If you tried to solve this with a sorted array and binary search, your time complexity would jump to O(n log n) due to the initial sort, or your code would become a tangled mess of pointer logic. The hash map wins here because order does not matter at all. You only care about exact key matching.

Frequency counting problems follow the same rule. When an array contains strings or integers and you need to count occurrences, a hash map maps each unique element to its frequency without rearrangement overhead.

Intervals and Range Queries

Interval problems change the math entirely. Consider Merge Intervals, where you receive a list of intervals like [[1, 3], [2, 6], [8, 10], [15, 18]]. Sorting the array by starting times is mandatory before you can compare adjacent elements.

If you put these intervals into a HashMap, you lose all sense of sequence. You cannot check if interval [2, 6] overlaps with [1, 3] because hash keys have no notion of before or after. Sorting the array lets you iterate through the list sequentially and merge overlapping bounds in a single pass of O(n log n) time.

For sliding window maximum problems or finding the closest smaller element in a stream, a TreeMap is the correct choice. A TreeMap keeps keys in sorted order using a self-balancing binary search tree, usually a red-black tree. This allows lowerKey and higherKey operations to run in O(log n) time. A hash map cannot find the next largest key without scanning every single entry, which ruins your time complexity.

Memory Costs and Overhead

Data structures trade memory for time in predictable ways. A HashMap in Java allocates an array of buckets, and each entry requires a node object with pointers for the key, value, hash, and next reference. This creates significant memory overhead and cache misses because nodes scatter across the heap.

A TreeMap allocates a tree node for every single element, storing left pointers, right pointers, parent pointers, and color bits. For one hundred thousand integers, a TreeMap consumes roughly three times more memory than a primitive array storing the same data.

A sorted array is just a contiguous block of memory. It has zero object overhead per element if you use primitive arrays. When memory limits are tight in competitive programming or backend systems, sorting a primitive array and using binary search uses the least memory possible.

A Worked Example by Hand

Trace this small snippet for finding the floor of a value 5 in a dataset containing [2, 4, 6, 8].

If you use a TreeMap, calling floorKey(5) compares 5 against the root. It moves right past 2 and 4, hits 6, sees that 6 is larger than 5, and steps left to find 4. The return value is 4 in O(log n) time.

If you use an unsorted HashMap, you have no method to find the largest key smaller than 5 without iterating through all keys and tracking the maximum, which takes O(n) time. If you use a sorted array [2, 4, 6, 8], you run binary search to find the insertion point, which lands between 4 and 6, and return the element at index 1.

Your Decision Rule

Memorize this short checklist for your next practice session on DSA Tracker.

• Use a HashMap for exact lookups, frequency counts, and graph adjacency lists where order is irrelevant.
• Use a TreeMap when you need dynamic sorted keys, range iteration, or floor and ceiling queries.
• Use a sorted array when the dataset is static and you only need binary search or sequential interval processing.

Next, open a coding problem involving intervals and force yourself to write the solution using a sorted array instead of a hash map.

Keep going with practice problems and the online compiler.

Further reading: Binary search on Wikipedia.