Using Hash Table Patterns

1. Understanding Hash Table Operations

Operation	Description	Time Complexity	Notes
Insert	Adding a key-value pair to the hash table	O(1) average, O(n) worst case	May require resizing if load factor is high
Search	Finding a value by its key	O(1) average, O(n) worst case	Depends on hash function and collision resolution
Delete	Removing a key-value pair from the hash table	O(1) average, O(n) worst case	Can leave "empty" slots for probing strategies

Example: Basic Hash Table Operations

const hashTable = new Map();

// Insert
hashTable.set("name", "Alice");
hashTable.set("age", 30);

// Search
console.log(hashTable.get("name")); // "Alice"

// Delete
hashTable.delete("age");
console.log(hashTable.get("age")); // undefined

Note: Hash tables are optimized for fast lookups, insertions, and deletions. Performance heavily depends on the hash function and collision handling strategy.

2. Solving Two Sum Problem

The Two Sum problem is a classic algorithmic challenge where you're given an array of integers and a target sum, and you need to find the indices of two numbers that add up to the target.

Property	Description	Example
Input	An array of integers and a target sum	`[2, 7, 11, 15]`, `9`
Output	Indices of two numbers that sum to target	`[0, 1]`

Example: Two Sum Solution Using Hash Map

function twoSum(nums, target) {
    const numMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        numMap.set(nums[i], i);
    }
    return [];
}

Note: This solution has O(n) time complexity and O(n) space complexity, making it efficient for large inputs.

3. Solving Four Sum Problem

The Four Sum problem involves finding all unique quadruplets in an array that sum up to a target value. It's an extension of the classic 3Sum problem.

Approach	Description	Time Complexity	Space Complexity
Two Pointers + Hash Set	Fix two elements, use hash set to find remaining two elements.	`O(n^2)`	`O(n)`
Sorting + Two Pointers	Sort array, fix two elements, use two pointers for remaining.	`O(n^3)`	`O(1)`

Example: Two Pointers + Hash Set

function fourSum(nums, target) {
  const result = [];
  const n = nums.length;
  if (n < 4) return result;

  nums.sort((a, b) => a - b);
  const seen = new Set();

  for (let i = 0; i < n - 3; i++) {
    for (let j = i + 1; j < n - 2; j++) {
      const twoSum = target - nums[i] - nums[j];
      const complement = new Set();
      for (let k = j + 1; k < n; k++) {
        const third = twoSum - nums[k];
        if (complement.has(third)) {
          const quad = [nums[i], nums[j], third, nums[k]];
          const key = quad.join(',');
          if (!seen.has(key)) {
            seen.add(key);
            result.push(quad);
          }
        }
        complement.add(nums[k]);
      }
    }
  }

  return result;
}

Example: Sorting + Two Pointers

function fourSum(nums, target) {
  const result = [];
  const n = nums.length;
  if (n < 4) return result;

  nums.sort((a, b) => a - b);

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let left = j + 1;
      let right = n - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          result.push([nums[i], nums[j], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }

  return result;
}

4. Checking for Duplicate Elements

Approach	Description	Time Complexity	Space Complexity
Hash Set	Insert elements into a hash set and check for duplicates during insertion.	`O(n)`	`O(n)`
Hash Map	Use a hash map to count occurrences of each element.	`O(n)`	`O(n)`

Example: Using Hash Set to Check for Duplicates

const hasDuplicates = (arr) => {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) {
      return true;
    }
    seen.add(item);
  }
  return false;
};

// Example usage
const array1 = [1, 2, 3, 4, 5];
const array2 = [1, 2, 3, 2, 5];

console.log(hasDuplicates(array1)); // false
console.log(hasDuplicates(array2)); // true

Example: Using Hash Map to Count Occurrences

const findDuplicates = (arr) => {
  const countMap = new Map();
  const duplicates = [];

  for (const item of arr) {
    countMap.set(item, (countMap.get(item) || 0) + 1);
  }

  for (const [item, count] of countMap) {
    if (count > 1) {
      duplicates.push(item);
    }
  }

  return duplicates;
};

// Example usage
const array = [1, 2, 3, 2, 4, 5, 3];
console.log(findDuplicates(array)); // [2, 3]

Note: The hash set approach is more efficient for simply checking if duplicates exist, while the hash map approach provides additional information about how many times each duplicate appears.

