Map

Java

Methods

NavigableMap

Prefix	Suffix	Parameter	Comparison
ceiling	entry/key	key	>=
floor	entry/key	key	<=
higher	entry/key	key	>
lower	entry/key	key	<
head	map	toKey	<
head	map	toKey, inclusive	< or <=
tail	map	fromKey	>=
tail	map	fromKey, inclusive	> or >=
(poll)first	entry		least
(poll)last	entry		greatest
descending	map
sub	map	fromKey, fromInclusive, toKey, toInclusive
descending	keySet
navigable	keySet

SortedMap

Prefix	Suffix	Parameter	Comparison
head	map	toKey	<
tail	map	fromKey	>=
first	key		lowest
last	key		highest
sub	map	fromKey, toKey	[)

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if the sorted map is to correctly implement the Map interface.

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

Sort Map by Values

Ascending

Map<String, Integer> unSortedMap = getUnSortedMap();
LinkedHashMap<String, Integer> sortedMap = new LinkedHashMap<>();
 
unSortedMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByValue())
    .forEachOrdered(e -> sortedMap.put(e.getKey(), e.getValue()));

Descending

Map<String, Integer> unSortedMap = getUnSortedMap();
LinkedHashMap<String, Integer> sortedMap = new LinkedHashMap<>();
 
unSortedMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .forEachOrdered(e -> sortedMap.put(e.getKey(), e.getValue()));

Sort Map by Values then Keys

    .sorted(Comparator.comparing(Map.Entry<String, Integer>::getValue)
            .thenComparing(Comparator.comparing(Map.Entry<String, Integer>::getKey)))

    .sorted(Map.Entry.<String, Integer>comparingByValue()
            .thenComparing(Map.Entry.comparingByKey()))

Key with the max value in a map

Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();

• default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
• default boolean remove(Object key, Object value)
• V put(K key, V value)
  • Returns the previous value associated with key, or null if there was no mapping for key.
• default V replace(K key, V value)

   if (map.containsKey(key)) {
     return map.put(key, value);
   } else
     return null;
  

Map.Entry

• static <K,V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue()

C++

Methods

• iterator upper_bound(const key_type& k) -> “higher”

• iterator lower_bound(const key_type& k) -> “ceiling”

• map::operator[]
  • “find-or-add”
  • Default constructible and assignable
• map::at: same as [] except throws an exception when the key doesn’t exist
• map::insert: doesn’t modify the map if the key exists
• map::emplace: parameters are forwareded to the constructor of the object stored in the container. No copies.

The following example is from this post:

K t; V u;
std::map<K,V> m;           // std::map<K,V>::value_type is std::pair<const K,V>
    
m.insert( std::pair<const K,V>(t,u) );
m.insert( std::map<K,V>::value_type(t,u) );
m.insert( std::make_pair<const K,V>(t,u) );

m.insert( std::make_pair(t,u) );

m.emplace(t,u);

@walletfox. (2018). Overview of std::map’s Insertion / Emplacement Methods in C++17

Making File Names Unique

public String[] getFolderNames(String[] names) {
    String[] folders = new String[names.length];
    // name: smallest valid integer
    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i < names.length; i++) {
        String curr = names[i];
        int count = map.getOrDefault(curr, 1);
        while (map.containsKey(curr)) {
            curr = names[i] + "(" + count++ + ")";
        }
        map.put(curr, 1);
        map.put(names[i], count);
        folders[i] = curr;
    }
    return folders;
}

Vowel Spellchecker

public String[] spellchecker(String[] wordlist, String[] queries) {
    Set<String> words = new HashSet<>();
    Map<String, String> cap = new HashMap<>(), vowel = new HashMap<>();

    for (String w : wordlist) {
        words.add(w);
        String lower = w.toLowerCase(), devowel = lower.replaceAll("[aeiou]", "#");
        cap.putIfAbsent(lower, w);
        vowel.putIfAbsent(devowel, w);
    }

    int n = queries.length;
    String[] result = new String[n];
    for (int i = 0; i < n; i++) {
        String q = queries[i];
        if (words.contains(q)) {
            result[i] = q;
            continue;
        }

        String lower = q.toLowerCase(), devowel = lower.replaceAll("[aeiou]", "#");
        if (cap.containsKey(lower)) {
            result[i] = cap.get(lower);
            continue;
        }

        if (vowel.containsKey(devowel)) {
            result[i] = vowel.get(devowel);
            continue;
        }
        result[i] = "";
    }
    return result;
}

Tuple with Same Product

public int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int p = nums[i] * nums[j];
            int c = map.getOrDefault(p, 0);
            // acculumates the count so we don't need a second pass
            count += c * 8;
            map.put(p, c + 1);
        }
    }
    return count;
}

Buckets

