You're solving a problem and you realize: "I need to know where I saw this value before."
Should you store the first index? The last index? All indices? How do you handle duplicates?
This is the gap between knowing you need indices and mastering the index mapping pattern.
The index mapping pattern is a fundamental hash map technique where you store element positions for instant lookup. It appears in 40+ LeetCode problems, from "Two Sum" to "Contains Duplicate II" to "Find All Anagrams." But the pattern isn't just "store indices"—it's a systematic approach to deciding what positions to track and how.
This guide will teach you:
Master this, and position-tracking problems become pattern recognition.
The index mapping pattern uses a hash map to store where each element appears in an array, enabling O(1) position lookup.
Structure:
Example:
nums = [7, 2, 5, 2, 8]
# Map value to index
index_map = {
7: 0,
2: 3, # Last occurrence
5: 2,
8: 4
}Without hash map:
# Find where value 5 appears - O(n)
for i, num in enumerate(nums):
if num == 5:
return iWith hash map:
# Build once - O(n)
index_map = {num: i for i, num in enumerate(nums)}
# Lookup - O(1)
index = index_map[5]Trade-off: Spend O(n) space to save repeated O(n) searches.
Imagine a parking lot:
Use index mapping when:
Strong index mapping signals:
vs. Frequency counter:
vs. Hash set:
vs. Sorting:
When to use: Need most recent occurrence
# Store last index (overwrite on duplicate)
index_map = {}
for i, num in enumerate(nums):
index_map[num] = i # Overwrites previousExample problems:
When to use: Need earliest occurrence
# Store first index (don't overwrite)
index_map = {}
for i, num in enumerate(nums):
if num not in index_map:
index_map[num] = i # Only store firstExample problems:
When to use: Need all occurrences
from collections import defaultdict
# Store all indices
index_map = defaultdict(list)
for i, num in enumerate(nums):
index_map[num].append(i)Example problems:
Do you need all occurrences?
├─ Yes → Store list of indices
└─ No → Do you need first or last?
├─ First → Store if not exists
└─ Last → Always overwriteFor more on handling duplicates, see Handling Duplicates in Hash Maps.
def storeLastIndex(nums: List[int]) -> Dict[int, int]:
"""
Store last occurrence of each element.
Time: O(n)
Space: O(k) where k = number of distinct elements
"""
index_map = {}
for i, num in enumerate(nums):
index_map[num] = i # Overwrites previous
return index_map
# Example
nums = [1, 2, 3, 2, 1]
# Result: {1: 4, 2: 3, 3: 2}def storeFirstIndex(nums: List[int]) -> Dict[int, int]:
"""
Store first occurrence of each element.
Time: O(n)
Space: O(k)
"""
index_map = {}
for i, num in enumerate(nums):
if num not in index_map:
index_map[num] = i # Only store first
return index_map
# Example
nums = [1, 2, 3, 2, 1]
# Result: {1: 0, 2: 1, 3: 2}from collections import defaultdict
def storeAllIndices(nums: List[int]) -> Dict[int, List[int]]:
"""
Store all occurrences of each element.
Time: O(n)
Space: O(n) worst case
"""
index_map = defaultdict(list)
for i, num in enumerate(nums):
index_map[num].append(i)
return index_map
# Example
nums = [1, 2, 3, 2, 1]
# Result: {1: [0, 4], 2: [1, 3], 3: [2]}// Store last index
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
indexMap.put(nums[i], i);
}
// Store first index
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
indexMap.putIfAbsent(nums[i], i);
}
// Store all indices
Map<Integer, List<Integer>> indexMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
indexMap.putIfAbsent(nums[i], new ArrayList<>());
indexMap.get(nums[i]).add(i);
}// Store last index
const indexMap = new Map();
for (let i = 0; i < nums.length; i++) {
indexMap.set(nums[i], i);
}
// Store first index
const indexMap = new Map();
for (let i = 0; i < nums.length; i++) {
if (!indexMap.has(nums[i])) {
indexMap.set(nums[i], i);
}
}
// Store all indices
const indexMap = new Map();
for (let i = 0; i < nums.length; i++) {
if (!indexMap.has(nums[i])) {
indexMap.set(nums[i], []);
}
indexMap.get(nums[i]).push(i);
}Problem: Find two numbers that sum to target, return their indices.
Why index mapping: Need to return indices, not values.
def twoSum(nums: List[int], target: int) -> List[int]:
"""
Use index mapping to find complement.
Store index as we go (last occurrence).
Time: O(n)
Space: O(n)
"""
index_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in index_map:
return [index_map[complement], i]
index_map[num] = i # Store last index
return []Key insight: Store index as value, check for complement before adding.
Why last index works: We check before adding, so we never use the same element twice.
For detailed analysis, see Two Sum Pattern.
Problem: Check if array contains duplicates within distance k.
Why index mapping: Need to track distance between occurrences.
def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
"""
Store last seen index, check distance.
Time: O(n)
Space: O(min(n, k))
"""
index_map = {}
for i, num in enumerate(nums):
if num in index_map:
# Check distance from last occurrence
if i - index_map[num] <= k:
return True
# Update to current index (last occurrence)
index_map[num] = i
return FalseTrace example:
nums = [1, 2, 3, 1], k = 3
i=0: num=1, not in map, add {1: 0}
i=1: num=2, not in map, add {1: 0, 2: 1}
i=2: num=3, not in map, add {1: 0, 2: 1, 3: 2}
i=3: num=1, in map! distance = 3 - 0 = 3 <= 3, return TrueKey insight: Always update to latest index to track most recent occurrence.
Problem: Find the first non-repeating character's index.
Why first index: Need earliest unique character.
from collections import Counter
def firstUniqChar(s: str) -> int:
"""
Count frequencies, then find first unique.
Time: O(n)
Space: O(1) - at most 26 characters
"""
# Count frequencies
freq = Counter(s)
# Find first character with frequency 1
for i, char in enumerate(s):
if freq[char] == 1:
return i
return -1Alternative (store first index):
def firstUniqChar(s: str) -> int:
# Store first index and count
index_map = {}
for i, char in enumerate(s):
if char not in index_map:
index_map[char] = [i, 1] # [first_index, count]
else:
index_map[char][1] += 1 # Increment count
# Find minimum index with count 1
result = float('inf')
for first_idx, count in index_map.values():
if count == 1:
result = min(result, first_idx)
return result if result != float('inf') else -1Key insight: Store first index, track count separately.
Problem: Find all start indices of anagrams of p in s.
Why all indices: Need to return all starting positions.
from collections import Counter
def findAnagrams(s: str, p: str) -> List[int]:
"""
Use sliding window + frequency counter.
Collect all valid starting indices.
Time: O(n)
Space: O(1) - at most 26 characters
"""
if len(p) > len(s):
return []
result = []
p_count = Counter(p)
window_count = Counter(s[:len(p)])
if window_count == p_count:
result.append(0)
# Slide window
for i in range(len(p), len(s)):
# Add new character
window_count[s[i]] += 1
# Remove old character
left_char = s[i - len(p)]
window_count[left_char] -= 1
if window_count[left_char] == 0:
del window_count[left_char]
# Check if anagram
if window_count == p_count:
result.append(i - len(p) + 1)
return resultKey insight: Collect all valid indices as we find them.
For "within distance k" problems:
def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
"""
Use sliding window to keep map size <= k.
Time: O(n)
Space: O(min(n, k))
"""
window = set()
for i, num in enumerate(nums):
if num in window:
return True
window.add(num)
# Keep window size <= k
if len(window) > k:
window.remove(nums[i - k])
return FalseOptimization: Use set instead of map (only need presence, not index).
# If you only need to check existence, not position
seen = set() # Instead of index_map = {}
for num in nums:
if num in seen:
return True
seen.add(num)Space saved: Set is more memory efficient than dict.
For arrays with limited range:
def findDuplicates(nums: List[int]) -> List[int]:
"""
Find duplicates in array where 1 <= nums[i] <= n.
Use array itself as hash map.
Time: O(n)
Space: O(1)
"""
result = []
for num in nums:
index = abs(num) - 1
if nums[index] < 0:
# Already seen
result.append(abs(num))
else:
# Mark as seen
nums[index] = -nums[index]
return resultTrade-off: Modifies input, only works for specific constraints.
For more optimization techniques, see Hash Map Memory Optimization.
❌ Wrong:
# Storing index as key, value as value
index_map[i] = num # Can't look up by value!✅ Correct:
# Store value as key, index as value
index_map[num] = i❌ Wrong (inconsistent):
# Sometimes overwrites, sometimes doesn't
if random.choice([True, False]):
index_map[num] = i✅ Correct (explicit choice):
# Always overwrite (last index)
index_map[num] = i
# Or never overwrite (first index)
if num not in index_map:
index_map[num] = i❌ Wrong:
index = index_map[num] # KeyError if num not in map!✅ Correct:
# Check first
if num in index_map:
index = index_map[num]
# Or use .get()
index = index_map.get(num, -1)❌ Wrong (overkill):
# Storing list when only need one index
index_map = defaultdict(list)
for i, num in enumerate(nums):
index_map[num].append(i)
# Then only use index_map[num][0]✅ Correct:
# Just store single index
index_map = {}
for i, num in enumerate(nums):
if num not in index_map:
index_map[num] = iBuilding index map: O(n)
Querying index: O(1)
Store last/first index: O(k) where k = distinct elements
Store all indices: O(n)
Optimization: O(min(n, k)) with sliding window
The index mapping pattern is a fundamental technique for tracking element positions.
Key principles:
The templates:
# Last index
index_map[num] = i
# First index
if num not in index_map:
index_map[num] = i
# All indices
index_map[num].append(i)When to use:
Common mistakes:
Next steps:
Master index mapping, and position-tracking problems become pattern recognition.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free