/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    for (let i = 0; i<flowerbed.length; i++) {
        if (flowerbed[i] == 0
           && (i == 0 || flowerbed[i-1] == 0)
           && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
            n--
            flowerbed[i] = 1
            if (n < 1)
                return true
        }
    }

    return n <= 0
};

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
    products.sort((a, b) => {
        if (a > b) return 1
        if (a < b) return -1
        return 0
    })

    const r = []

    for (let i = 1; i<=searchWord.length; i++) {
        const arr = products.filter((s) => s.startsWith(searchWord.substring(0, i))).slice(0, 3)
        //console.log(searchWord.substring(0, i))
        r.push(arr)
    }

    return r
};

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function(intervals) {
    if (intervals.length < 1) return 0

    const startTimes = []
    const endTimes = []

    for (let i = 0; i<intervals.length; i++) {
        startTimes[i] = intervals[i][0]
        endTimes[i] = intervals[i][1]
    }

    startTimes.sort((a, b) => a-b)
    endTimes.sort((a, b) => a-b)

    let startPtr = 0
    let endPtr = 0
    let rooms = 0

    for (let i=0; i<intervals.length; i++) {
        if (startTimes[i] >= endTimes[endPtr]) {
            endPtr++
        } else {
            rooms++
        }
    }

    return rooms
};

/**
 * @param {string[]} logs
 * @return {string[]}
 */
var reorderLogFiles = function(logs) {

    const sorted = []
    const numLogs = []
    const charLogs = []

    for (let i = 0; i<logs.length; i++) {
        const log = logs[i]
        const tokenized = log.split(" ")
        if (Number.isInteger(parseInt(tokenized[1]))) {
            numLogs.push(log)
        } else {
            charLogs.push(log)
        }
    }

    charLogs.sort(function (a, b) {
        const stra = a.substr(a.indexOf(' ') + 1)
        const strb = b.substr(b.indexOf(' ') + 1)
        if (stra > strb) {
            return 1
        }
        if (stra < strb) {
            return -1
        }

        const ida = a.substr(0, a.indexOf(' '))
        const idb = b.substr(0, b.indexOf(' '))
        //console.log({ida})
        if (ida > idb) {
            return 1
        }
        if (ida < idb) {
            return -1
        }

        return 0
    })

    return [...charLogs, ...numLogs]

};

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const map = []

    for (let i = 0; i<strs.length; i++) {
        const str = strs[i].split('').sort().join('')
        if (!map[str]) map[str] = []
        map[str].push(strs[i])
    }
    const ans = []
    for (let k in map) {
        ans.push(map[k])
    }
    return ans
};

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const simple = [];
    const splitPath = path.split("/").filter(x => x.length>0 && x !== '.')

    for (let i = 0; i<splitPath.length; i++) {
        if (splitPath[i] === '..') {
            simple.pop()
        } else {
            simple.push(splitPath[i])
        }

    }

    return `/${simple.join('/')}`
};

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (x == 0) return 0

    if (n == 0) return 1

    if (n < 0) {
        x = 1/x
        n = -1 * n
    }

    const half = myPow(x, Math.floor(n/2))
    let ans = half * half

    if (n%2 == 1) ans = x * ans

    return ans
};

/**
 * @param {number[]} nums
 * @return {SparseVector}
 */
var SparseVector = function(nums) {
    const x = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            x.set(i, nums[i])
        }
    }
    this.map = x
    this.length = nums.length
    return this
};


// Return the dotProduct of two sparse vectors
/**
 * @param {SparseVector} vec
 * @return {number}
 */
SparseVector.prototype.dotProduct = function(vec) {
    let ans = 0;

    for (let i = 0; i < vec.length; i++) {
        if (vec.map.has(i) && this.map.has(i)) {
            ans += vec.map.get(i) * this.map.get(i)
        }
    }

    return ans
};

// Your SparseVector object will be instantiated and called as such:
// let v1 = new SparseVector(nums1);
// let v2 = new SparseVector(nums2);
// let ans = v1.dotProduct(v2);

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    let currPos = 1;
    let currNode = head;
    let startNode = head;
    let endNode = null;

    while(currPos < left) {
        startNode = currNode;
        currNode = currNode.next;
        currPos++;
    }

    let newList = null;
    let tail = currNode;

    while (currPos <= right) {
        const next = currNode.next;
        currNode.next = newList;
        newList = currNode;
        currNode = next;
        currPos++;
    }

    startNode.next = newList;
    tail.next = currNode;

    if (left > 1) {
        return head;
    }

    return newList;


};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    let currPos = 1;
    let currNode = head;
    let startNode = head;
    let endNode = null;
    
    while(currPos < left) {
        startNode = currNode;
        currNode = currNode.next;
        currPos++;
    }
    
    let newList = null;
    let tail = currNode;
    
    while (currPos <= right) {
        const next = currNode.next;
        currNode.next = newList;
        newList = currNode;
        currNode = next;
        currPos++;
    }
    
    startNode.next = newList;
    tail.next = currNode;
    
    if (left > 1) {
        return head;    
    }
    
    return newList;
    
    
};