Contains Duplicate III

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    Map<Long, Long> buckets = new HashMap<>();
    // capacity of each bucket
    long capacity = (long)t + 1;

    for (int i = 0; i < nums.length; i++) {
        long bucket = Math.floorDiv(nums[i], capacity);

        // checks if the bucket already contains a number
        if (buckets.containsKey(bucket)) {
            return true;
        }

        // checks the neighbor buckets
        if (buckets.containsKey(bucket - 1) && Math.abs(nums[i] - buckets.get(bucket - 1)) < capacity) {
            return true;
        }

        if (buckets.containsKey(bucket + 1) && Math.abs(nums[i] - buckets.get(bucket + 1)) < capacity) {
            return true;
        }

        buckets.put(bucket, (long)nums[i]);

        // removes out-of-window buckets
        if (i >= k) {
            buckets.remove(Math.floorDiv(nums[i - k], capacity));
        }
    }

    return false;
}

TreeMap

Depth of BST Given Insertion Order

Array of Doubled Pairs

public boolean canReorderDoubled(int[] arr) {
    Map<Integer, Integer> count = new TreeMap<>();
    for (int a : arr) {
        count.put(a, count.getOrDefault(a, 0) + 1);
    }

    for (int a : count.keySet()) {
        if (count.get(a) == 0) {
            continue;
        }

        int pair = a < 0 ? a / 2 : a * 2;
        // if a is an odd negative, we can't find a pair that pair * 2 == a
        // if count(a) > count(pair), there's not enough pair to cancel a out
        // since we are scanning in ascending order
        if ((a < 0 && a % 2 != 0) || count.get(a) > count.getOrDefault(pair, 0)) {
            return false;
        }

        count.put(pair, count.get(pair) - count.get(a));
    }
    return true;
}

Find Array Given Subset Sums

public int[] recoverArray(int n, int[] sums) {
    Arrays.sort(sums);

    return recover(sums).stream().mapToInt(i -> i).toArray();
}

private List<Integer> recover(int[] sums) {
    if (sums.length == 1) {
        return new ArrayList<>();
    }

    Map<Integer, Long> count = Arrays.stream(sums).boxed()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    // considers the subset sums of arr [x, y, z]
    // sums can be split into two groups:
    //     A             B
    // [0, y, z] + [x, x + y, x + z]

    // sorts sums
    // d = sums[1] - sums[0]
    // then x == -d or x == d

    // proof:
    // s0, s1, ..., s_k, where k = 2 ^ n
    // since one of the subsets is empty, there always exists s_i == 0

    // - if there's at least one negative subset sum s_0
    //   - if there's only one negative subset sum
    //     - d = arr[m], where arr[m] is the least non-negative
    //       x = d
    //       e.g. arr = [-3, 1]
    //     - d = -arr[0], x = -d
    //       e.g. arr = [-3, 4]
    //   - if there're more than one negative subset sum
    //     - d = -arr[m], where arr[m] < 0 and |arr[m]| is the least
    //       x = -d
    // - else
    //   - if there're more than one subset sum == 0
    //     d = 0, x = d = 0
    //   - else
    //     d = arr[m], where arr[m] is the least
    //     x = d
    int d = sums[1] - sums[0];

    // splits the subset sums into two groups A and B
    int[] groupA = new int[sums.length / 2], groupB = new int[sums.length / 2];
    // by default, Group A + x == Group B
    boolean toSwap = false;
    // iterates the sums ascendingly, finds the matching b == a + d
    int i = 0;
    for (int a : sums) {
        int b = a + d;
        if (count.getOrDefault(a, 0l) > 0) {
            count.put(b, count.get(b) - 1);
            count.put(a, count.get(a) - 1);

            // when b == 0, we can swap Group B and Group A
            // and take -d as the new x
            if (b == 0) {
                toSwap = true;
            }

            groupA[i] = a;
            groupB[i] = b;
            i++;
        }
    }

    // arr is sorted
    List<Integer> arr = recover(toSwap ? groupB : groupA);
    // arr.add(x)
    arr.add(toSwap ? -d : d);

    return arr;
}

Dynamic Programming

Odd Even Jump

public int oddEvenJumps(int[] arr) {
    int n  = arr.length;
    // whether has higher or lower later elements
    boolean[] hasHigher = new boolean[n], hasLower = new boolean[n];
    hasHigher[n - 1] = hasLower[n - 1] = true;

    // {element, index}
    TreeMap<Integer, Integer> map = new TreeMap<>();
    map.put(arr[n - 1], n - 1);

    // in reverse order
    int count = 1;
    for (int i = n - 2; i >= 0; i--) {
        var c = map.ceilingEntry(arr[i]);
        var f = map.floorEntry(arr[i]);
        if (c != null) {
            hasHigher[i] = hasLower[c.getValue()];
        }
        if (f != null) {
            hasLower[i] = hasHigher[f.getValue()];
        }

        // odd numbered jumps are higher
        if (hasHigher[i]) {
            count++;
        }
        map.put(arr[i], i);
    }
    return count;
}

Another solution is using Stack (next greater/less element).

Non Generic Map

Word Pattern

public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");

    if (words.length != pattern.length()) {
        return false;
    }

    // non generic map
    // <Object, Object>
    Map map = new HashMap<>();
    // the type of i must be Integer
    // since there's no auto boxing for non generic map integer values
    for (Integer i = 0; i < words.length; i++) {
        char c = pattern.charAt(i);
        String w = words[i];

        map.putIfAbsent(c, i);
        map.putIfAbsent(w, i);

        if (map.get(c) != map.get(w)) {
            return false;
        }
    }
    return true;
}