Hash Maps

Overview

Hash maps (also known as hash tables or dictionaries) store data in key-value pairs. They provide O(1) average-time lookups, insertions, and deletions.

Key Characteristics

• Data stored in key-value pairs
• No duplicate keys allowed
• Unordered data structure

When to Use

• Need O(1) lookup instead of O(n) search
• Counting occurrences of elements
• Finding pairs or complements
• Tracking seen elements

Problems

Pair Sum – Unsorted

Given an array of integers, return the indexes of any two numbers that add up to a target. The order of the indexes in the result doesn't matter. If no pair is found, return an empty array.

Constraint: The same index cannot be used twice in the result.

Example 1:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9

Example 2:

Input: nums = [3, 3], target = 6
Output: [0, 1]

Explanation: Both elements are needed, but they are at different indexes.

Brute Force Approach

Check all possible pairs using two nested loops. For each element, scan the rest of the array for its complement.

This approach has a time complexity of O(n²).

Hash Map Approach

Use a single pass with a hash map to store seen values and their indexes:

• For each element, calculate its complement (target - current).
• Check if the complement exists in the hash map.
• If yes, return both indexes.
• If no, store the current value and index in the hash map.

Complexity:

• Time complexity: O(n).
• Space complexity: O(n).

Interviewing Tips

• Iterate through solutions from brute force to optimized. Don't jump to the most optimized one first.

Longest Chain of Consecutive Numbers

Find the longest chain of consecutive numbers in an array. Two numbers are consecutive if they have a difference of 1.

Example 1:

Input: nums = [1, 6, 2, 5, 8, 7, 10, 3]
Output: 4

Explanation: The longest chain of consecutive numbers is 5, 6, 7, 8.

Example 2:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4

Explanation: The longest chain is 1, 2, 3, 4.

Brute Force Approach

Sort the array, then scan through tracking the longest consecutive sequence.

This approach has a time complexity of O(n log n) due to sorting.

Hash Set Approach

Instead of sorting, use a hash set to identify chain starts and extend from there:

• Add all numbers to a hash set.
• For each number, check if it's a chain start (num - 1 doesn't exist in the set).
• If it's a start, count consecutive numbers (num + 1, num + 2, ...) that exist in the set.
• Track the maximum chain length.

Why is this O(n)? Although there's a nested while loop, each number is visited at most twice: once to check if it's a chain start, and once when extending from a previous start. Numbers that aren't chain starts are skipped immediately.

Complexity:

• Time complexity: O(n).
• Space complexity: O(n).

Verify Sudoku Board

Given a partially completed 9x9 sudoku board, determine if the current state adheres to the rules:

• Each row must contain unique numbers between 1 and 9 (or 0 for empty).
• Each column must contain unique numbers between 1 and 9 (or 0 for empty).
• Each of the nine 3x3 subgrids must contain unique numbers between 1 and 9 (or 0 for empty).

Constraint: Assume each integer on the board falls in the range [0, 9].

Example 1:

Input: board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
]
Output: true

Explanation: All rows, columns, and 3x3 subgrids contain unique non-zero values.

Example 2:

Input: board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 5]
]
Output: false

Explanation: The last column contains two 5s (at rows 0 and 8).

Brute Force Approach

For each row, column, and subgrid, use nested loops to check for duplicates by comparing every pair of elements.

This approach has a time complexity of O(n³) for an n×n board.

Hash Set Approach (Three Passes)

Use hash sets to detect duplicates efficiently:

Pass 1 - Check rows:

• For each row, add non-zero values to a hash set.
• If a value already exists in the set, return false.

Pass 2 - Check columns:

• For each column, add non-zero values to a hash set.
• If a value already exists in the set, return false.

Pass 3 - Check 3x3 subgrids:

• For each subgrid, add non-zero values to a hash set.
• If a value already exists in the set, return false.

Complexity:

• Time complexity: O(n²) where n = 9, so effectively O(81) = O(1).
• Space complexity: O(n) for the hash sets.

Optimization: All three checks can be done in a single pass using 9 row sets, 9 column sets, and 9 subgrid sets simultaneously. The subgrid index can be calculated as (row / 3) * 3 + (col / 3).

Zero Striping

For each zero in an m x n matrix, set its entire row and column to zero in place.

Example 1:

Input: matrix = [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]
Output: [
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]

Explanation: The zero at position (1, 1) causes row 1 and column 1 to become zeros.

Example 2:

Input: matrix = [
  [0, 1, 2, 0],
  [3, 4, 5, 2],
  [1, 3, 1, 5]
]
Output: [
  [0, 0, 0, 0],
  [0, 4, 5, 0],
  [0, 3, 1, 0]
]

Explanation: Zeros at (0, 0) and (0, 3) cause rows 0 and columns 0, 3 to become zeros.

Brute Force Approach

For each zero found, iterate through its entire row and column to set values to zero. Use a marker value to avoid confusion with original zeros.

This approach has a time complexity of O((m × n) × (m + n)).

Hash Set Approach

Use two hash sets to track which rows and columns need to be zeroed:

First pass:

• Scan the matrix and record row/column indexes of all zeros.

Second pass:

• For each cell, if its row or column is in the sets, set it to zero.

Complexity:

• Time complexity: O(m × n).
• Space complexity: O(m + n).

In-Place Approach

Use the first row and first column of the matrix itself as markers:

Step 1: Check if the first row or first column contains any zeros (store in separate flags).

Step 2: For cells not in the first row/column, if matrix[i][j] = 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.

Step 3: Use the markers to zero out cells (skip first row/column).

Step 4: Zero out the first row and/or column based on the flags from Step 1.

Edge case: The cell matrix[0][0] is ambiguous—it could mark either the first row or first column. Solution: use matrix[0][0] to mark the first row, and use a separate variable to track the first column.

Complexity:

• Time complexity: O(m × n).
• Space complexity: O(1).