leetcode roadmap 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
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
Arrays & Hashing
var containsDuplicate = function(nums) {
const numsSet = new Set();
for (let i = 0; i < nums.length; i++) {
if (numsSet.has(nums[i])) {
return true;
}
numsSet.add(nums[i]);
}
return false;
};
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
Constraints:
1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.
Arrays & Hashing
var isAnagram = function(s, t) {
if (s.length !== t.length) {
return false;
}
const map = new Map();
for (let i = 0; i < s.length; i++) {
map.set(s[i], (map.get(s[i]) || 0) + 1);
map.set(t[i], (map.get(t[i]) || 0) - 1);
}
for ([char, count] of map) {
if (count !== 0) {
return false;
}
}
return true;
};
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]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Arrays & Hashing
var twoSum = function(nums, target) {
const hash = {};
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];
if (diff in hash) {
return [i, hash[diff]];
}
hash[nums[i]] = i;
}
return [];
};
Group Anagrams (med)
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: [[””]]
Example 3:
Input: strs = [“a”]
Output: [[“a”]]
Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
Arrays & Hashing
var groupAnagrams = function(strs) {
if (strs.length === 1) {
return [strs];
}
const anagramMap = new Map();
for (let i = 0; i < strs.length; i++) {
const str = strs[i];
const frequency = new Array(26).fill(0);
for (let j = 0; j < str.length; j++) {
const charCode = (str[j].charCodeAt() - 97);
frequency[charCode]++;
}
let key = frequency.join('_');
if (anagramMap.get(key)) {
anagramMap.get(key).push(str);
} else {
anagramMap.set(key, [str]);
}
}
return [...anagramMap.values()];
};
Top K Frequent Elements (med)
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]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
Arrays & Hashing
var topKFrequent = function(nums, k) {
const res = [];
const map = {};
const bucket = [];
nums.forEach(num => {
map[num] = (map[num] || 0) + 1;
});
Object.entries(map).forEach(([num, freq]) => {
if (bucket[freq]) {
bucket[freq].push(num);
} else {
bucket[freq] = [num];
}
});
for (let i = bucket.length - 1; i >= 0; i--) {
if (bucket[i]) {
res.push(...bucket[i]);
if (res.length === k) {
return res;
}
}
}
return res;
};
Product of Array Except Self (med)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Arrays & Hashing
var productExceptSelf = function(nums) {
const res = [];
let prefix = 1;
let postfix = 1;
for (let i = 0; i < nums.length; i++) {
res[i] = prefix;
prefix *= nums[i];
}
for (let i = nums.length - 2; i >= 0; i--) {
postfix *= nums[i + 1];
res[i] *= postfix;
}
return res;
};
Valid Sudoku (med)
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: 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”]]
Output: true
Example 2:
Input: board =
[[“8”,”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”]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or ‘.’.
Arrays & Hashing
const addToSetIfNotPresent = (set, value) => {
if (set.has(value)) {
return false;
} else {
set.add(value);
return true;
}
}
var isValidSudoku = function(board) {
const seen = new Set();
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const number = board[i][j];
if (number !== '.') {
if (
!addToSetIfNotPresent(seen, `${number} in row ${i}`) ||
!addToSetIfNotPresent(seen, `${number} in column ${j}`) ||
!addToSetIfNotPresent(seen, `${number} in block ${Math.floor(i / 3)} - ${Math.floor(j / 3)}`)
) {
return false;
}
}
}
}
return true;
};
Encode and Decode Strings (med)
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement encode and decode
Example(s):
Example1
Input: [“lint”,“code”,“love”,“you”] Output: [“lint”,“code”,“love”,“you”] Explanation: One possible encode method is: “lint:;code:;love:;you”
Example2
Input: [“we”, “say”, “:”, “yes”] Output: [“we”, “say”, “:”, “yes”] Explanation: One possible encode method is: “we:;say:;:::;yes”
Arrays & Hashing
const encode = (arr) => {
let res = '';
arr.forEach(str => {
res += `${str.length}#${str}`;
});
return res;
}
const delimitWord = (str, index) => {
const delimeterIndex = str.indexOf('#', index);
const length = Number(str.slice(index, delimeterIndex));
const start = delimeterIndex + 1;
const end = start + length;
const word = str.slice(start, end);
return [word, end];
}
const decode = (str) => {
const res = [];
let i = 0;
while (i < str.length) {
const [word, nextIndex] = delimitWord(str, i);
res.push(word);
i = nextIndex;
}
return res;
}
Longest Consecutive Sequence (med)
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
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
Arrays & Hashing
var longestConsecutive = function(nums) {
if (nums.length === 0) {
return 0;
}
let res = 1;
const set = new Set(nums);
for (let num of set) {
if (set.has(num + 1) && !set.has(num - 1)) {
let length = 2;
let i = num + 2;
while (set.has(i)) {
length++;
i++;
}
res = Math.max(res, length);
}
}
return res;
};
Valid Palindrome (easy)
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
Example 2:
Input: s = “race a car”
Output: false
Explanation: “raceacar” is not a palindrome.
Example 3:
Input: s = “ “
Output: true
Explanation: s is an empty string “” after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
Constraints:
1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.
Two Pointers
const isAlphaNumeric = (char) => ((char >= '0' && char <= '9') || (char >= 'A' && char <= 'Z') || (char >= 'a' && char <= 'z'));
var isPalindrome = function(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
if (!isAlphaNumeric(s[left])) {
left++;
} else if (!isAlphaNumeric(s[right])) {
right--;
} else {
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
}
return true;
};
Two Sum II - Input Array Is Sorted (med)
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Two Pointers
var twoSum = function(numbers, target) {
if (numbers.length == 2) {
return [1, 2];
}
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
}
if (sum > target) {
right--;
} else {
left++;
}
}
};
3Sum (med)
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
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]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
Two Pointers
var threeSum = function(nums) {
nums.sort((a, b) => a - b);
const res = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
res.push([nums[i], nums[left], nums[right]]);
while (nums[left] === nums[left + 1]) {
left ++;
}
left++;
while (nums[right] === nums[right - 1]) {
right --;
}
right --;
} else if (sum > 0) {
right --;
} else {
left ++;
}
}
}
return res;
};
Container With Most Water (med)
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
Two Pointers
var maxArea = function(height) {
let max = 0;
let left = 0;
let right = height.length - 1;
let maxHeight = 0;
while (left < right) {
const isLeftMin = height[left] < height[right];
const currentHeight = isLeftMin ? height[left] : height[right];
if (currentHeight > maxHeight) {
maxHeight = currentHeight;
max = Math.max(max, currentHeight * (right - left));
}
if (isLeftMin) {
left++;
} else {
right--;
}
}
return max;
};
Trapping Rain Water (hard)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Two Pointers
var trap = function(height) {
if (height.length < 3) {
return 0;
}
let res = 0;
let l = 0;
let r = height.length - 1;
let lMax = 0;
let rMax = 0;
while (l < r) {
if (height[l] < lMax) {
res += lMax - height[l];
} else {
lMax = height[l];
}
if (height[r] < rMax) {
res += rMax - height[r];
} else {
rMax = height[r];
}
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return res;
};
Valid Parentheses (easy)
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.
Stack
const pairs = {
'{': '}',
'(': ')',
'[': ']',
}
var isValid = function(s) {
const opened = [];
for (let i = 0; i < s.length; i++) {
if (pairs[s[i]]) {
opened.push(s[i]);
} else if (s[i] !== pairs[opened.pop()]) {
return false;
}
}
return opened.length === 0;
};
