# 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 | class Solution { |