Introduction

A Map is a data structure that stores data in the form of key-value pairs.

Each key is associated with a value, allowing us to efficiently find a value using its key.

For example, a student's roll number can be used as a key and the student's name can be stored as its value.

This concept helps in understanding:

  • Key-value pairs
  • Hashing
  • Fast searching
  • Insertion and deletion
  • Frequency counting

Problem Statement

Given a collection of key-value pairs, store the data and efficiently retrieve the value associated with a given key.

For example, if the keys are student IDs and the values are student names, searching for a student ID should return the corresponding name.

Example

Input:Keys   = [101, 102, 103]
Values = ["Alice", "Bob", "Charlie"]

Search Key:
102

Output:
Bob

Explanation:
The key 102 is associated with the value "Bob".

Approach 1: Brute Force

Explanation

The brute force approach stores keys and values in separate arrays.

To find the value associated with a key, we traverse the keys one by one.

When the required key is found, we return the value at the same index.

Steps

  1. Store keys in one array.
  2. Store corresponding values in another array.
  3. Traverse the keys.
  4. Compare each key with the target key.
  5. Return the value at the matching index.

Dry Run

Input:Keys   = [101, 102, 103]
Values = ["Alice", "Bob", "Charlie"]

Search Key:
102

Check 101 → Not found
Check 102 → Found

Corresponding value:
Bob

Final Result:
Bob

Brute Force Code

Complexity Analysis

Time Complexity: O(n)

In the worst case, all keys may need to be checked.

Space Complexity: O(n)

The keys and values are stored in separate arrays.

Approach 2: Optimized Solution

Explanation

The optimized approach uses a Map.

A Map directly associates each key with its corresponding value.

Hashing allows us to find a value using its key in average O(1) time.

Steps

  1. Create an empty Map.
  2. Insert each key-value pair.
  3. Search for the required key.
  4. Retrieve its associated value.
  5. Return the result.

Dry Run

Input:Key-Value pairs:

101 → Alice
102 → Bob
103 → Charlie

Insert:
101 → Alice
102 → Bob
103 → Charlie

Search:
102

Map finds:
102 → Bob

Final Result:
Bob

Optimized Code

Complexity Analysis

Time Complexity: O(1) average

Hashing allows average constant-time lookup.

Space Complexity: O(n)

The Map stores all key-value pairs.

Common Map Operations

A Map commonly supports:

  • Insert: Add a key-value pair.
  • Search: Find a value using its key.
  • Update: Change the value associated with a key.
  • Delete: Remove a key-value pair.
  • Size: Find the number of stored pairs.

Edge Cases

  1. Empty Map: No key-value pairs are available.
  2. Key not found: The Map should indicate that the key does not exist.
  3. Duplicate key: A new value generally replaces the previous value for that key.
  4. Single key-value pair: The Map contains only one entry.
  5. Large number of entries: Hashing provides efficient average lookup.

Why This Problem is Important

Maps are commonly used for:

  1. Key-value storage
  2. Frequency counting
  3. Fast lookups
  4. Caching
  5. Grouping data

Real-World Applications

Maps are useful in:

  1. Student record systems
  2. Database indexing
  3. Caching systems
  4. Configuration storage
  5. Counting frequencies
  6. User and product lookup systems

Common Mistakes

  1. Confusing a Map with a Set.
  2. Assuming duplicate keys create multiple independent entries.
  3. Forgetting to check whether a key exists.
  4. Using an array when frequent key-based searching is required.
  5. Ignoring the difference between average and worst-case hashing performance.

Interview Tips

When a problem requires storing a relationship between a key and a value, think about using a Map.

Maps are especially useful for problems involving:

  • Frequency counting
  • Lookup tables
  • Duplicate detection
  • Grouping
  • Counting occurrences

Related Questions

  1. Introduction to Set
  2. Happy Number
  3. Two Sum
  4. Majority Element
  5. Group Anagrams

Final Takeaway

A Map stores information as key-value pairs and provides efficient access to values using their keys.

The brute force approach searches through stored keys one by one, while the optimized hashing approach provides average O(1) lookup with O(n) space.