bugudiramu

Posted on

# JavaScript Arrays & HashMaps: Mastering the Most Asked LeetCode Problems in Coding Interviews

## A Brief Introduction

Embark on a journey through common array and hashmap problems on LeetCode with this guide. Whether you're a beginner or a seasoned developer, it focuses on essential problem-solving and algorithmic skills.

Explore challenges like checking for duplicates, validating anagrams, finding sums, and identifying frequent elements. Each problem comes with straightforward solutions and explanations, using techniques like sets, maps, sorting, and iterations.

Clear code snippets and simple algorithm breakdowns ensure understanding. Time and space complexities provided offer insights into solution efficiency. Whether you're starting out or refining your skills, this guide equips you with a versatile toolkit for LeetCode's challenges. Happy coding! ππ©βπ»

## 217. Contains Duplicate

``````function containsDuplicate(nums) {
if (!nums.length) return false;
const uniqueNums = new Set();

for (const num of nums) {
if (uniqueNums.has(num)) {
return true;
}
}
return false;
}

const result = containsDuplicate([1, 2, 3, 1]);
console.log(result); // true
``````
• Time complexity: O(n)
• Space complexity: O(n)

## Algorithm:

1. Check if the array 'nums' is empty. If it is, return false since an empty array cannot have duplicates.
2. Create a Set called 'uniqueNums' to store unique elements encountered while iterating through the array.
3. Iterate through each element 'num' in the array 'nums' using a for...of loop. a. Check if 'uniqueNums' already has the current element 'num'.
• If true, it means the array contains a duplicate, so return true.
• If false, add the current element 'num' to 'uniqueNums'.
4. If the loop completes without returning true, it indicates that no duplicates were found, so return false.

## 242. Valid Anagram

``````function isAnagram(str1, str2) {
if (str1.length !== str2.length) {
return false;
}

const charCountMap = new Map();

for (const char of str1) {
charCountMap.set(char, (charCountMap.get(char) || 0) + 1);
}

for (const char of str2) {
if (charCountMap.get(char)) {
charCountMap.delete(char);
}
}

return charCountMap.size === 0;
}

const result = isAnagram("ramu", "umar");
console.log(result); // true
``````
• Time complexity: O(n)
• Space complexity: O(n)

## Algorithm:

1. Check if the lengths of str1 and str2 are not equal. If they are not equal, return false since they cannot be anagrams.

2. Create a Map called charCountMap to store the count of each character in str1.

3. Iterate over each character (char) in str1:
a. If char is already in charCountMap, increment its count.
b. If char is not in charCountMap, set its count to 1.

4. Iterate over each character (char) in str2:
a. Check if char is in charCountMap and its count is greater than 0.
b. If true, decrement the count of char in charCountMap.
c. If false, return false since char is not present in str1 or its count is exhausted.

5. After both iterations, check if charCountMap is empty (size is 0).
a. If true, return true, indicating that str1 and str2 are anagrams.
b. If false, return false.

## 1. Two Sum

``````function twoSum(nums, target) {
const indexMap = new Map();

for (let i = 0; i < nums.length; i++) {
const currentNumber = nums[i];
const complement = target - currentNumber;

if (indexMap.has(complement)) {
return [indexMap.get(complement), i];
}

indexMap.set(currentNumber, i);
}

return [];
}

const result = twoSum([3, 2, 4], 6);
console.log(result);
``````
• Time complexity: O(n)
• Space complexity: O(n)

## Algorithm Steps:

1. Create an empty Map called indexMap to store numbers and their corresponding indices.
2. Iterate through the nums array using a for loop with index variable i.
3. Inside the loop:
• Get the currentNumber at index i.
• Calculate the complement as target minus currentNumber.
• Check if the complement exists in the indexMap.
• If yes, return an array containing the indices of complement and currentNumber.
• If not, store the currentNumber and its index in the indexMap.
1. If the loop completes without finding a pair, return an empty array.

## 49. Group Anagrams

``````function groupAnagrams(strs) {
const anagramMap = new Map();

for (const str of strs) {
const sortedStr = str.split("").sort().join("");

if (anagramMap.has(sortedStr)) {
anagramMap.get(sortedStr).push(str);
} else {
anagramMap.set(sortedStr, [str]);
}
}

return [...anagramMap.values()];
}

const result = groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);
console.log(result);
``````
• Time complexity: O(n log n)
• Space complexity: O(n)

## Algorithm:

1. Initialize an empty Map called anagramMap to store anagrams.
2. Iterate through each string (str) in the input array (strs). a. Convert the string into an array of characters, sort the array, and then join the characters back into a string. b. Check if the sorted string exists as a key in anagramMap.
• If yes, push the original string (str) to the corresponding array value.
• If no, create a new entry in the map with the sorted string as the key and an array containing the original string as the value.
3. After processing all strings, return an array containing all the values from anagramMap.
• Each value in the array represents a group of anagrams.

