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

class MinStack {
  constructor() { this.stack = []; this.minStack = []; }
  push(val) {
    this.stack.push(val);
    this.minStack.push(Math.min(val, this.minStack[this.minStack.length-1] ?? val));
  }
  pop() { this.stack.pop(); this.minStack.pop(); }
  top() { return this.stack[this.stack.length-1]; }
  getMin() { return this.minStack[this.minStack.length-1]; }
}

function decodeString(s) {
  const stackNum = [], stackStr = [];
  let curNum=0, curStr='';
  for (let ch of s) {
    if(!isNaN(ch)) curNum = curNum*10 + (+ch);
    else if(ch==='['){ stackNum.push(curNum); curNum=0; stackStr.push(curStr); curStr=''; }
    else if(ch===']'){ curStr = stackStr.pop() + curStr.repeat(stackNum.pop()); }
    else curStr += ch;
  }
  return curStr;
}

function simplifyPath(path) {
  const stack = [];
  const parts = path.split('/');
  for (let part of parts) {
    if(part===''||part=='.') continue;
    if(part==='..') stack.pop(); else stack.push(part);
  }
  return '/' + stack.join('/');
}

function maxSlidingWindow(nums,k){
  const res=[], deque=[];
  for(let i=0;i<nums.length;i++){
    while(deque.length && deque[0]<=i-k) deque.shift();
    while(deque.length && nums[i]>=nums[deque[deque.length-1]]) deque.pop();
    deque.push(i);
    if(i>=k-1) res.push(nums[deque[0]]);
  }
  return res;
}

function orangesRotting(grid){
  const m=grid.length, n=grid[0].length;
  const queue=[];
  let fresh=0, minutes=0;
  
  for(let i=0;i<m;i++)
    for(let j=0;j<n;j++){
      if(grid[i][j]===2) queue.push([i,j]);
      else if(grid[i][j]===1) fresh++;
    }

  const dirs=[[0,1],[1,0],[0,-1],[-1,0]];
  while(queue.length && fresh>0){
    let sz=queue.length;
    for(let i=0;i<sz;i++){
      const [x,y]=queue.shift();
      for(let [dx,dy] of dirs){
        const nx=x+dx, ny=y+dy;
        if(nx<0||ny<0||nx>=m||ny>=n||grid[nx][ny]!==1) continue;
        grid[nx][ny]=2;
        queue.push([nx,ny]);
        fresh--;
      }
    }
    minutes++;
  }
  return fresh>0?-1:minutes;
}

class MinHeap {
  constructor(){ this.heap=[]; }
  insert(val){ 
    this.heap.push(val); 
    let i=this.heap.length-1; 
    while(i>0){ 
      const p=Math.floor((i-1)/2); 
      if(this.heap[p]<=this.heap[i]) break; 
      [this.heap[p],this.heap[i]]=[this.heap[i],this.heap[p]]; 
      i=p; 
    }
  }
  pop(){ 
    if(this.heap.length===1) return this.heap.pop();
    const top=this.heap[0]; this.heap[0]=this.heap.pop();
    let i=0;
    while(true){
      let left=2*i+1, right=2*i+2, smallest=i;
      if(left<this.heap.length && this.heap[left]<this.heap[smallest]) smallest=left;
      if(right<this.heap.length && this.heap[right]<this.heap[smallest]) smallest=right;
      if(smallest===i) break;
      [this.heap[i],this.heap[smallest]]=[this.heap[smallest],this.heap[i]];
      i=smallest;
    }
    return top;
  }
  peek(){ return this.heap[0]; }
}

function findKthLargest(nums,k){
  const heap=new MinHeap();
  for(let n of nums){
    heap.insert(n);
    if(heap.heap.length>k) heap.pop();
  }
  return heap.peek();
}

function twoSum(nums,target){
  const map=new Map();
  for(let i=0;i<nums.length;i++){
    if(map.has(target-nums[i])) return [map.get(target-nums[i]),i];
    map.set(nums[i],i);
  }
  return [];
}

