Welcome to Hashing Sets CodeSnap

Hashing involves mapping data (like keys) to indices in a hash table for efficient lookups, insertions, and deletions, typically averaging O(1) time. Sets are collections that store unique elements, often implemented using hash tables, providing fast membership testing. This category focuses on problems solvable using hash maps (dictionaries) or hash sets to track frequencies, check for existence, group items, or detect duplicates/cycles. Problems often involve arrays or strings where quick lookups or uniqueness constraints are key, such as finding pairs (Two Sum), checking anagrams, identifying duplicates, or finding the longest consecutive sequence.

Table of Contents

• Two Sum

  Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice. A hash map enables an O(n) solution by storing seen numbers and their indices.

• Contains Duplicate

  Given an integer array `nums`, return `true` if any value appears at least twice in the array, and `false` if every element is distinct. Using a hash set allows checking for duplicates in O(1) average time per element.

• Valid Anagram

  Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`, and `false` otherwise. An anagram is formed by rearranging the letters of a word or phrase. Typically solved using character counts stored in a hash map or a fixed-size array.

• Intersection of Two Arrays

  Given two integer arrays `nums1` and `nums2`, return an array of their intersection. Each element in the result must be unique. Using hash sets for each array makes finding common elements efficient.

• Group Anagrams

  Given an array of strings `strs`, group the anagrams together. You can return the answer in any order. A hash map can be used where the key represents the character count or sorted version of a string, and the value is a list of its anagrams.

• Top K Frequent Elements

  Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order. Use a hash map to count frequencies, then use a min-heap, bucket sort, or QuickSelect to find the top k elements.

• Longest Consecutive Sequence

  Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence. An efficient O(n) solution uses a hash set to store numbers and then iterates, checking for consecutive elements only starting from the minimum number in a potential sequence.

• Isomorphic Strings

  Given two strings `s` and `t`, determine if they are isomorphic. Strings are isomorphic if `s` characters can be replaced to get `t` while preserving order. Use two hash maps to track the character mappings in both directions (s -> t and t -> s) to ensure consistency.

• First Unique Character in a String

  Given a string `s`, find the first non-repeating character in it and return its index. If one does not exist, return -1. Use a hash map to store character counts, then iterate through the string again to find the first character with a count of 1.

• Subarray Sum Equals K

  Given an array of integers `nums` and an integer `k`, find the total number of continuous subarrays whose sum equals `k`. Use a hash map to store the frequencies of cumulative prefix sums encountered so far. For a current sum `curr_sum`, check if `curr_sum - k` exists in the map.

• Happy Number

  Determine if a number `n` is a 'happy number'. A happy number is defined by the process: starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat. If the process ends in 1, the number is happy. If it loops endlessly in a cycle without reaching 1, it's not. Use a hash set to detect cycles.

• Find All Duplicates in an Array

  Given an array of integers `nums` where `1 ≤ nums[i] ≤ n` (n = array size), and each integer appears once or twice, return an array of all integers that appear twice. Can be solved in O(n) time and O(n) space using a hash set, or O(n) time and O(1) space by modifying the input array (e.g., negating visited indices).

• Check If Two Strings Are Anagrams

  Given two strings `s1` and `s2`, determine if they are anagrams of each other. Return `true` if they are, `false` otherwise. This is identical to the 'Valid Anagram' problem and can be solved using character counts in a hash map or array.