# map

***

**1. Store Key-Value Pairs**

```cpp
map<string, int> myMap;
myMap["apple"] = 10;
myMap["banana"] = 20;
```

**2. Sort Keys**

```cpp
map<char, int> myMap;
myMap['a'] = 1;
myMap['b'] = 2;
myMap['c'] = 3;

for (auto it = myMap.begin(); it != myMap.end(); ++it) {
  cout << it->first << " " << it->second << endl;
}
```

**3. Count Occurrences**

```cpp
map<string, int> myMap;
for (const string &word : words) {
  myMap[word]++;
}
```

**4. Find Maximum and Minimum**

```cpp
map<int, int> myMap;
myMap.insert(pair<int, int>(1, 10));
myMap.insert(pair<int, int>(2, 20));
myMap.insert(pair<int, int>(3, 30));

auto maxElement = myMap.rbegin();
auto minElement = myMap.begin();
```

**5. Check for Existence**

```cpp
map<int, string> myMap;
if (myMap.count(1)) {
  cout << "Key 1 exists" << endl;
} else {
  cout << "Key 1 does not exist" << endl;
}
```

**6. Iterate over Keys**

```cpp
map<int, string> myMap;
for (const auto &key : myMap) {
  cout << key.first << endl;
}
```

**7. Iterate over Values**

```cpp
map<int, string> myMap;
for (const auto &value : myMap) {
  cout << value.second << endl;
}
```

**8. Reverse Iteration**

```cpp
map<int, string> myMap;
for (auto it = myMap.rbegin(); it != myMap.rend(); ++it) {
  cout << it->first << " " << it->second << endl;
}
```

**9. Clear Map**

```cpp
map<int, string> myMap;
myMap.clear();
```

**10. Erase Element**

```cpp
map<int, string> myMap;
myMap.erase(2);
```

**11. Modify Element**

```cpp
map<int, string> myMap;
myMap[2] = "modified";
```

**12. Insert Multiple Elements**

```cpp
map<int, string> myMap;
map<int, string> anotherMap = {{1, "one"}, {2, "two"}, {3, "three"}};
myMap.insert(anotherMap.begin(), anotherMap.end());
```

**13. Construct from Array**

```cpp
int arr[3] = {1, 2, 3};
string values[3] = {"one", "two", "three"};
map<int, string> myMap(arr, arr + 3, values);
```

**14. Construct from Vector**

```cpp
vector<pair<int, string>> vec = {{1, "one"}, {2, "two"}, {3, "three"}};
map<int, string> myMap(vec.begin(), vec.end());
```

**15. Use as Hash Table**

```cpp
unordered_map<int, int> myMap;
myMap[1]++;
myMap[2]++;
myMap[3]++;
```

**16. Implement Frequency Counter**

```cpp
unordered_map<string, int> myMap;
for (const string &word : words) {
  myMap[word]++;
}
```

**17. Implement LRU Cache**

```cpp
class LRUCache {
 private:
  map<int, int> cache;
  int capacity;

 public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    if (!cache.count(key)) return -1;
    cache[key];  // Update access time
    return cache[key];
  }

  void put(int key, int value) {
    if (cache.count(key)) cache.erase(key);
    cache[key] = value;
    if (cache.size() > capacity) cache.erase(cache.begin());
  }
};
```

**18. Implement Two Sum**

```cpp
bool twoSum(vector<int> &nums, int target) {
  unordered_map<int, int> seen;
  for (int num : nums) {
    int complement = target - num;
    if (seen.count(complement)) return true;
    seen[num]++;
  }
  return false;
}
```

**19. Implement Find Anagrams**

```cpp
vector<int> findAnagrams(string s, string p) {
  vector<int> result;
  unordered_map<char, int> freqP;
  unordered_map<char, int> freqS;

  for (char c : p) freqP[c]++;

  int l = 0, r = 0;
  while (r < s.size()) {
    freqS[s[r]]++;

    while (freqS[s[r]] > freqP[s[r]]) {
      freqS[s[l]]--;
      l++;
    }

    if (freqS == freqP) result.push_back(l);

    r++;
  }

  return result;
}
```