5. Finding Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Approach	Time Complexity	Space Complexity	Description
Hash Set	`O(n)`	`O(n)`	Use a hash set to store all elements. For each element, check if it's the start of a sequence (i.e., `num - 1` is not in the set). If so, count consecutive elements.

Example: Finding Longest Consecutive Sequence

function longestConsecutive(nums) {
    const numSet = new Set(nums);
    let maxLength = 0;

    for (const num of numSet) {
        // Only start counting if this is the beginning of a sequence
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLength = 1;

            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }

            maxLength = Math.max(maxLength, currentLength);
        }
    }

    return maxLength;
}

// Example usage:
const nums = [100, 4, 200, 1, 3, 2];
console.log(longestConsecutive(nums)); // Output: 4 (sequence: [1, 2, 3, 4])

Note: The algorithm ensures that each element is processed at most twice (once in the outer loop, once in the inner while loop), making it linear time.

6. Implementing LRU Cache

Operation	Description	Time Complexity	Space Complexity
get(key)	Retrieve value for key if exists, else return null	`O(1)`	`O(1)`
put(key, value)	Insert or update key-value pair	`O(1)`	`O(1)`

Example: LRU Cache Implementation

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

  get(key) {
    if (!this.cache.has(key)) return null;
    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);
    } else if (this.cache.size >= this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
  }
}

Note: The Map in JavaScript maintains insertion order, which allows us to efficiently track least recently used items.

7. Implementing LFU Cache

Operation	Description	Time Complexity	Space Complexity
get(key)	Returns value if key exists, otherwise -1	O(1)	O(1)
put(key, value)	Inserts or updates key-value pair; evicts least frequently used if at capacity	O(1)	O(1)

Example: LFU Cache Implementation

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.freqMap = new Map();
    this.minFreq = 0;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    const node = this.cache.get(key);
    this.updateFreq(node);
    return node.value;
  }

  put(key, value) {
    if (this.capacity === 0) return;

    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.updateFreq(node);
    } else {
      if (this.cache.size === this.capacity) {
        const lfuList = this.freqMap.get(this.minFreq);
        const lfuNode = lfuList.shift();
        this.cache.delete(lfuNode.key);
      }

      const newNode = { key, value, freq: 1 };
      this.cache.set(key, newNode);
      this.updateFreq(newNode);
    }
  }

  updateFreq(node) {
    const oldFreq = node.freq;
    node.freq++;
    this.freqMap.get(oldFreq).delete(node.key);

    if (this.freqMap.get(oldFreq).size === 0) {
      this.freqMap.delete(oldFreq);
      if (oldFreq === this.minFreq) {
        this.minFreq++;
      }
    }

    if (!this.freqMap.has(node.freq)) {
      this.freqMap.set(node.freq, new Map());
    }
    this.freqMap.get(node.freq).set(node.key, node);
  }
}

Note: The LFU cache uses a combination of hash maps and doubly linked lists to maintain frequency tracking. When the cache is full, it removes the least frequently used item.

8. Grouping Shifted Strings

Grouping shifted strings involves identifying strings that are rotations of each other. A string s is a rotation of string t if s can be obtained by shifting the characters of t cyclically.

For example, "abcde" is a rotation of "cdeab".

Property	Description	Example
Rotation Check	Two strings are rotations if one is a substring of the other concatenated with itself.	`isRotation("abcde", "cdeab")` returns `true`
Hash Map Grouping	Use a hash map to group strings by their canonical form (e.g., sorted version or rotation class).	Group "abc", "bca", "cab" under canonical form "abc"

Example: Grouping Rotated Strings

function groupRotatedStrings(strings) {
  const groups = new Map();
  
  for (const str of strings) {
    const canonical = getCanonicalForm(str);
    if (!groups.has(canonical)) {
      groups.set(canonical, []);
    }
    groups.get(canonical).push(str);
  }
  
  return Array.from(groups.values());
}

function getCanonicalForm(str) {
  const sorted = str.split('').sort().join('');
  return sorted;
}

// Example usage:
const strings = ["abc", "bca", "cab", "xyz", "yzx", "zxy"];
console.log(groupRotatedStrings(strings));
// Output: [["abc", "bca", "cab"], ["xyz", "yzx", "zxy"]]

Note: The canonical form can be any consistent representation that uniquely identifies a rotation class, such as the lexicographically smallest rotation.

9. Finding Isomorphic Strings

Two strings are isomorphic if characters in one string can be mapped to characters in another string such that:

