Blind 75

class ArrayAndHashmap {
    containsDuplicate = function (nums) {
        const map = new Map()
        for (let char of nums) {
            map.set(char, (map.get(char) || 0) + 1)
        }
        for (let [key, value] of map) {
            if (value > 1) return true
        }
        return false;
    };

    isAnagram = function (s, t) {
        if (s.length !== t.length) return false
        let map = new Map()
        for (let char of s) {
            map.set(char, (map.get(char) || 0) + 1);
        } //you have map now compare with t
        for (let char of t) {
            if (!map.has(char)) return false
            map.set(char, map.get(char) - 1);
            if (map.get(char) === 0) map.delete(char)
        }
        return map.size === 0
    };

    twoSum = function (nums, target) { // Find two numbers which are two-sum of target in nums                      
        const map = new Map(); // create a new map
        for (let i = 0; i < nums.length; i++) { // now iterate over nums
            const complement = target - nums[i] // find complement of target to current
            if (map.has(complement)) { // if there's complement in map
                return [map.get(complement), i] // return complement and current index
            }
            map.set(nums[i], i) // map current number to current index otherwise
        }
    };

    groupAnagrams = function (strs) {
        const map = new Map()
        for (let str of strs) {
            const sorted = str.split('').sort().join('')
            if (!map.has(sorted)) map.set(sorted, [])
            map.get(sorted).push(str)
        }
        return Array.from(map.values())
    };

    topKFrequent = function (nums, k) {
        const frequencyMap = new Map()
        const buckets = Array.from({ // bucket sort
            length: nums.length + 1
        }, () => [])
        const result = []
        for (const num of nums) {
            frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1)
        }
        for (const [num, freq] of frequencyMap.entries()) {
            buckets[freq].push(num)
        }
        for (let i = buckets.length - 1; i >= 0; i--) {
            for (const num of buckets[i]) {
                result.push(num)
                if (result.length === k) {
                    return result
                }
            }
        }
        return result
    }

    EncodeDecode = function () { // Encode and decode string
        function encode(strs) {
            let encoded = ''
            for (let str of strs) {
                encoded += str.length + "#" + str
            }
            return encoded;
        }

        function decode(str) {
            let decoded = []
            let i = 0;
            while (i < str.length) { //while i is in bound
                let j = str.indexOf('#', i) //find delimeter
                let length = parseInt(str.slice(i, j)); // find length
                i = j + 1; // start from the beginning of string
                decoded.push(str.slice(i, i + length)) // push into str
                i += length // jump to next string
            }
            return decoded
        }
    }

    productExceptSelf(nums) {
        const n = nums.length;
        const result = Array(n).fill(1)
        let leftProduct = 1;
        for (let i = 0; i < n; i++) {
            result[i] = leftProduct;
            leftProduct *= nums[i]
        }
        let rightProduct = 1
        for (let i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i]
        }
        return result
    }

    longestConsecutive = function (nums) { // longest coonsecutive subsequence
        if (nums.length === 0) return 0
        let longest = 0;
        let numSet = new Set(nums)
        for (let num of nums) {
            if (!numSet.has(num - 1)) {
                let currentStreak = 1;
                let currentNum = num
                while (numSet.has(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                longest = Math.max(longest, currentStreak)
            }
        }
        return longest
    };
}

class Twopointer {
    isPalindrome = function (s) { // Check if a string is a palindrome
        const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
        return cleaned === cleaned.split('').reverse().join('');
    };

    threeSum = function (nums) {
        const result = []; // result
        nums.sort((a, b) => a - b) // sort the array
        for (let i = 0; i < nums.length - 2; i++) { // iterate over nums
            if (i > 0 && nums[i] === nums[i - 1]) continue // skip first duplicate
            let left = i + 1,
                right = nums.length - 1; // two pointer
            while (left < right) { // inner loop
                const currentSum = nums[i] + nums[left] + nums[right] // find sum
                if (currentSum === 0) { // if valid 
                    result.push([nums[i], nums[left], nums[right]]) //push into result
                    while (left < right && nums[left] === nums[left + 1]) left++; //duplicates
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    left++; // carry on
                    right--;
                } else if (currentSum < 0) {
                    left++
                } else right--;
            }
        }
        return result
    };

    maxArea = function (height) { // container with most water
        let left = 0; // two pointers
        let right = height.length - 1;
        let maxWater = 0;
        while (left < right) {
            const area = Math.min(height[left], height[right]) * (right - left) // calculate area enclosed by left and right pillar
            maxWater = Math.max(maxWater, area) // if current area is maximum, update it 
            if (height[left] < height[right]) { // continue with next larger pillar whether it is left or right 
                left++;
            } else {
                right--;
            }
        }
        return maxWater;
    };
}

class SlidingWindow {
    maxProfit = function (prices) { //   Best time to buy and sell stocks
        let maxProfit = 0;
        let minPrice = Infinity;
        for (let price of prices) {
            minPrice = Math.min(minPrice, price);
            const profit = price - minPrice;
            maxProfit = Math.max(maxProfit, profit);
        }
        return maxProfit;
    };

    lengthOfLongestSubstring = function (s) { // without repeating characters
        let left = 0;
        let max_length = 0;
        const map = new Map();
        for (let right = 0; right < s.length; right++) {
            while (map.has(s[right])) {
                map.delete(s[left]);
                left++
            }
            map.set(s[right], right)
            max_length = Math.max(max_length, right - left + 1)
        }
        return max_length;
    };

    characterReplacement = function(s, k) { //Longest repeating character replacement
        let left = 0, freq = {}, maxFrequency = 0, maxLength = 0;
        for (let right = 0; right < s.length; right++){
            const char  = s[right];
            freq[char] = (freq[char] || 0)+1
            maxFrequency = Math.max(maxFrequency, freq[char])
            while ((right-left+1)-maxFrequency > k) {
                freq[s[left]]--
                left++
            }
            maxLength = Math.max(maxLength, right-left+1)
        }
        return maxLength
    };

    // NOTE: It is advised to solve hard question like this in python or even C++
    minWindow(s, t) { // minimum window substring
        if (s.length < t.length) return "";
    
        const requiredChars = new Map();
        for (const char of t) {
            requiredChars.set(char, (requiredChars.get(char) || 0) + 1);
        }
    
        let left = 0;
        let right = 0;
        let formed = 0;
        const windowCounts = new Map();
        const required = requiredChars.size;
    
        let minLength = Infinity;
        let minWindowStart = 0;
    
        while (right < s.length) {
            const char = s[right];
            windowCounts.set(char, (windowCounts.get(char) || 0) + 1);
    
            if (requiredChars.has(char) && windowCounts.get(char) === requiredChars.get(char)) {
                formed += 1;
            }
    
            while (left <= right && formed === required) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    minWindowStart = left;
                }
    
                const leftChar = s[left];
                windowCounts.set(leftChar, windowCounts.get(leftChar) - 1);
    
                if (requiredChars.has(leftChar) && windowCounts.get(leftChar) < requiredChars.get(leftChar)) {
                    formed -= 1;
                }
                left += 1;
            }
            right += 1;
        }
    
        return minLength === Infinity ? "" : s.slice(minWindowStart, minWindowStart + minLength);
    }
}