**20. Implement Group Anagrams**

```cpp
vector<vector<string>> groupAnagrams(vector<string> &strs) {
  unordered_map<string, vector<string>> groups;
  for (string &str : strs) {
    string sortedStr = str;
    sort(sortedStr.begin(), sortedStr.end());
    groups[sortedStr].push_back(str);
  }
  vector<vector<string>> result;
  for (auto &group : groups) {
    result.push_back(group.second);
  }
  return result;
}
```

**21. Implement Merge Intervals**

```cpp
vector<vector<int>> merge(vector<vector<int>> &intervals) {
  map<int, int> merged;
  for (auto &interval : intervals) {
    merged[interval[0]] = max(merged[interval[0]], interval[1]);
  }

  vector<vector<int>> result;
  for (auto &interval : merged) {
    result.push_back({interval.first, interval.second});
  }
  return result;
}
```

**22. Implement Phone Directory**

```cpp
class PhoneDirectory {
 private:
  unordered_map<int, int> available;
  int min;
  int max;

 public:
  PhoneDirectory(int maxNumbers) : min(0), max(maxNumbers - 1) {}

  int get() {
    if (available.empty()) return -1;
    int number = min;
    available.erase(min);
    min++;
    return number;
  }

  void release(int number) {
    if (number < min || number > max) return;
    available[number] = number;
  }
};
```

**23. Implement Word Ladder**

```cpp
int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
  unordered_map<string, vector<string>> graph;
  for (string word : wordList) {
    for (int i = 0; i < word.size(); i++) {
      string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
      graph[pattern].push_back(word);
    }
  }

  queue<string> q;
  q.push(beginWord);
  int level = 1;

  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      string word = q.front();
      q.pop();
      if (word == endWord) return level;

      for (int i = 0; i < word.size(); i++) {
        string pattern = word.substr(0, i) + '*' + word.substr(i + 1);
        for (string neighbor : graph[pattern]) {
          q.push(neighbor);
        }
      }
    }
    level++;
  }

  return 0;
}
```

**24. Implement Minimum Height Trees**

```cpp
vector<int> findMinHeightTrees(int n, vector<pair<int, int>> &edges) {
  unordered_map<int, vector<int>> graph;
  for (auto &edge : edges) {
    graph[edge.first].push_back(edge.second);
    graph[edge.second].push_back(edge.first);
  }

  vector<int> degree(n, 0);
  for (auto &neighbors : graph) {
    degree[neighbors.first] = neighbors.second.size();
  }

  queue<int> leaves;
  for (int i = 0; i < n; i++) {
    if (degree[i] == 1) leaves.push(i);
  }

  while (n > 2) {
    int size = leaves.size();
    n -= size;
    while (size--) {
      int leaf = leaves.front();
      leaves.pop();
      for (int neighbor : graph[leaf]) {
        degree[neighbor]--;
        if (degree[neighbor] == 1) leaves.push(neighbor);
      }
    }
  }

  vector<int> result;
  while (!leaves.empty()) {
    result.push_back(leaves.front());
    leaves.pop();
  }
  return result;
}
```

**25. Implement Clone Graph**

```cpp
class Node {
 public:
  int val;
  vector<Node *> neighbors;

  Node() : val(0), neighbors() {}
  Node(int _val) : val(_val), neighbors() {}
  Node(int _val, vector<Node *> _neighbors) : val(_val), neighbors(_neighbors) {}
};

Node *cloneGraph(Node *node) {
  unordered_map<Node *, Node *> visited;
  return clone(node, visited);
}

Node *clone(Node *node, unordered_map<Node *, Node *> &visited) {
  if (!node) return nullptr;

  if (visited.count(node)) return visited[node];

  Node *cloneNode = new Node(node->val);
  visited[node] = cloneNode;

  for (Node *neighbor : node->neighbors) {
    cloneNode->neighbors.push_back(clone(neighbor, visited));
  }

  return cloneNode;
}
```

**26. Implement Course Schedule**