10 Problem Solution

/*function validAnagram(s1, s2) {
    if(typeof s1 !== "string" || typeof s2 !== "string") {
        return false;
    }
    const len1 = s1.length;
    const len2 = s2.length;
    if(len1 !== len2) {
        return false;
    }
    const s1Map = {};
    for(let val of s1) {
        if(s1Map[val]) {
            s1Map[val] += 1;
        }else {
            s1Map[val] = 1;
        }
    }
    for(let val of s2) {
        if(s1Map[val] === undefined || s1Map[val] <= 0) {
            return false;
        }
        s1Map[val] -= 1;
    }
    return true;
}

console.log("validAnagram output - ", validAnagram("danger", "gardenn"));*/

function firstAndLastIndex(arr, target) {
    const len = arr.length;
    if(len === 0 || arr[0] > target || arr[len-1] < target) {
        return [-1, -1];
    }
    const firstIndex = getStartIndex(arr, target);
    if(firstIndex === -1) {
        return [-1, -1];
    }
    let lastIndex = getLastIndex(arr, target, firstIndex);
    return [firstIndex, lastIndex];
}

function getStartIndex(arr, target) {
    if(arr[0] === target) {
        return 0;
    }
    let start = 0, end = arr.length-1;
    while(start <= end) {
        const mid = Math.floor((start+end)/2);
        if(arr[mid] === target && arr[mid-1] < target) {
            return mid;
        }else if(arr[mid] < target) {
            start = mid+1;
        }else {
            end = mid-1;
        }
    }
    return -1;
}

function getLastIndex(arr, target, start) {
    let end = arr.length-1;
    if(arr[end] === target) {
        return end;
    }
    while(start <= end) {
        const mid = Math.floor((start+end)/2);
        if(arr[mid] === target && arr[mid+1] > target) {
            return mid;
        }else if(arr[mid] > target) {
            end = mid-1;
        }else {
            start = mid+1;
        }
    }
    return -1;
}

console.log("firstAndLastIndex output - ", firstAndLastIndex([1,2,2,2,3,4], 2));

class MinHeap {
    constructor(arr=[]) {
        this.data = arr;
        if(this.data.length > 1) {
            for(let i=this.data.length-1;i >= 0;i--) {
                this.siftdown(i);
            }
        }
    }
    siftup(index) {
        if(index >= this.data.length || index <= 0) {
            return null;
        }
        let parent = Math.floor((index-1)/2);
        while(index > 0 && this.data[index] < this.data[parent]) {
            const temp = this.data[index];
            this.data[index] = this.data[parent];
            this.data[parent] = temp;
            index = parent;
            parent = Math.floor((index-1)/2);
        }
    }
    siftdown(index) {
        if(index >= this.data.length/2 || index < 0) {
            return null;
        }
        let left = 2*index+1;
        let right = 2*index+2;
        while(left < this.data.length && (this.data[index] > this.data[left] || (right < this.data.length && this.data[index] > this.data[right]))) {
            const min = right >= this.data.length || this.data[left] <= this.data[right] ? left : right;
            const temp = this.data[index];
            this.data[index] = this.data[min];
            this.data[min] = temp;
            index = min;
            left = 2*index+1;
            right = 2*index+2;
        }
    }
    insert(item) {
        this.data.push(item);
        this.siftup(this.data.length-1);
    }
    get_min() {
        return this.data[0];
    }
    extract_min() {
        if(this.data.length === 0) {
            return null;
        }
        const return_val = this.data[0];
        this.data[0] = this.data.pop();
        this.siftdown(0);
        return return_val;
    }
    update_by_index(val, index) {
        if(index < 0 || index >= this.data.length) {
            return null;
        }
        const current_val = this.data[index];
        this.data[index] = val;
        if(val > current_val) {
            this.siftdown(index);
        }else if(val < current_val) {
            this.siftup(index);
        }
        return true;
    }
    update(oldVal, newVal) {
        for(let i=0;i<this.data.length;i++) {
            if(this.data[i] === oldVal) {
                this.update_by_index(newVal, i);
                return true;
            }
        }
        return false;
    }
}

