class TwoPointers {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

class TwoPointers {
  isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
      if (s[left] !== s[right]) return false;
      left++;
      right--;
    }
    return true;
  }
}

class SlidingWindow {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, maxLen = 0;
        Set set = new HashSet<>();
        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

class SlidingWindow {
  lengthOfLongestSubstring(s) {
    let left = 0, maxLen = 0;
    const set = new Set();
    for (let right = 0; right < s.length; right++) {
      while (set.has(s[right])) {
        set.delete(s[left++]);
      }
      set.add(s[right]);
      maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
  }
}

class FastSlowPointers {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

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

class BinarySearch {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

class BinarySearch {
  search(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      const mid = Math.floor(left + (right - left) / 2);
      if (nums[mid] === target) return mid;
      else if (nums[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
    return -1;
  }
}

class PrefixSum {
    public int subarraySum(int[] nums, int k) {
        Map map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, count = 0;
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

class PrefixSum {
  subarraySum(nums, k) {
    const map = new Map();
    map.set(0, 1);
    let sum = 0, count = 0;
    for (const num of nums) {
      sum += num;
      if (map.has(sum - k)) count += map.get(sum - k);
      map.set(sum, (map.get(sum) || 0) + 1);
    }
    return count;
  }
}

class MonotonicStack {
    public int[] nextGreaterElement(int[] nums) {
        Stack stack = new Stack<>();
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                res[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return res;
    }
}

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

class Kadanes {
    public int maxSubArray(int[] nums) {
        int max = nums[0], curr = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curr = Math.max(nums[i], curr + nums[i]);
            max = Math.max(max, curr);
        }
        return max;
    }
}

class Kadanes {
  maxSubArray(nums) {
    let max = nums[0], curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
      curr = Math.max(nums[i], curr + nums[i]);
      max = Math.max(max, curr);
    }
    return max;
  }
}

class DFS {
    public void preorder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
}

class DFS {
  preorder(root) {
    if (root === null) return;
    console.log(root.val);
    this.preorder(root.left);
    this.preorder(root.right);
  }
}

class BFS {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        if (root == null) return res;
        Queue q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(level);
        }
        return res;
    }
}

class BFS {
  levelOrder(root) {
    const res = [];
    if (root === null) return res;
    const q = [root];
    while (q.length) {
      const size = q.length;
      const level = [];
      for (let i = 0; i < size; i++) {
        const node = q.shift();
        level.push(node.val);
        if (node.left) q.push(node.left);
        if (node.right) q.push(node.right);
      }
      res.push(level);
    }
    return res;
  }
}

class Backtracking {
    List> res = new ArrayList<>();
    public List> combine(int n, int k) {
        backtrack(new ArrayList<>(), 1, n, k);
        return res;
    }
    private void backtrack(List curr, int start, int n, int k) {
        if (curr.size() == k) {
            res.add(new ArrayList<>(curr));
            return;
        }
        for (int i = start; i <= n; i++) {
            curr.add(i);
            backtrack(curr, i + 1, n, k);
            curr.remove(curr.size() - 1);
        }
    }
}

class Backtracking {
  constructor(){ this.res = []; }
  combine(n, k) {
    this.backtrack([], 1, n, k);
    return this.res;
  }
  backtrack(curr, start, n, k) {
    if (curr.length === k) {
      this.res.push([...curr]);
      return;
    }
    for (let i = start; i <= n; i++) {
      curr.push(i);
      this.backtrack(curr, i + 1, n, k);
      curr.pop();
    }
  }
}