JavaScript Map and Big O Notation

Understanding the time complexity (Big O notation) of Map operations is essential for building efficient algorithms. In this post, we’ll explore the Big O notation of Map operations and how they can be utilized to improve algorithm performance.

Big O Notation of Map Operations

1. Insertion (set): O(1)

   • Adding a key-value pair to a Map is generally an O(1) operation because it involves hashing the key and placing the value in the appropriate bucket.

2. Deletion (delete): O(1)

   • Deleting a key-value pair from a Map is O(1) on average, as it typically involves hashing the key and removing the associated value from the bucket.

3. Check Existence (has): O(1)

   • Checking if a key exists in a Map is an O(1) operation, requiring the key to be hashed and then checking the corresponding bucket.

4. Retrieval (get): O(1)

   • Retrieving the value associated with a key in a Map is O(1) because the key is hashed and the corresponding value is looked up directly.

5. Iteration: O(n)

   • Iterating over all key-value pairs in a Map is O(n), where n is the number of elements in the Map.

Practical Examples of Using Map for Efficient Algorithms

Example 1: Counting Occurrences in an Array

Problem: Count the number of occurrences of each element in an array.

Solution: Use a Map to store the element as the key and its count as the value.

function countOccurrences(arr) {
  const map = new Map()
  for (let item of arr) {
    map.set(item, (map.get(item) || 0) + 1)
  }
  return map
}

const numbers = [1, 2, 2, 3, 3, 3, 4]
console.log(countOccurrences(numbers))
// Output: Map { 1 => 1, 2 => 2, 3 => 3, 4 => 1 }

Analysis:

• Time Complexity: O(n) for iterating over the array and updating the count in the Map.
• Space Complexity: O(n) for storing the counts of unique elements.

Example 2: Checking for Duplicate Keys

Problem: Check if a list of objects has duplicate keys.

Solution: Use a Map to track keys and detect duplicates efficiently.

function hasDuplicateKeys(objects) {
  const map = new Map()
  for (let obj of objects) {
    for (let key of Object.keys(obj)) {
      if (map.has(key)) {
        return true
      }
      map.set(key, true)
    }
  }
  return false
}

const objects = [{ a: 1 }, { b: 2 }, { a: 3 }]
console.log(hasDuplicateKeys(objects)) // Output: true

Analysis:

• Time Complexity: O(n), where n is the total number of keys.
• Space Complexity: O(n) for storing the keys in the Map.

Example 3: Grouping Elements by Key

Problem: Group an array of objects by a common key.

Solution: Use a Map to group objects by a specific key.

function groupBy(arr, key) {
  const map = new Map()
  for (let obj of arr) {
    const keyValue = obj[key]
    if (!map.has(keyValue)) {
      map.set(keyValue, [])
    }
    map.get(keyValue).push(obj)
  }
  return map
}

const people = [
  { name: 'John', age: 25 },
  { name: 'Jane', age: 30 },
  { name: 'Jim', age: 25 },
]

console.log(groupBy(people, 'age'))
// Output: Map { 25 => [{ name: 'John', age: 25 }, { name: 'Jim', age: 25 }], 30 => [{ name: 'Jane', age: 30 }] }

Analysis:

• Time Complexity: O(n) for iterating over the array and grouping objects by the specified key.
• Space Complexity: O(n) for storing the groups in the Map.

Example 4: Efficient LRU Cache Implementation

Problem: Implement a Least Recently Used (LRU) cache using a Map.

Solution: Use a Map where the keys represent cache entries and the values represent the data.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.cache = new Map()
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1
    }
    const value = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, value)
    return value
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key)
    }
    this.cache.set(key, value)
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value)
    }
  }
}

const lru = new LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
console.log(lru.get(1)) // Output: 1
lru.put(3, 3)
console.log(lru.get(2)) // Output: -1 (2 is evicted)

Analysis:

• Time Complexity: O(1) for both get and put operations.
• Space Complexity: O(n) for storing the cache entries in the Map.

Summary

• Insertion, Deletion, Existence Check, and Retrieval: All have O(1) average time complexity, making Map highly efficient for operations requiring key-value pairs and fast lookups.
• Iteration: O(n) time complexity for iterating over all elements.

By leveraging Map for fast key-value storage and retrieval, you can optimize algorithms that involve frequent lookups, caching, or grouping of data.