function lengthOfLongestSubstring(s){
  const set=new Set();
  let l=0,res=0;
  for(let r=0;r<s.length;r++){
    while(set.has(s[r])) set.delete(s[l++]);
    set.add(s[r]);
    res=Math.max(res,r-l+1);
  }
  return res;
}

function reverseList(head){
  let prev=null, cur=head;
  while(cur){
    let next=cur.next;
    cur.next=prev;
    prev=cur;
    cur=next;
  }
  return prev;
}

function hasCycle(head){
  let slow=head, fast=head;
  while(fast && fast.next){
    slow=slow.next; fast=fast.next.next;
    if(slow===fast) return true;
  }
  return false;
}

function mergeTwoLists(l1,l2){
  const dummy={next:null}; let cur=dummy;
  while(l1 && l2){
    if(l1.val<l2.val){ cur.next=l1; l1=l1.next; }
    else{ cur.next=l2; l2=l2.next; }
    cur=cur.next;
  }
  cur.next=l1||l2;
  return dummy.next;
}

function inorder(root,res=[]){
  if(!root) return;
  inorder(root.left,res);
  res.push(root.val);
  inorder(root.right,res);
  return res;
}

function lowestCommonAncestor(root,p,q){
  if(!root||root===p||root===q) return root;
  const left=lowestCommonAncestor(root.left,p,q);
  const right=lowestCommonAncestor(root.right,p,q);
  if(left && right) return root;
  return left || right;
}

function height(root){
  if(!root) return 0;
  return 1 + Math.max(height(root.left), height(root.right));
}

class TrieNode{
  constructor(){ this.children={}; this.isWord=false; }
}

class Trie{
  constructor(){ this.root=new TrieNode(); }
  insert(word){
    let node=this.root;
    for(let c of word){
      if(!node.children[c]) node.children[c]=new TrieNode();
      node=node.children[c];
    }
    node.isWord=true;
  }
  search(word){
    let node=this.root;
    for(let c of word){
      if(!node.children[c]) return false;
      node=node.children[c];
    }
    return node.isWord;
  }
  startsWith(prefix){
    let node=this.root;
    for(let c of prefix){
      if(!node.children[c]) return false;
      node=node.children[c];
    }
    return true;
  }
}

// BFS
function bfs(graph,start){
  const visited=new Set();
  const queue=[start];
  const result=[];
  visited.add(start);
  while(queue.length){
    const node=queue.shift();
    result.push(node);
    for(const nei of graph[node]){
      if(!visited.has(nei)){
        visited.add(nei);
        queue.push(nei);
      }
    }
  }
  return result;
}

// Example adjacency list
const graph={
  0:[1,2],
  1:[0,3],
  2:[0,3],
  3:[1,2]
};

function numIslands(grid){
  const m=grid.length,n=grid[0].length;
  let res=0;
  function dfs(i,j){
    if(i<0||j<0||i>=m||j>=n||grid[i][j]==='0') return;
    grid[i][j]='0';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  }
  for(let i=0;i<m;i++)
    for(let j=0;j<n;j++)
      if(grid[i][j]==='1'){ dfs(i,j); res++; }
  return res;
}

function nextGreater(nums){
  const stack=[], res=Array(nums.length).fill(-1);
  for(let i=0;i<nums.length;i++){
    while(stack.length && nums[i]>nums[stack[stack.length-1]]){
      res[stack.pop()]=nums[i];
    }
    stack.push(i);
  }
  return res;
}

function dailyTemperatures(T){
  const stack=[], res=Array(T.length).fill(0);
  for(let i=0;i<T.length;i++){
    while(stack.length && T[i]>T[stack[stack.length-1]]){
      let idx=stack.pop();
      res[idx]=i-idx;
    }
    stack.push(i);
  }
  return res;
}