Each character maps to exactly one character
No two characters map to the same character

Property	Description	Example
isIsomorphic	Function to check if two strings are isomorphic	`isIsomorphic("egg", "add")`

Example: Check if two strings are isomorphic

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;

  const mapS = new Map();
  const mapT = new Map();

  for (let i = 0; i < s.length; i++) {
    const charS = s[i];
    const charT = t[i];

    if (mapS.has(charS) && mapS.get(charS) !== charT) {
      return false;
    }

    if (mapT.has(charT) && mapT.get(charT) !== charS) {
      return false;
    }

    mapS.set(charS, charT);
    mapT.set(charT, charS);
  }

  return true;
}

// Example usage:
console.log(isIsomorphic("egg", "add")); // true
console.log(isIsomorphic("foo", "bar")); // false

Note: The mapping must be bijective — each character in the first string maps to exactly one character in the second, and vice versa.

10. Finding Word Pattern Match

Property	Description	Example
pattern	Pattern string to match against	`"abba"`
words	Array of words to check for pattern match	`["cat", "dog", "dog", "cat"]`

Example: Word Pattern Matching

function wordPattern(pattern, words) {
  const map = new Map();
  const used = new Set();

  if (pattern.length !== words.length) return false;

  for (let i = 0; i < pattern.length; i++) {
    const char = pattern[i];
    const word = words[i];

    if (map.has(char)) {
      if (map.get(char) !== word) return false;
    } else {
      if (used.has(word)) return false;
      map.set(char, word);
      used.add(word);
    }
  }

  return true;
}

// Example usage:
console.log(wordPattern("abba", ["cat", "dog", "dog", "cat"])); // true
console.log(wordPattern("abba", ["cat", "dog", "dog", "fish"])); // false

11. Validating Sudoku Board

Validating a Sudoku board checks if the given 9x9 grid adheres to Sudoku rules:

Each row contains digits 1-9 without repetition
Each column contains digits 1-9 without repetition
Each of the nine 3x3 sub-boxes contains digits 1-9 without repetition

Example: Validating a Sudoku Board

function isValidSudoku(board) {
  const seen = new Set();
  
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      const cell = board[i][j];
      if (cell !== '.') {
        const rowKey = `row${i}-${cell}`;
        const colKey = `col${j}-${cell}`;
        const boxKey = `box${Math.floor(i/3)}-${Math.floor(j/3)}-${cell}`;
        
        if (seen.has(rowKey) || seen.has(colKey) || seen.has(boxKey)) {
          return false;
        }
        
        seen.add(rowKey);
        seen.add(colKey);
        seen.add(boxKey);
      }
    }
  }
  
  return true;
}

// Example usage:
const board = [
  ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
  ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
  ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
  ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
  ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
  ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
  ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
  ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
  ['.', '.', '.', '.', '8', '.', '.', '7', '9']
];

console.log(isValidSudoku(board)); // true

Property	Description	Time Complexity	Space Complexity
Hash Set	Used to store unique identifiers for rows, columns, and boxes	O(1) average for insertions and lookups	O(n²) where n = 9

12. Finding Intersection of Arrays

Approach	Description	Time Complexity	Space Complexity
Hash Set	Use a hash set to store elements from one array. Iterate through the second array and check for presence in the set.	`O(n + m)`	`O(min(n, m))`
Two Pointers (Sorted)	Sort both arrays and use two pointers to traverse them simultaneously.	`O(n log n + m log m)`	`O(1)`

Example: Hash Set Approach

function findIntersection(arr1, arr2) {
  const set = new Set(arr1);
  const result = [];

  for (const num of arr2) {
    if (set.has(num)) {
      result.push(num);
      set.delete(num); // Prevent duplicates
    }
  }

  return result;
}

// Example usage:
const arr1 = [4, 9, 5];
const arr2 = [9, 4, 9, 8, 4];
console.log(findIntersection(arr1, arr2)); // [9, 4]

Example: Two Pointers Approach

function findIntersectionSorted(arr1, arr2) {
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);

  const result = [];
  let i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] === arr2[j]) {
      result.push(arr1[i]);
      i++;
      j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

// Example usage:
const arr1 = [4, 9, 5];
const arr2 = [9, 4, 9, 8, 4];
console.log(findIntersectionSorted(arr1, arr2)); // [4, 9]

Note: The hash set approach is generally preferred for unsorted arrays due to better time complexity.