## 347. Top K Frequent Elements

``````function topKFrequent(nums, k) {
const frequencyMap = new Map();

for (const num of nums) {
frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
}

const result = [];
for (const [num, frequency] of frequencyMap) {
if (frequency >= k) {
result.push(num);
}
}

return result;
}

const result = topKFrequent([1, 1, 1, 2, 2, 3], 2);
console.log(result);
``````
• Time complexity: O(n)
• Space complexity: O(n)

## Algorithm:

1. Create a frequency map using a Map to count the occurrences of each unique number in the input array 'nums'.
2. Iterate through each element 'num' in the 'nums' array. a. If 'num' is already a key in the frequency map, increment its value by 1. b. If 'num' is not a key, set its value to 1.
3. Initialize an empty array 'result' to store the numbers with a frequency greater than or equal to 'k'.
4. Iterate through each entry [num, frequency] in the frequency map. a. If the frequency is greater than or equal to 'k', push 'num' to the 'result' array.
5. Return the 'result' array containing numbers with frequencies greater than or equal to 'k'.

## 238. Product of Array Except Self

``````function productExceptSelf(nums) {
const n = nums.length;

const result = new Array(n).fill(1);

let leftProduct = 1;
for (let i = 0; i < n; i++) {
result[i] *= Math.abs(leftProduct);
leftProduct *= nums[i];
}

let rightProduct = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= Math.abs(rightProduct);
rightProduct *= nums[i];
}

return result;
}

const result = productExceptSelf([1, -1]);
console.log(result);
``````
• Time complexity: O(n)
• Space complexity: O(n)

## Algorithm:

1. Initialize an array 'result' of length 'n' with all elements set to 1.
2. Initialize a variable 'leftProduct' to 1 to keep track of the product of elements to the left.
3. Iterate through the array from left to right: a. Update result[i] by multiplying it with the absolute value of 'leftProduct'. b. Update 'leftProduct' by multiplying it with the current element 'nums[i]'.
4. Initialize a variable 'rightProduct' to 1 to keep track of the product of elements to the right.
5. Iterate through the array from right to left: a. Update result[i] by multiplying it with the absolute value of 'rightProduct'. b. Update 'rightProduct' by multiplying it with the current element 'nums[i]'.
6. The 'result' array now contains the product of all elements except self for each index.
7. Return the 'result' array.

## 128. Longest Consecutive Sequence

### If the given input array is sorted:

``````function longestConsecutive(nums) {
if (nums.length === 0) {
return 0;
}

let max = 1;
let currMax = 1;

for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1] + 1) {
currMax++;
} else if (nums[i] !== nums[i - 1]) {
currMax = 1;
}

max = Math.max(max, currMax);
}

return max;
}

const result = longestConsecutive([1, 2, 3, 4, 100, 200]);
console.log(result);
``````
• Time complexity: O(n)
• Space complexity: O(1)

## Algorithm:

1. If the input array is empty, return 0 as there are no consecutive elements.
2. Initialize two variables, max and currMax, to keep track of the overall maximum and the current maximum consecutive sequence length.
3. Iterate through the array starting from index 1. a. Check if the current element is one more than the previous element. If true, increment currMax. b. If the current element is not equal to the previous element (handling duplicates), reset currMax to 1. c. Update the overall maximum (max) by taking the maximum of max and currMax.
4. Return the final maximum consecutive sequence length (max).

### If the given input array is not sorted:

``````function longestConsecutive(nums) {
const set = new Set(nums);
let max = 0;

for (const num of nums) {
if (set.has(num - 1)) continue;

let currNum = num;
let currMax = 1;

while (set.has(currNum + 1)) {
currMax++;
currNum++;
}
max = Math.max(currMax, max);
}
return max;
}

const result = longestConsecutive([100, 4, 200, 1, 3, 2]);
console.log(result);
``````
• Time complexity: O(n)
• Space complexity: O(n)

## Algorithm:

1. Create a Set 'set' from the given array 'nums' to allow constant-time lookup.
2. Initialize a variable 'max' to 0 to keep track of the maximum length of consecutive sequence.
3. Iterate through each 'num' in the 'nums' array using a for...of loop. a. Check if 'num - 1' exists in the set. If yes, continue to the next iteration. b. If 'num - 1' does not exist, it means 'num' is the start of a potential consecutive sequence. c. Initialize variables 'currNum' to 'num' and 'currMax' to 1 to track the current sequence length. d. Use a while loop to iterate as long as 'currNum + 1' exists in the set.
• Increment 'currMax' and 'currNum' in each iteration to extend the consecutive sequence. e. Update 'max' by taking the maximum of 'currMax' and the previous 'max'.
4. Return the final 'max' representing the length of the longest consecutive sequence.

Thank you for reading this far; your support means a lot! If you have any questions, please don't hesitate to ask in the comments. Don't forget to like and share the article β your appreciation is highly valued. Your feedback and suggestions are also more than welcome. πππ