LeetCode is the best platform for coding interview questions practice. Here are the top questions and their solutions using JavaScript.
1. Two Sum
Given an int array nums and a target int, return the indices of the two numbers that sum up to the target.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9, so the indices are [0, 1].
const sumTwo = (nums, target) => {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}
const nums = [2, 7, 11, 15];
const target = 9;
console.log(sumTwo(nums, target));Solution
Create a hashmap to store numbers and their indices. Loop through the array and check if the complement (target – number) is in the hashmap. If found, return the indices.
Time Complexity = O(n) | Space Complexity = O(1)
Notes
The map can be defined as an object, i.e., cost map = {}, as all objects are hashmaps in JS. The key difference is that objects only support string and symbol keys, whereas maps support more or less any key type. Additionally, Map() provided get(), set(), has(), and delete() methods.
2. Contains Duplicate
Given an int array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Input: nums = [1,2,3,1]
Output: true
const containsDuplicate = nums => {
const dups = new Set(nums);
return nums.length !== dups.size;
}
const nums = [1,2,3,1];
console.log(containsDuplicate(nums));Solution
Use a Set() to store unique numbers. There are duplicates if the array’s length and the set’s size aren’t the same.
Time Complexity = O(n) | Space Complexity = O(n)
3. First Recurring Element
Given an int array nums, return the first recurring element (value) or undefined if not found.
Input: nums = [2,5,1,2,3,5,1,2,4];
Output: 2
const firstRecurringElement = (nums) => {
map= {};
for(i in nums){
if(map[nums[i]]) {
return nums[i];
} else {
map[nums[i]] = nums[i];
}
}
return undefined;
};
const testData = [2,5,1,2,3,5,1,2,4];
console.log(firstRecurringElement(testData));Solution
Create a hashmap to hold unique keys (nums), then iterate through the input array and check if the key already exists. If so, return its value. Otherwise, add it to the hashmap. Return undefined if there’s no solution.
Time Complexity = O(n) | Space Complexity = O(n)
4. Move Zeroes
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
var moveZeroes = function(nums) {
let len = nums.length;
for(let i=0; i < len; i++) {
if(nums[i]===0){
nums.splice(i, 1);
nums.push(0);
i--;
len--;
}
}
};Solution
Iterate over the array, removing an item when it’s == 0 and appending another item to the end of the array. Then, decrement the loop index and length accordingly.
Time complexity = O(n) | Space complexity = O(1)
5. First Unique Character in a String
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Input: s = “leetcode”
Output: 0
Explanation: the character 'l' at index 0 is the first character that does not occur at any other index.
const firstUniqChar = function(s) {
for (i in s.split('')) {
if(s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
return s.indexOf(s[i]);
}
}
return -1;
};
const testData = 'loveleetcode';
console.log(firstUniqChar(testData));Solution
Check if the first indexOf(char) equals the lastIndexOf(char), return the index if true, return -1 otherwise.
Time complexity = O(n) | Space complexity = O(1)
6. Best Time to Buy and Sell Stock
Given an array of prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day to sell that stock in the future. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6), and profit = 6-1 = 5.
Note that buying on day two and selling on day one is prohibited because you must buy before selling.
const maxProfit = prices => {
let minPrice = prices[0];
let maxProfit = 0;
for (let i = 1; i < prices.length; i++) {
let sellPrice = prices[i];
let profit = sellPrice - minPrice;
maxProfit = Math.max(maxProfit, profit);
if(sellPrice < minPrice) {
minPrice = sellPrice;
}
}
return maxProfit;
}
const prices = [7,1,5,3,6,4];
console.log(maxProfit(prices));Solution
Maintain two variables – minimum price and maximum profit. Update the minimum price if a lower price is found and calculate the profit for selling at the current price.
Time complexity = O(n) | Space complexity = O(1)
7. Valid Anagram
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.
Input: s = “anagram”, t = “nagaram”
Output: true
const validAnagram = (s, t) => {
if (s.length !== t.length) return false;
const counts = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
counts[s.charCodeAt(i) - 97]++;
counts[t.charCodeAt(i) - 97]--;
}
return counts.every(count => count === 0);
}
const s = "anagram", t = "nagaram";
console.log(validAnagram(s, t));Solution
Create a new array of size 26 using the Array() and fill each element in the array with value 0. Iterate over the string s and keep track of the frequency of each character in the string in the array. Then, iterate through the second string t and decrement the frequency of each character in the array. Check if every value in the array is 0, return true; Otherwise, return false.
Time complexity = O(n) | Space complexity = O(n)
8. Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. An input string is valid if: (1) Open brackets must be closed by the same type of brackets. (2) Open brackets must be closed in the correct order. (3) Every close bracket has a corresponding open bracket of the same type.
Input: s = “()[]{}”
Output: true
const validParenthasis = (s) => {
const stack = [];
const map = { '(': ')', '[': ']', '{': '}' };
for (let i = 0; i < s.length; i++) {
if (map[s[i]]) {
stack.push(map[s[i]]);
} else if (s[i] !== stack.pop()) {
return false;
}
}
return stack.length === 0;
}
const s = '()[]{}';
console.log(validParenthasis(s));Solution
Use a stack to keep track of opening brackets and hashmap for matching pairs of brackets. For every closing bracket encountered, check the top of the stack.
Time complexity = O(n) | Space complexity = O(n)
9. Maximum Subarray
Given an int array nums, find the subarray with the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
const maxSubarray = (nums) => {
let currSum = -Infinity;
let maxSum = -Infinity;
for(let i = 0; i < nums.length; i++) {
currSum = Math.max(0, currSum);
currSum += nums[i];
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubarray(nums));Solution
Use Kadane’s algorithm to maintain variables for maximum sum and current sum. Update the current sum and maximum sum as you iterate through the array.
Time complexity = O(n) | Space complexity = O(1)
Notes
The Infinity is a global property in JavaScript that is a numeric value representing infinity.
10. Product of Array Except for Self
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[I].
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
const productExceptSelf = (nums) => {
// Value to increment per each index
let carry = 1;
// Array to return all the product values
const output = Array(nums.length).fill(1);
// Add products to output array starting at the front
for(let i = 0; i < nums.length;i++){
output[i]*=carry;
carry*=nums[i];
}
// Reset carry
carry = 1
// Add products to output array starting at the back
for(let i = nums.length-1; i >= 0; i--){
output[i]*=carry;
carry*=nums[i];
}
return output;
};
const nums = [1,2,3,4];
console.log(productExceptSelf(nums));Solution
Initialize an array to store the result. Perform a forward pass: calculate the product of all elements to the left of each index, then perform a backward pass: calculate the product of all elements to the right of each index and return the final result array.
Time complexity = O(n) | Space complexity = O(1)
11. 3Sum Problem
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 that give a sum of zero.
const threeSum = (nums, target) => {
let result = [];
nums.sort((a, b) => a - b);
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 === target) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
};Solution
Sort the array and use two pointers to find pairs that sum up to the target. Skip duplicates to avoid duplicate triplets.
12. Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
const merge = (intervals) => {
if (intervals.length < 2) return intervals;
intervals.sort((a, b) => a[0] - b[0]);
const result = [];
let previous = intervals[0];
for (let i = 1; i < intervals.length; i += 1) {
if (previous[1] >= intervals[i][0]) {
previous = [previous[0], Math.max(previous[1], intervals[i][1])];
} else {
result.push(previous);
previous = intervals[i];
}
}
result.push(previous);
return result;
};
const intervals = [[1,3],[2,6],[8,10],[15,18]]
console.log(merge(intervals));Solution
Sort the intervals based on their start times. Merge overlapping intervals while iterating through the sorted list.
Time complexity = O(nlogn) | Space complexity = O(n)
13. Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
var rotate = function(nums, k) {
const rotations = k % nums.length;
if (rotations > 0) {
const removedElements = nums.splice(nums.length - rotations);
nums.unshift(...removedElements);
}
};Solution
Define the number of required rotations by taking the modulo (%) of k with the array’s length. This ensures that rotations are within the array’s length range, even if k is greater than the array’s length. Then, the splice() method removes the last rotation elements from the array. Then, add the removed elements at the beginning of the array nums using the unshift() method.
14. Group Anagrams
Given an array of strings, group anagrams together.
Solution
Use a hashmap to store sorted strings as keys and their anagrams as values. Iterate through the array, sort each string, and add it to the hashmap.