Leetcode Solution Revision Flashcards
For reviewing solutions to specific questions that i have already completed
What is this code doing, and what is its time/space complexity?
function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++){
let diff = target - nums[i]
if(map.has(diff)){
return [i, map.get(diff)]
}
map.set(nums[i],i)
}
};
It is the solution to the Two Sum problem, it searches through a list of numbers and looks for the index of 2 numbers that add up the target number.
It has a time complexity of O(n) because it is iterating through the list once. It is O(n) space complexity because it creates a map that is up to the size of the input array.
[Two Sum]
Fill in the blanks for this solution
function(nums, target) {
let map = ?????
for(let i = 0; i < nums.length; i++){
let diff = ????
if(map.has(diff)){
return [i, map.get(diff)]
}
????
}
};
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]
function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++){
let diff = target - nums[i]
if(map.has(diff)){
return [i, map.get(diff)]
}
map.set(nums[i],i)
}
};
[Two Sum]
Fill in the blanks for this solution
function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++){
????
if(map.has(diff)){
??????
}
map.set(nums[i],i)
}
};
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]
function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++){
let diff = target - nums[i]
if(map.has(diff)){
return [i, map.get(diff)]
}
map.set(nums[i],i)
}
};
[Two Sum]
Fill in the blanks for this solution
function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++){
let diff = target - nums[i]
if(??????){
return [i, map.get(diff)]
}
map.set(????,????)
}
};
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]
function(nums, target) {
let map = new Map()
for(let i = 0; i < nums.length; i++){
let diff = target - nums[i]
if(map.has(diff)){
return [i, map.get(diff)]
}
map.set(nums[i],i)
}
};
[Two Sum]
Explain in english how to solve this problem
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
- Create an empty stack to store the closing brackets
- iterate through the list
- if the item is an open bracket, add its corresponding closing bracket to the list
- Otherwise, if its a closing bracket check if the last item in the stack is different. If it is, then its invalid
- At the end of the loop, if the stack has nothing left in it, then the parenthesis are valid
[Valid Parenthesis]
What is the time and space complexity of this code?
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};
It is creating a stack in memory which could be up to the size of the array, so its O(n) space complexity and it iterates over the whole array once so its O(n) time complexity
What is this code doing?
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};
It is looking at items in an array of brackets and checking if the brackets have a corresponding match in the correct order. Eg [,(,},] would be correct and [,[,},) would be incorrect
Fill in the blanks
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
????
} else if (s[idx] == '[') {
???
} else if (s[idx] == '(') {
????
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};
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
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};Fill in the blanks
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
????
}
}
return ????
};
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
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};Fill in the blanks
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (?????) {
stack.push('}');
} else if (?????) {
stack.push(']');
} else if (?????) {
stack.push(')');
}
else if (????) {
return false;
}
}
return !stack.length;
};
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
function (s) {
let stack = [];
for (let idx = 0; idx < s.length; idx++) {
if (s[idx] == '{') {
stack.push('}');
} else if (s[idx] == '[') {
stack.push(']');
} else if (s[idx] == '(') {
stack.push(')');
}
else if (stack.pop() !== s[idx]) {
return false;
}
}
return !stack.length;
};Fill in the blanks
const isPalindrome = function(s) {
s = s.toLowerCase()
let i = 0
let j = s.length-1
const IsAlphaNumeric = (character) => {
let code = character.charCodeAt(0)
if (!(code > 47 && code < 58) && // numeric (0-9)
!(code > 64 && code < 91) && // upper alpha (A-Z)
!(code > 96 && code < 123)) { // lower alpha (a-z)
return false;
}
return true
}
while(????){
while(????){
i++;
}
while(????){
j--;
}
if(????){
return false
}
i++;
j--;
}
return true
};
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.
const isPalindrome = function(s) {
s = s.toLowerCase()
let i = 0
let j = s.length-1
const IsAlphaNumeric = (character) => {
let code = character.charCodeAt(0)
if (!(code > 47 && code < 58) && // numeric (0-9)
!(code > 64 && code < 91) && // upper alpha (A-Z)
!(code > 96 && code < 123)) { // lower alpha (a-z)
return false;
}
return true
}
while(i < j){
while(!IsAlphaNumeric(s[i]) && i < j){
i++;
}
while(!IsAlphaNumeric(s[j]) && i < j){
j--;
}
if(s[i] != s[j]){
return false
}
i++;
j--;
}
return true
};Fill in the blanks
const isPalindrome = function(s) {
s = s.toLowerCase()
let i = 0
let j = s.length-1
const IsAlphaNumeric = (character) => {
let code = character.charCodeAt(0)
if (!(code > 47 && code < 58) && // numeric (0-9)
!(code > 64 && code < 91) && // upper alpha (A-Z)
!(code > 96 && code < 123)) { // lower alpha (a-z)
return false;
}
return true
}
while(i < j){
while(!IsAlphaNumeric(s[i]) && i < j){
????
}
while(!IsAlphaNumeric(s[j]) && i < j){
????
}
if(s[i] != s[j]){
????
}
????
????
}
return true
};
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.
const isPalindrome = function(s) {
s = s.toLowerCase()
let i = 0
let j = s.length-1
const IsAlphaNumeric = (character) => {
let code = character.charCodeAt(0)
if (!(code > 47 && code < 58) && // numeric (0-9)
!(code > 64 && code < 91) && // upper alpha (A-Z)
!(code > 96 && code < 123)) { // lower alpha (a-z)
return false;
}
return true
}
while(i < j){
while(!IsAlphaNumeric(s[i]) && i < j){
i++;
}
while(!IsAlphaNumeric(s[j]) && i < j){
j--;
}
if(s[i] != s[j]){
return false
}
i++;
j--;
}
return true
};Explain in english how you would solve this problem
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.
- Start by lowercasing the string
- A pointer at the start of the string and the end of the string
- while the left pointer index continues to be before the right pointer:
- Check left pointer, if its not alphanumeric then increment it by 1
- Check the right pointer, if its not alphanumberic then decrement it by 1
- Then compare the left and right pointers value. If it does not match its not a palindrome
- if it does, increment left by 1 and decrement right by 1.
- if we exit the loop, then its a palindome
What is the space and time complexity of this code
const isPalindrome = function(s) {
s = s.toLowerCase()
let i = 0
let j = s.length-1
const IsAlphaNumeric = (character) => {
let code = character.charCodeAt(0)
if (!(code > 47 && code < 58) && // numeric (0-9)
!(code > 64 && code < 91) && // upper alpha (A-Z)
!(code > 96 && code < 123)) { // lower alpha (a-z)
return false;
}
return true
}
while(i < j){
while(!IsAlphaNumeric(s[i]) && i < j){
i++;
}
while(!IsAlphaNumeric(s[j]) && i < j){
j--;
}
if(s[i] != s[j]){
return false
}
i++;
j--;
}
return true
};
It has a space complexity of O(1), because we are not creating any additional memory. It has a time complexity of O(n) because we will need to check each item of the array once