class MaxHeap {
    constructor(arr=[]) {
        this.data = arr;
        if(this.data.length > 1) {
            for(let i=this.data.length-1;i>=0;i--) {
                this.siftdown(i);
            }
        }
    }
    siftup(index) {
        if(index <= 0 || index >= this.data.length) {
            return null;
        }
        let parent = Math.floor((index-1)/2);
        while(index > 0 && this.data[parent] < this.data[index]) {
            const temp = this.data[index];
            this.data[index] = this.data[parent];
            this.data[parent] = temp;
            index = parent;
            parent = Math.floor((index-1)/2);
        }
    }
    siftdown(index) {
        if(index < 0 || index >= this.data.length-1) {
            return null;
        }
        let left = 2*index+1;
        let right = 2*index+2;
        while(left < this.data.length && (this.data[index] < this.data[left] || (right < this.data.length && this.data[index] < this.data[right]))) {
            const maxValIndex = right >= this.data.length || this.data[left] > this.data[right] ? left : right;
            const temp = this.data[index];
            this.data[index] = this.data[maxValIndex];
            this.data[maxValIndex] = temp;
            index = maxValIndex;
            left = 2*index+1;
            right = 2*index+2;
        }
    }
    insert(item) {
        this.data.push(item);
        this.siftup(this.data.length-1);
    }
    get_max() {
        return this.data[0];
    }
    extract_max() {
        if(this.data.length === 0) {
            return null;
        }
        const return_val = this.data[0];
        this.data[0] = this.data.pop();
        this.siftdown(0);
        return return_val;
    }
    update_by_index(val, index) {
        if(index < 0 || index >= this.data.length) {
            return null;
        }
        const current_val = this.data[index];
        this.data[index] = val;
        if(val > current_val) {
            this.siftup(index);
        }else if(val < current_val) {
            this.siftdown(index);
        }
        return true;
    }
    update(oldVal, newVal) {
        for(let i=0;i<this.data.length;i++) {
            if(this.data[i] === oldVal) {
                this.update_by_index(newVal, i);
                return true;
            }
        }
        return false;
    }
}

const inputArr = [4,2,9,7,5,6,7,1,3];
const k = 4;

function getKthLargestElement(arr, k) {
    const len = arr.length;
    if(len < k) {
        return null;
    }
    const getMaxHeap = new MaxHeap(arr);
    for(let i=1;i<k;i++) {
        getMaxHeap.extract_max();
    }
    return getMaxHeap.get_max();
}

// Symetrical tree

function isSymetricalTree(root=null) {
    if(root === null || (root.left === null && root.right === null)) {
        return true;
    }
    function symetricalStatus(leftTree, rightTree) {
        if(leftTree === null && rightTree === null) {
            return true;
        }else if(leftTree === null || rightTree === null) {
            return false;
        }else {
            if(leftTree.val !== rightTree.val) {
                return false;
            }
            return symetricalStatus(leftTree.left, rightTree.right) && symetricalStatus(leftTree.right, rightTree.left);
        }
    }
    return symetricalStatus(root.left, root.right);
}

// Generate Valid Parenthesis of payer n

function Generate(n) {
    function Parenthesis(num, diff, comb, combs) {
        if(diff < 0 || diff > n) {
            return null;
        }else if(num === 0) {
            if(diff === 0) {
                combs.push(comb.join(""));
            }
        }else {
            comb.push("(");
            Parenthesis(num-1, diff+1, comb, combs);
            comb.pop();
            comb.push(")");
            Parenthesis(num-1, diff-1, comb, combs);
            comb.pop();
        }
    }
    const combs = [];
    Parenthesis(n*2, 0, [], combs);
    return combs;
}

// console.log(Generate(3));

// Petrol pump station
function getIndex(gasArr, costArr) {
    const len = gasArr.length;
    let currentGas = 0;
    let startIndex = 0, currentIndex = 0, isStarted = false;
    while(startIndex < len) {
        while(currentGas >= 0 && (currentIndex !== startIndex || !isStarted)) {
            isStarted = true;
            currentGas += gasArr[currentIndex]-costArr[currentIndex];
            currentIndex = (currentIndex+1)%len;
        }
        if(currentGas >= 0 && currentIndex === startIndex) {
            return startIndex;
        }else if(currentIndex <= startIndex) {
            return -1;
        }
        currentGas = 0;
        isStarted = false;
        startIndex = currentIndex;
    }
    return -1;
}

function getStationIndex(gasArr, costArr) {
    const len = gasArr.length;
    let totalGas = 0, prevGas = 0;
    let startIndex = 0;
    for(let i=0;i<len;i++) {
        prevGas += gasArr[i]-costArr[i];
        if(prevGas < 0) {
            startIndex = i+1;
            totalGas += prevGas;
            prevGas = 0;
        }
    }
    if(startIndex >= len || prevGas+totalGas < 0) {
        return -1;
    }else {
        return startIndex;
    }
}

