Set and Maps Flashcards
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
let sortedArr = nums.sort((a, b) => a - b);
for (let i = 1; i < sortedArr.length; i++) {
if (sortedArr[i] === sortedArr[i - 1]) {
return true;
}
}
return false; };
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]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const hashTable = {};
for (let i = 0; i < nums.length; i++) {
hashTable[nums[i]] = i;
}
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (hashTable[complement] && hashTable[complement] !== i) {
return [i, hashTable[complement]];
}
}
};
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
const hash_1 = {};
const hash_2 = {};
const set = new Set();
for (let i = 0; i < nums1.length; i++) {
if (hash_1[nums1[i]] !== 1) {
hash_1[nums1[i]] = 1;
}
}
for (let i = 0; i < nums2.length; i++) {
if (hash_2[nums2[i]] !== 1) {
hash_2[nums2[i]] = 1;
}
}
for (let i = 0; i < nums2.length; i++) {
if (hash_1[nums2[i]] === 1) {
set.add(nums2[i]);
}
}
return Array.from(set); };
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: [[””]]
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
if (strs.length === 0) {
return [];
}
const map = {};
for (let i = 0; i < strs.length; i++) {
const str = strs[i].split('').sort().join('');
if (!map[str]) {
map[str] = [strs[i]];
} else {
map[str].push(strs[i]);
}
}
const res = [];
Object.keys(map).forEach(key => res.push(map[key]));
return res
};
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = “abba”, str = “dog cat cat dog”
Output: true
Example 2:
Input:pattern = “abba”, str = “dog cat cat fish”
Output: false
Example 3:
Input: pattern = “aaaa”, str = “dog cat cat dog”
Output: false
Example 4:
Input: pattern = “abba”, str = “dog dog dog dog”
Output: false
/**
* @param {string} pattern
* @param {string} str
* @return {boolean}
*/
var wordPattern = function(pattern, str) {
const words = str.split(' ');
if (words.length !== pattern.length) {
return false;
}
const map_p = {};
const map_word = {};
for (let i = 0; i < words.length; i++) {
const char = pattern[i];
const word = words[i];
if (!map_p[char]) {
if (map_word[word]) {
return false;
} else {
map_p[char] = word;
map_word[word] = char;
}
} else {
const mapped_word = map_p[char];
if (mapped_word !== word) {
return false;
}
}
}
return true; };
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
var target = 0;
if (nums.length === 3) {
if (nums[0]+nums[1]+nums[2] === 0) {
return [[nums[0],nums[1],nums[2]]];
}
}
var results = [];
var map = {};
for (var i=0; i a -b);
if (!map[possibleValue]) {
results.push(possibleValue);
map[possibleValue] = 1;
}
}
}
}
}
return results;
};
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function(nums, k) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j] && j - i <= k) {
return true;
}
}
}
return false;
};Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Constraints:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j <= nums.length; j++) {
let sum = 0;
for (let a = i; a < j; a++) {
sum += nums[a];
}
if (sum === k) {
count++;
}
}
}
return count; };
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let count = 0;
const sum = [];
sum[0] = 0;
for (let i = 1; i <= nums.length; i++)
sum[i] = sum[i - 1] + nums[i - 1];
for (let start = 0; start < nums.length; start++) {
for (let end = start + 1; end <= nums.length; end++) {
if (sum[end] - sum[start] == k)
count++;
}
}
return count; };
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
/**
* @param {number[]} A
* @param {number[]} B
* @param {number[]} C
* @param {number[]} D
* @return {number}
*/
var fourSumCount = function(A, B, C, D) {
let counter = 0;
const N = A.length;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
for (let k = 0; k < N; k++) {
for (let l = 0; l < N; l++) {
if (A[i] + B[j] + C[k] + D[l] === 0) {
counter++;
}
}
}
}
}
return counter; };
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
if (k === nums.length){
return nums;
}
const count = {};
for (const n of nums) {
if (count[n]) {
count[n] += 1;
} else {
count[n] = 1;
}
}
const ans = Object.keys(count).sort((key1, key2) => count[key2] - count[key1]);
return ans.slice(0, k);
};
