Neetcode - Arrays & Hashing

Valid Anagrams

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

• check if length of input word and length of anagram is same, if length doesn't match return False

• iterate through word and count each character, and compare with count of that character for the anagram

  • if count of characters don't match, return False

• else return True

Two Sum

• use a hashmap to map values: index

• iterate through the array and get the index value pair using enumerate()

• add target - value to hashmap if not in hashmap, if in hashmap then we have encountered a previous number that when added to our current number, sums up to target

• return the index of the previous number which is stored in the hashmap and the current index

  • [previous index, current index]

  • [hashmap[target - currVal], currIndex]

Group Anagrams

• use a hashmap and sorting to group strings that are anagrams of each other by storing sorted versions as keys

• for each string in the input array, sort the string

  • if sorted string is already in hashmap, append current string that is unsorted

  • else, make a key with the sorted string and append current string that is unsorted

• create an output array

  • append all values in the dictionary using for value in dictName.values()

  • return output array

Longest Consecutive Sequence

• need to find the start of sequence, so that we can begin counting how long that sequence is. what makes a start of a sequence? when a number - 1 is not in the input

• global variables:

  • maxLength

  • nums_set

    • convert input array into a set to remove duplicates

    • O(1) lookup time to check next number in sequence

• iterate through numbers in set

  • if found start of sequence (x - 1 not in nums_set)

    • local variable length = 1

    • increment length += 1 if next number in sequence exists

    • max(maxLength, length)

• return maxLength