console.log(getIndex([1,5,3,3,5,3,1,3,4,5],[5,2,2,8,2,4,2,5,1,2]));
console.log(getIndex([2,2,2,2,2,2,2,2,2,2],[1,1,1,1,1,1,1,1,1,50]));
console.log(getStationIndex([1,5,3,3,5,3,1,3,4,5],[5,2,2,8,2,4,2,5,1,2]));
console.log(getStationIndex([2,2,2,2,2,2,2,2,2,2],[1,1,1,1,1,1,1,1,1,50]));

// All Schedule Problem
function isAllSchedule(n, preRequisiteArr=[]) {
    const len = preRequisiteArr.length;
    if(len < 2) {
        return true;
    }
    const doneCourses = new Set();
    let ongoingCourse = new Set();
    const courseDependencyMap = new Map();
    for(let [mainCourse, dependentCourse] of preRequisiteArr) {
        if(courseDependencyMap.has(mainCourse)) {
            courseDependencyMap.set(mainCourse, [...courseDependencyMap.get(mainCourse), dependentCourse]);
        }else {
            courseDependencyMap.set(mainCourse, [dependentCourse]);
        }
    }
    function traverseMap(mainCourse, dependentCourseArr) {
        if(!dependentCourseArr || dependentCourseArr.length === 0 || doneCourses.has(mainCourse)) {
            doneCourses.add(mainCourse);
            return true;
        }else if(ongoingCourse.has(mainCourse)) {
            return false;
        }else {
            ongoingCourse.add(mainCourse);
            for(let course of dependentCourseArr) {
                if(!traverseMap(course, courseDependencyMap.get(course))) {
                    return false;
                }
            }
            ongoingCourse.delete(mainCourse);
            doneCourses.add(mainCourse);
            return true;
        }
    }
    for(let [course,dependentCourseArr] of courseDependencyMap) {
        if(doneCourses.has(course)) {
            continue;
        }else {
            if(!traverseMap(course, dependentCourseArr)) {
                return false;
            }
            ongoingCourse = new Set();
        }
    }
    return true;
}

console.log(isAllSchedule(6, [[0,1],[1,3],[2,1],[4,1],[4,2],[5,3],[5,4]]));

// create permutation with number n starting with 1
function swap(str, index1, index2) {
    if(index1 === index2) {
        return str;
    }
    const str1 = str[index1];
    const str2 = str[index2];
    return str.substring(0,index1)+str2+str.substring(index1+1,index2)+str1+str.substring(index2+1);
}
function printPermutation(str, start, end) {
    if(start === end) {
        console.log(str);
        return;
    }
    for(let i=start;i<=end;i++) {
        let tempStr = swap(str,start,i);
        printPermutation(tempStr, start+1, end);
    }
    return;
}

function createAllPermutation(n) {
    let str = "";
    for(let i=1;i<=n;i++) {
        str += i;
    }
    if(n < 2) {
        console.log(str);
        return;
    }
    printPermutation(str, 0, n-1);
    return;
}
createAllPermutation(3);

// give kth permutation
function factorial(n) {
    let result = 1, resultMap = {};
    for(let i=1;i<=n;i++) {
        result *= i;
        resultMap[i] = result;
    }
    return resultMap;
}

function getKthPermutation(n, k) {
    const totalPermMap = factorial(n);
    if(k < 1 || k > totalPermMap[n]) {
        return null;
    }
    const permArr = [];
    for(let i=1;i<=n;i++) {
        permArr.push(i);
    }
    if(k === 1) {
        return permArr.join("");
    }
    const resultArr = [];
    k -= 1;
    while(n > 0) {
        const totalPerm = totalPermMap[n];
        const partLength = totalPerm/n;
        const section = Math.floor(k/partLength);
        const currentNum = permArr[section];
        resultArr.push(currentNum);
        permArr.splice(section, 1);
        n--;
        k = k%partLength;
    }
    return resultArr.join("");
}
console.log(getKthPermutation(4,16));

// window substring problem
function mapLetters(s1) {
    const map1 = {};
    for(let str of s1) {
        if(typeof map1[str] === "number") {
            map1[str] += 1;
        }else {
            map1[str] = 1;
        }
    }
    return map1;
}