class Stack {
    isValid = function(s) {
        let stack = []
        const map = {
            '}':'{',
            ')':'(',
            ']':'['
        }
        for (let char of  s){
            if (char === '{' || char ==='('|| char ==='[' ){
                stack.push(char)
            }else{
                if (stack.length===0 ||stack.pop() !== map[char] ) return false;
            }
        }
        return stack.length === 0
    };
}

class BinarySearch{
    findMin = function(nums) { // Find minimum in a rotated sorted array
        let left = 0, right = nums.length-1;
        while (left < right){
            const mid = Math.floor((left+right)/2)
            if (nums[right] < nums[mid]){ // If mid is greater than minimum is on the right
                left = mid +1;
            }else{
                right = mid;
            }
        }
        return nums[left]
    };

    search = function(nums, target) { // search target in a rotated sorted array
        let left = 0, right = nums.length -1;
        while (left <= right ){
            const mid = Math.floor((left + right )/2);
            if ( nums[mid] === target) return mid;
            if ( nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]){
                    right = mid;
                }else {
                    left = mid +1;
                }
            }else{
                if (nums[mid] < target && target <= nums[right]){
                    left = mid+1;
                } else {
                    right = mid;
                }
            }
        }
        return -1;
    };   
}

class LinkedList{
    reverseList = function(head) {
        let prev = null
        let curr = head
        while (curr !== null){
            let next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    };

    mergeTwoLists = function(list1, list2) {
        let dummy = new ListNode(-1);
        let curr = dummy;
        while (list1 !== null && list2 !== null){
            if ( list1.val <= list2.val){
                curr.next = list1
                list1 = list1.next
            }else{
                curr.next = list2
                list2 = list2.next
            }
            curr = curr.next
        }
        curr.next = list1 !== null ? list1 :list2
        return dummy.next;
    };
    
}