DSA | JavaScript | Arrays & Hashing (Map or Set)

Sonika | @Walmart | FrontEnd Developer | 10 Years

5 min readMay 19, 2024

List:

Count Occurrence
Contains Duplicate
Valid Anagram
Two Sum
Group Anagrams
Top K Frequent Elements
Product of Array Except Self
Valid Sudoku
Longest Consecutive Sequence

Solution: https://levelup.gitconnected.com/dsa-javascript-arrays-hashing-map-or-set-72115e45de87

Similar problems::

Longest Common Prefix
Word Pattern
Minimum Number of Swaps to Make the String Balanced
Best Time to Buy and Sell Stock II

Solutions,

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Implementation,

Time Complexity: 𝑂(𝑛⋅𝑚) , where n is the number of strings and 𝑚m is the length of the shortest string.
Space Complexity: 𝑂(𝑚), where m is the length of the shortest string.

Approach,

Iteration through Strings: The function iterates through each string in the array strs.

Substring Operation: Inside the loop, the function performs a substring operation to reduce the prefix.


function longestCommonPrefix(strs) {
    if (strs.length === 0) return "";

    // Start with the first string as the initial prefix
    let prefix = strs[0];

    // Iterate through the rest of the strings
    for (let i = 1; i < strs.length; i++) {
        // Compare the prefix with each string and reduce it as necessary
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === "") return "";
        }
    }

    return prefix;
}

// Example usage
const strs = ["flower", "flow", "flight"];
console.log(longestCommonPrefix(strs)); // Output: "fl"

Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Here’s how we can approach this problem in JavaScript:

Split the string s into an array of words.
Create two maps (patternMap and wordMap) to store the mapping between characters and words.
Iterate through each character in the pattern and its corresponding word in s.

If the character already exists in patternMap, check if its corresponding word matches the word from s. If not, return false.
If the word already exists in wordMap, check if its corresponding character matches the character from the pattern. If not, return false.
Otherwise, establish the bijection by adding the character-word pair to patternMap and wordMap.

4. After the loop, return true if no inconsistencies are found.

Implementation,

Time coplexity O(n)
Space complexity O(n)


var wordPattern = function(pattern, s) {
    
s = s.split(' ');

if(s.length !== pattern.length) return false;

wordToChar = new Map();
charToWord = new Map();

for(let i = 0; i < pattern.length; i++) {
    wordToChar.set(s[i], pattern[i]);
    charToWord.set(pattern[i], s[i]);
};


for(let i = 0; i < pattern.length; i++)  {
    if(charToWord.get(pattern[i]) !== s[i] || pattern[i] !== wordToChar.get(s[i])) {
        return false;
    }
}

return true;
};


OR



function wordPattern(pattern, s) {
    const words = s.split(' ');
    if (pattern.length !== words.length) {
        return false;
    }

    const patternMap = new Map();
    const wordMap = new Map();

    for (let i = 0; i < pattern.length; i++) {
        const char = pattern[i];
        const word = words[i];

        if (patternMap.has(char)) {
            if (patternMap.get(char) !== word) {
                return false;
            }
        } else {
            patternMap.set(char, word);
        }

        if (wordMap.has(word)) {
            if (wordMap.get(word) !== char) {
                return false;
            }
        } else {
            wordMap.set(word, char);
        }
    }

    return true;
}

// Example usage
const pattern = "abba";
const s = "dog cat cat dog";
console.log(wordPattern(pattern, s)); // Output: true

Minimum Number of Swaps to Make the String Balanced

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

It is the empty string, or
It can be written as AB, where both A and B are balanced strings, or
It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Implementation,

Time complexity O(n)
Space complexity O(1)


function minSwapsToBalance(s) {
    let imbalance = 0;

    // Calculate the imbalance
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '[') {
            imbalance++;
        } else {
            imbalance--;
        }
    }

    // The number of swaps needed is half of the absolute imbalance (rounded up)
    return Math.ceil(Math.abs(imbalance) / 2);
}

// Example usage
const s = "]]][[[";
console.log(minSwapsToBalance(s)); // Output: 2


or


var minSwaps = function(s) {

    let extraClosing = 0;
    let maxClosing = 0;
    for(let i = 0; i < s.length; i++) {
        s[i] === ']' ? extraClosing++ : extraClosing--;
        maxClosing = Math.max(maxClosing, extraClosing);
    }

    return Math.ceil(maxClosing/2);
};

Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.


function maxProfit(prices) {
    let totalProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        // Calculate the difference between the current day price and the previous day price
        let profit = prices[i] - prices[i - 1];

        // If the difference is positive, add it to the total profit
        if (profit > 0) {
            totalProfit += profit;
        }
    }

    return totalProfit;
}

// Example usage
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 7