/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function(flowerbed, n) {
for (let i = 0; i<flowerbed.length; i++) {
if (flowerbed[i] == 0
&& (i == 0 || flowerbed[i-1] == 0)
&& (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
n--
flowerbed[i] = 1
if (n < 1)
return true
}
}
return n <= 0
};
Tag Archives: leetcode
LeetCode 1268. Search Suggestions System
/**
* @param {string[]} products
* @param {string} searchWord
* @return {string[][]}
*/
var suggestedProducts = function(products, searchWord) {
products.sort((a, b) => {
if (a > b) return 1
if (a < b) return -1
return 0
})
const r = []
for (let i = 1; i<=searchWord.length; i++) {
const arr = products.filter((s) => s.startsWith(searchWord.substring(0, i))).slice(0, 3)
//console.log(searchWord.substring(0, i))
r.push(arr)
}
return r
};
LeetCode 253. Meeting Rooms II
Lack of built-in Priority Queues in JavaScript makes it a bit hard to do problems like this. I end looking at the solution:
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
if (intervals.length < 1) return 0
const startTimes = []
const endTimes = []
for (let i = 0; i<intervals.length; i++) {
startTimes[i] = intervals[i][0]
endTimes[i] = intervals[i][1]
}
startTimes.sort((a, b) => a-b)
endTimes.sort((a, b) => a-b)
let startPtr = 0
let endPtr = 0
let rooms = 0
for (let i=0; i<intervals.length; i++) {
if (startTimes[i] >= endTimes[endPtr]) {
endPtr++
} else {
rooms++
}
}
return rooms
};
LeetCode 937. Reorder Data in Log Files
/**
* @param {string[]} logs
* @return {string[]}
*/
var reorderLogFiles = function(logs) {
const sorted = []
const numLogs = []
const charLogs = []
for (let i = 0; i<logs.length; i++) {
const log = logs[i]
const tokenized = log.split(" ")
if (Number.isInteger(parseInt(tokenized[1]))) {
numLogs.push(log)
} else {
charLogs.push(log)
}
}
charLogs.sort(function (a, b) {
const stra = a.substr(a.indexOf(' ') + 1)
const strb = b.substr(b.indexOf(' ') + 1)
if (stra > strb) {
return 1
}
if (stra < strb) {
return -1
}
const ida = a.substr(0, a.indexOf(' '))
const idb = b.substr(0, b.indexOf(' '))
//console.log({ida})
if (ida > idb) {
return 1
}
if (ida < idb) {
return -1
}
return 0
})
return [...charLogs, ...numLogs]
};
LeetCode 49. Group Anagrams
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
const map = []
for (let i = 0; i<strs.length; i++) {
const str = strs[i].split('').sort().join('')
if (!map[str]) map[str] = []
map[str].push(strs[i])
}
const ans = []
for (let k in map) {
ans.push(map[k])
}
return ans
};
LeetCode 71. Simplify Path
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
const simple = [];
const splitPath = path.split("/").filter(x => x.length>0 && x !== '.')
for (let i = 0; i<splitPath.length; i++) {
if (splitPath[i] === '..') {
simple.pop()
} else {
simple.push(splitPath[i])
}
}
return `/${simple.join('/')}`
};
LeetCode 50. Pow(x, n)
I got stuck on this problem, even after looking at answers, I could not follow algorithm. Following video really helped me understand it:
Here is my solution after watching this video:
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
if (x == 0) return 0
if (n == 0) return 1
if (n < 0) {
x = 1/x
n = -1 * n
}
const half = myPow(x, Math.floor(n/2))
let ans = half * half
if (n%2 == 1) ans = x * ans
return ans
};
LeetCode 1570. Dot Product of Two Sparse Vectors
My solution in JavaScript:
/**
* @param {number[]} nums
* @return {SparseVector}
*/
var SparseVector = function(nums) {
const x = new Map()
for (let i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
x.set(i, nums[i])
}
}
this.map = x
this.length = nums.length
return this
};
// Return the dotProduct of two sparse vectors
/**
* @param {SparseVector} vec
* @return {number}
*/
SparseVector.prototype.dotProduct = function(vec) {
let ans = 0;
for (let i = 0; i < vec.length; i++) {
if (vec.map.has(i) && this.map.has(i)) {
ans += vec.map.get(i) * this.map.get(i)
}
}
return ans
};
// Your SparseVector object will be instantiated and called as such:
// let v1 = new SparseVector(nums1);
// let v2 = new SparseVector(nums2);
// let ans = v1.dotProduct(v2);
Leetcode 92: Reverse Linked List II
Here is my leetcode solution in JavaScript:
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
let currPos = 1;
let currNode = head;
let startNode = head;
let endNode = null;
while(currPos < left) {
startNode = currNode;
currNode = currNode.next;
currPos++;
}
let newList = null;
let tail = currNode;
while (currPos <= right) {
const next = currNode.next;
currNode.next = newList;
newList = currNode;
currNode = next;
currPos++;
}
startNode.next = newList;
tail.next = currNode;
if (left > 1) {
return head;
}
return newList;
};
LeetCode 92. Reverse Linked List II
I copied solution for Reverse Linked List II from this Udemy course. It was a little hard to understand all these pointers in second loop, I had to use pen and paper to draw each step to finally understand how each pointer works.
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
let currPos = 1;
let currNode = head;
let startNode = head;
let endNode = null;
while(currPos < left) {
startNode = currNode;
currNode = currNode.next;
currPos++;
}
let newList = null;
let tail = currNode;
while (currPos <= right) {
const next = currNode.next;
currNode.next = newList;
newList = currNode;
currNode = next;
currPos++;
}
startNode.next = newList;
tail.next = currNode;
if (left > 1) {
return head;
}
return newList;
};
LeetCode 206. Reverse Linked List
Here is a quick solution to Reverse Linked List problem.
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let curr = head;
let prev = null;
while (curr) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};
LeetCode 560. Subarray Sum Equals K
Brute Force Solution to Subarray Sum Equals K problem from LeetCode:
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let ans = 0;
for (let i=0; i<nums.length; i++) {
let currSum = nums[i];
if (currSum === k) ans++;
for (let j=i+1; j<nums.length; j++) {
currSum += nums[j];
if (currSum === k) ans++;
}
}
return ans;
};
Optimized solution after cheating a bit:
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let ans = 0;
const m = new Map();
let sum=0;
m.set(sum, 1);
for (let i=0; i<nums.length; i++) {
sum += nums[i];
if (m.has(sum-k)) {
ans += m.get(sum-k);
}
if (!m.has(sum)) {
m.set(sum, 1);
} else {
m.set(sum, m.get(sum) + 1);
}
}
return ans;
};
Runtime: 96 ms, faster than 94.76% of JavaScript online submissions for Subarray Sum Equals K.
Memory Usage: 46.6 MB, less than 81.14% of JavaScript online submissions for Subarray Sum Equals K.