function getMinimumSubstring(s1, s2) {
    const len1 = s1.length, len2 = s2.length;
    if(len2 > len1) {
        return null;
    }
    const map1 = mapLetters(s1), map2 = mapLetters(s2);
    let totalConditions = 0;
    for(let key of Object.keys(map2)){
        if(!map1[key] || map1[key] < map2[key]) {
            return null;
        }
        totalConditions++;
    };
    const prevMap = mapLetters(s1.substr(0, len2-1));
    let prevCondition = 0;
    Object.keys(prevMap).forEach(key => {
        if(key in map2 && prevMap[key] >= map2[key]) {
            prevCondition++;
        }
    });
    for(let length=len2;length<=len1;length++) {
        if(s1[length-1] in prevMap) {
            prevMap[s1[length-1]] += 1;
        }else {
            prevMap[s1[length-1]] = 1;
        }
        if(s1[length-1] in map2 && prevMap[s1[length-1]] === map2[s1[length-1]]) {
            prevCondition++;
        }
        const currMap = Object.assign({},prevMap);
        let currCondition = prevCondition;
        for(let index=0;index<=len1-length;index++) {
            if(index > 0) {
                const newChar = s1[index+length-1];
                const oldChar = s1[index-1];
                if(newChar in currMap) {
                    currMap[newChar] += 1;
                }else {
                    currMap[newChar] = 1;
                }
                if(newChar in map2 && currMap[newChar] === map2[newChar]) {
                    currCondition++;
                }
                if(oldChar in map2 && currMap[oldChar] === map2[oldChar]) {
                    currCondition--;
                }
                currMap[oldChar] -= 1;
            }
            if(currCondition === totalConditions) {
                return s1.substr(index, length);   
            }
        }
    }
    return null;
}

function getMinSubString(src, tgt) {
    const srcLen = src.length, tgtLen = tgt.length;
    if(tgtLen > srcLen) {
        return null;
    }
    const srcMap = mapLetters(src), tgtMap = mapLetters(tgt);
    let totalConditions = 0;
    for(let key of Object.keys(tgtMap)){
        if(!srcMap[key] || srcMap[key] < tgtMap[key]) {
            return null;
        }
        totalConditions++;
    };
    let start = 0, end = srcLen-1, left = 0, satisfied = 0;
    const currMap = {};
    for(let right=0;right<srcLen;right++) {
        currMap[src[right]] = typeof currMap[src[right]] === "number" ? currMap[src[right]]+1 : 1;
        if(src[right] in tgtMap && currMap[src[right]] === tgtMap[src[right]]) {
            satisfied++;
        }
        if(satisfied === totalConditions) {
            while(!(src[left] in tgtMap) || currMap[src[left]] > tgtMap[src[left]]) {
                currMap[src[left]] -= 1;
                left++;
            }
            if(end-start > right-left) {
                start = left;
                end = right;
            }
        }
    }
    return src.substring(start, end+1);
}
console.log(getMinimumSubstring("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCA"));
console.log(getMinimumSubstring("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCZ"));
console.log(getMinSubString("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCA"));
console.log(getMinSubString("ADCFEBECEABEBADFCDFCBFCBEAD", "ABCZ"));
console.log(getMinSubString("ADCFEBECEABEBADFCDFCBFCBEAD", "ADCFEBECEABEBADFCDFCBFCBEAD"));

//Largest Rectangle in histogram
function getSmallestFromLeft(arr) {
    const stack = [], result = [-1];
    stack.push({value: arr[0], index: 0});
    for(let i=1;i<arr.length;i++) {
        while(stack.length > 0 && stack[stack.length-1].value > arr[i]) {
            stack.pop();
        }
        if(stack.length === 0) {
            result.push(-1);
        }else {
            result.push(stack[stack.length-1].index);
        }
        stack.push({value: arr[i], index: i});
    }
    return result;
}

function getSmallestFromRight(arr) {
    const len = arr.length;
    const stack = [], result = new Array(len);
    result[len-1] = len;
    stack.push({value: arr[len-1], index: len-1});
    for(let i=len-2;i>=0;i--) {
        while(stack.length > 0 && stack[stack.length-1].value > arr[i]) {
            stack.pop();
        }
        if(stack.length === 0) {
            result[i] = len;
        }else {
            result[i] = stack[stack.length-1].index;
        }
        stack.push({value: arr[i], index: i});
    }
    return result;
}

function getLargestRectangle(heights) {
    const len = heights.length;
    if(len === 0) {
        return 0;
    }else if(len === 1) {
        return heights[0];
    }
    const fromLeft = getSmallestFromLeft(heights);
    const fromRight = getSmallestFromRight(heights);
    let result = -Infinity;
    for(let i=0;i<len;i++) {
        result = Math.max(result, heights[i]*(fromRight[i]-fromLeft[i]-1));
    }
    return result;
}
console.log(getLargestRectangle([3,2,4,5,7,6,1,3,8,9,11,10,7,5,2,6]));