Arrays & Hashing Flashcards
- Contains Duplicate (Easy)
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
sort, then for loop comparing [i] to [i + 1]
Brute force would be a nested for loop that checks to see if arr[i] and arr[j] are the same and that you’re not comparing the same index (i !==j).
But this has a quadratic time complexity of O(n^2), and the much more efficient way is to sort the array, then check to see if the current number is the same as the next number.
- Valid Anagram (Easy)
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
convert to array, sort, back to string and compare
string.split(‘’).sort().join()
Sort the string by splitting it into an array, sorting it, then rejoining it. Then check to see if the two sorted strings are equal.
(Can also sort with string.sort((a, b) => a - b))
- Two Sum (Easy)
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.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
for loop with nested while loop that compares all values higher than i
this way we’re not comparing values we’ve already checked
Brute force is to create a nested for loop through each item in the array until we find two nums that add up to target.
Better way is to loop through the array with i, and starting with i + j, check to see if j equals target - i
- Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Input: strs = [””]
Output: [[””]]
create map to store results
Maps have built-in methods for manipulating and iterating over the data they store, making them more convenient to use in certain situations.
**for each
return Array.from(map.values())
For this, we can use a map so we can quickly retrieve the value associated with a particular key. While you can certainly store key-value pairs in an object, the methods for accessing and manipulating those pairs are not as optimized as they are for Map. A plain JavaScript object is optimized for general use cases and is not specifically designed for key-value pairs.
Maps have built-in methods for manipulating and iterating over the data they store, making them more convenient to use in certain situations.
Basically, sort the string, then check to see if the sorted string exists as a key in the map with anagramMap.has(sortedStr). If it does, push it to that array with .get(sortedStr).push(str)
If it doesn’t use ‘set’ to create the key-value pair with anagramMap.set(sortedStr, [str]).
- 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.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Iterate and build hash
freqs[num] = (freqs[num] || 0) + 1;
sort the keys by frequency and then slice that array to the k element
Object.keys(freqs).sort((a, b) => freq[b] - freq[a]).slice(0, k)
Build a hash table of the element frequencies by looping through nums, and either initializing the value or incrementing by 1 if it already exists.
then sort the keys of the hash map and slice that array.
Note: When we refer to a “hash table” in JavaScript, we typically mean using a plain JavaScript object to store key-value pairs. This is because JavaScript objects are implemented as hash tables in most modern JavaScript engines.
- Longest Consecutive Sequence (Medium)
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Convert to set for fast lookup
iterate and check if number has left neighbor, if so ignore, if not it’s the start of a sequence and check to see how far it goes
The solution revolves around checking if number has a “left neighbor,” aka is the start of a sequence
- Create highestCounter variable to track
- Convert array into a set to make it easier to check if numbers have a left neighbor (faster lookup times because sets are designed for fast membership tests whereas arrays are meant to provide fast access by index)
- In a for loop iterating through the array, check if it has left neighbor ( if (!numsSet.has(nums[i] - 1)). If not, move on because it’s not a full sequence.
- if it does, use a while loop to see how far the sequence goes and add one to a counter while (numsSet.has(nums[i] + counter)). If counter is higher than highestCounter, replace it.
- Jump Game (Medium)
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Greedy solution: work backwards from the end
Check index + max jump length from that number and see if it’s greater than the lastGoodIndex, if so update lastGoodIndex to i
** return lastGoodIndex === 0**
First instinct was to use recursive, but using a greedy approach and working backwards from the end is much more efficient.
The greedy function starts from the last element and works backwards. It checks if the current index i plus the maximum jump length from that index nums[i] is greater than or equal to the last known good index. If it is, then it updates the last good index to the current index i.
Finally, it checks if the last good index is 0 (meaning that the first index is reachable from some point in the array), and if so, it returns true. If it doesn’t reach the first index, it returns false.
- Find Minimum in Rotated Sorted Array (Medium)
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Modified binary search: calculate mid but then figure out if you’re in left or right portion
If you’re in the left, move to the right since right protion is lower
If you’re in the right, keep searching as normal
This is a variation on binary search, but what you do after finding the mid is a little bit trickier.
When you calculate the mid, figure out if you’re in the left or right portion of the array. If you’re in the left, move to the right since the right portion is always lower. If both high and low are in the right, keep searching as normal.
- Search in Rotated Sorted Array (Medium)
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Modified binary search: calculate mid but then figure out if you’re in left or right portion
4 possible outcomes: mid is in left or right, and target is in left or right
check for mid first, then check to see if target is in the same range
This is a variation on binary search, but what you do after finding the mid is a little bit trickier since there are 4 cases to account for rather than 2 (target is higher or lower than mid).
