TreeMap Usage

Background Knowledge

TreeMap uses a red-black tree in the background which makes sure that there are no duplicates; also maintains the elements in a sorted order.

Build a TreeMap time complexity is O(nlogn)

add, remove, containsKey, time complexity is O(logn), n is the number of elements present in TreeMap

Common Function

K ceilingKey(K key)
returns the least key greater than or equal to the given key, or null if there is no such key.

K higherKey(K key)
returns the the least key strictly greater than the given key, or null if there is no such key.

K firstKey()
This method returns the first (lowest) key currently in this map.

K lastKey()
This method returns the last (highest) key currently in this map.

K floorKey(K key)
This method returns the greatest key less than or equal to the given key, or null if there is no such key.

K lowerKey(K key)
This method returns the greatest key strictly less than the given key, or null if there is no such key.

An example

870. Advantage Shuffle

LeetCode link
This example can take advantage of the TreeMap:

Problem

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.
Example 1:
Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Solution

Pay attention to use higherKey(), not ceilingKey(), can they may contain duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int[] advantageCount(int[] a, int[] b) {
TreeMap<Integer, Integer> map = new TreeMap<>();

for (int i : a) {
map.put(i, map.getOrDefault(i, 0) + 1);
}

int[] res = new int[a.length];
for (int i = 0; i < b.length; i++) {
int cur = b[i];
Integer higher = map.higherKey(cur);

if (higher == null) {
res[i] = map.firstKey();
} else {
res[i] = higher;
}
map.put(res[i], map.get(res[i]) - 1);
if (map.get(res[i]) == 0) map.remove(res[i]);
}

return res;
}
}