DSA Problems

Given a string `s`, find the length of the **longest substring** without repeating characters. ### Examples ```js lengthOfLongestSubstring("abcabcbb"); // 3 // Explanation: The answer is "abc", with the length of 3. lengthOfLongestSubstring("bbbbb"); // 1 // Explanation: The answer is "b", with the length of 1. lengthOfLongestSubstring("pwwkew"); // 3 // Explanation: The answer is "wke", with the length of 3. ``` ### Constraints - `0 <= s.length <= 5 * 10^4` - `s` consists of English letters, digits, symbols and spaces.

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A **subarray** is a contiguous part of an array. ### Examples ```js maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6 // Explanation: [4, -1, 2, 1] has the largest sum = 6. maxSubArray([1]); // 1 maxSubArray([5, 4, -1, 7, 8]); // 23 ``` ### Constraints - `1 <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4`

Given the head of a singly linked list, reverse the list, and return the reversed list. ### Examples ```js // Input: head = [1, 2, 3, 4, 5] // Output: [5, 4, 3, 2, 1] // Input: head = [1, 2] // Output: [2, 1] // Input: head = [] // Output: [] ``` ### Constraints - The number of nodes in the list is the range `[0, 5000]`. - `-5000 <= Node.val <= 5000`

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`. You must write an algorithm with `O(log n)` runtime complexity. ### Examples ```js search([-1, 0, 3, 5, 9, 12], 9); // 4 // Explanation: 9 exists in nums and its index is 4 search([-1, 0, 3, 5, 9, 12], 2); // -1 // Explanation: 2 does not exist in nums so return -1 ``` ### Constraints - `1 <= nums.length <= 10^4` - `-10^4 < nums[i], target < 10^4` - All the integers in `nums` are unique. - `nums` is sorted in ascending order.

Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return the number of islands. An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. ### Examples ```js numIslands([ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]); // 1 numIslands([ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]); // 3 ``` ### Constraints - `m == grid.length` - `n == grid[i].length` - `1 <= m, n <= 300` - `grid[i][j]` is `'0'` or `'1'`.

You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top? ### Examples ```js climbStairs(2); // 2 // Explanation: There are two ways to climb to the top. // 1. 1 step + 1 step // 2. 2 steps climbStairs(3); // 3 // Explanation: There are three ways to climb to the top. // 1. 1 step + 1 step + 1 step // 2. 1 step + 2 steps // 3. 2 steps + 1 step ``` ### Constraints - `1 <= n <= 45`

Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. 3. Every close bracket has a corresponding open bracket of the same type. ### Examples ```js isValid("()"); // true isValid("()[]{}"); // true isValid("(]"); // false isValid("([)]"); // false isValid("{[]}"); // true ``` ### Constraints - `1 <= s.length <= 10^4` - `s` consists of parentheses only `'()[]{}'`.

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`th day. You want to maximize your profit by choosing a **single day** to buy one stock and choosing a **different day in the future** to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`. ### Examples ```js maxProfit([7, 1, 5, 3, 6, 4]); // 5 // Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. maxProfit([7, 6, 4, 3, 1]); // 0 // Explanation: In this case, no transactions are done and the max profit = 0. ``` ### Constraints - `1 <= prices.length <= 10^5` - `0 <= prices[i] <= 10^4`

Given an array of `intervals` where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. ### Examples ```js merge([[1, 3], [2, 6], [8, 10], [15, 18]]); // [[1, 6], [8, 10], [15, 18]] // Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. merge([[1, 4], [4, 5]]); // [[1, 5]] // Explanation: Intervals [1,4] and [4,5] are considered overlapping. ``` ### Constraints - `1 <= intervals.length <= 10^4` - `intervals[i].length == 2` - `0 <= start_i <= end_i <= 10^4`

Given an array of integers `nums` and an integer `target`, return **indices of the two numbers** such that they add up to `target`. You may assume that each input would have **exactly one solution**, and you may not use the same element twice. You can return the answer in any order. ### Examples ```js twoSum([2, 7, 11, 15], 9); // [0, 1] // Explanation: nums[0] + nums[1] = 2 + 7 = 9 twoSum([3, 2, 4], 6); // [1, 2] // Explanation: nums[1] + nums[2] = 2 + 4 = 6 twoSum([3, 3], 6); // [0, 1] ``` ### Constraints - `2 <= nums.length <= 10^4` - `-10^9 <= nums[i] <= 10^9` - `-10^9 <= target <= 10^9` - Only one valid answer exists.

Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order. ### Examples ```js topKFrequent([1, 1, 1, 2, 2, 3], 2); // [1, 2] topKFrequent([1], 1); // [1] ``` ### Constraints - `1 <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4` - `k` is in the range `[1, the number of unique elements in the array]`. - It is guaranteed that the answer is unique.

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays. The overall run time complexity should be `O(log (m+n))`. ### Examples ```js findMedianSortedArrays([1, 3], [2]); // 2.0 // Explanation: merged array = [1, 2, 3] and median is 2. findMedianSortedArrays([1, 2], [3, 4]); // 2.5 // Explanation: merged array = [1, 2, 3, 4] and median is (2 + 3) / 2 = 2.5. ``` ### Constraints - `nums1.length == m` - `nums2.length == n` - `0 <= m <= 1000` - `0 <= n <= 1000` - `1 <= m + n <= 2000` - `-10^6 <= nums1[i], nums2[i] <= 10^6`

Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, and `j != k`, and `nums[i] + nums[j] + nums[k] == 0`. Notice that the solution set must not contain duplicate triplets. ### Examples ```js threeSum([-1, 0, 1, 2, -1, -4]); // [[-1, -1, 2], [-1, 0, 1]] // Explanation: // nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. // nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. // The distinct triplets are [-1,0,1] and [-1,-1,2]. threeSum([0, 1, 1]); // [] // Explanation: The only possible triplet does not sum up to 0. threeSum([0, 0, 0]); // [[0, 0, 0]] ``` ### Constraints - `3 <= nums.length <= 3000` - `-10^5 <= nums[i] <= 10^5`

Given an array of integers `nums` and an integer `k`, return the total number of subarrays whose sum equals `k`. A subarray is a contiguous non-empty sequence of elements within an array. ### Examples ```js subarraySum([1, 1, 1], 2); // 2 // Explanation: The subarrays [1,1] and [1,1] have sum 2. subarraySum([1, 2, 3], 3); // 2 // Explanation: The subarrays [1,2] and [3] have sum 3. ``` ### Constraints - `1 <= nums.length <= 2 * 10^4` - `-1000 <= nums[i] <= 1000` - `-10^7 <= k <= 10^7`

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. ### Examples ```js // Input: lists = [[1,4,5],[1,3,4],[2,6]] // Output: [1,1,2,3,4,4,5,6] // Explanation: The linked-lists are: // [ // 1->4->5, // 1->3->4, // 2->6 // ] // merging them into one sorted list: // 1->1->2->3->4->4->5->6 // Input: lists = [] // Output: [] // Input: lists = [[]] // Output: [] ``` ### Constraints - `k == lists.length` - `0 <= k <= 10^4` - `0 <= lists[i].length <= 500` - `-10^4 <= lists[i][j] <= 10^4` - `lists[i]` is sorted in ascending order. - The sum of `lists[i].length` will not exceed `10^4`.

There is an integer array `nums` sorted in ascending order (with distinct values). Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k` (1 <= k < nums.length) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (0-indexed). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`. Given the array `nums` after the rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`. You must write an algorithm with `O(log n)` runtime complexity. ### Examples ```js search([4, 5, 6, 7, 0, 1, 2], 0); // 4 search([4, 5, 6, 7, 0, 1, 2], 3); // -1 search([1], 0); // -1 ``` ### Constraints - `1 <= nums.length <= 5000` - `-10^4 <= nums[i] <= 10^4` - All values of `nums` are unique. - `nums` is an ascending array that is possibly rotated. - `-10^4 <= target <= 10^4`

Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining. ### Examples ```js trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]); // 6 // Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. trap([4, 2, 0, 3, 2, 5]); // 9 ``` ### Constraints - `n == height.length` - `1 <= n <= 2 * 10^4` - `0 <= height[i] <= 10^5`

Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in `O(n)` time. ### Examples ```js longestConsecutive([100, 4, 200, 1, 3, 2]); // 4 // Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]); // 9 ``` ### Constraints - `0 <= nums.length <= 10^5` - `-10^9 <= nums[i] <= 10^9`

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [a_i, b_i]` indicates that you must take course `b_i` first if you want to take course `a_i`. - For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`. Return `true` if you can finish all courses. Otherwise, return `false`. ### Examples ```js canFinish(2, [[1, 0]]); // true // Explanation: There are a total of 2 courses to take. // To take course 1 you should have finished course 0. So it is possible. canFinish(2, [[1, 0], [0, 1]]); // false // Explanation: There are a total of 2 courses to take. // To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible. ``` ### Constraints - `1 <= numCourses <= 2000` - `0 <= prerequisites.length <= 5000` - `prerequisites[i].length == 2` - `0 <= a_i, b_i < numCourses` - All the pairs `prerequisites[i]` are unique.

Given a string `s`, return the longest palindromic substring in `s`. ### Examples ```js longestPalindrome("babad"); // "bab" or "aba" // Explanation: Both "bab" and "aba" are valid answers. longestPalindrome("cbbd"); // "bb" longestPalindrome("a"); // "a" ``` ### Constraints - `1 <= s.length <= 1000` - `s` consist of only digits and English letters.

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`th line are `(i, 0)` and `(i, height[i])`. Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. **Notice** that you may not slant the container. ### Examples ```js maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]); // 49 // Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. maxArea([1, 1]); // 1 ``` ### Constraints - `n == height.length` - `2 <= n <= 10^5` - `0 <= height[i] <= 10^4`

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer. You must write an algorithm that runs in `O(n)` time and without using the division operator. ### Examples ```js productExceptSelf([1, 2, 3, 4]); // [24, 12, 8, 6] // Explanation: answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, answer[2] = 1*2*4 = 8, answer[3] = 1*2*3 = 6 productExceptSelf([-1, 1, 0, -3, 3]); // [0, 0, 9, 0, 0] ``` ### Constraints - `2 <= nums.length <= 10^5` - `-30 <= nums[i] <= 30` - The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer.

Given an array of strings `strs`, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. ### Examples ```js groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]); // [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]] groupAnagrams([""]); // [[""]] groupAnagrams(["a"]); // [["a"]] ``` ### Constraints - `1 <= strs.length <= 10^4` - `0 <= strs[i].length <= 100` - `strs[i]` consists of lowercase English letters.

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. ### Examples ```js exist([["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], "ABCCED"); // true exist([["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], "SEE"); // true exist([["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], "ABCB"); // false ``` ### Constraints - `m == board.length` - `n = board[i].length` - `1 <= m, n <= 6` - `1 <= word.length <= 15` - `board` and `word` consists of only lowercase and uppercase English letters.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. ### Examples ```js rob([1, 2, 3, 1]); // 4 // Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). // Total amount you can rob = 1 + 3 = 4. rob([2, 7, 9, 3, 1]); // 12 // Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). // Total amount you can rob = 2 + 9 + 1 = 12. ``` ### Constraints - `1 <= nums.length <= 100` - `0 <= nums[i] <= 400`

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`. You may assume that you have an infinite number of each kind of coin. ### Examples ```js coinChange([1, 2, 5], 11); // 3 // Explanation: 11 = 5 + 5 + 1 coinChange([2], 3); // -1 // Explanation: The amount of 3 cannot be made up with coins of value 2. coinChange([1], 0); // 0 ``` ### Constraints - `1 <= coins.length <= 12` - `1 <= coins[i] <= 2^31 - 1` - `0 <= amount <= 10^4`

Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: - The left subtree of a node contains only nodes with keys less than the node's key. - The right subtree of a node contains only nodes with keys greater than the node's key. - Both the left and right subtrees must also be binary search trees. ### Examples ```js // Input: root = [2, 1, 3] // Output: true // Input: root = [5, 1, 4, null, null, 3, 6] // Output: false // Explanation: The root node's value is 5 but its right child's value is 4. ``` ### Constraints - The number of nodes in the tree is in the range `[1, 10^4]`. - `-2^31 <= Node.val <= 2^31 - 1`

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. ### Examples ```js wordBreak("leetcode", ["leet", "code"]); // true // Explanation: Return true because "leetcode" can be segmented as "leet code". wordBreak("applepenapple", ["apple", "pen"]); // true // Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". // Note that you are allowed to reuse a dictionary word. wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]); // false ``` ### Constraints - `1 <= s.length <= 300` - `1 <= wordDict.length <= 1000` - `1 <= wordDict[i].length <= 20` - `s` and `wordDict[i]` consist of only lowercase English letters. - All the strings of `wordDict` are unique.

Given an `m x n` matrix, return all elements of the matrix in spiral order. ### Examples ```js spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]); // [1, 2, 3, 6, 9, 8, 7, 4, 5] spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]); // [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] ``` ### Constraints - `m == matrix.length` - `n == matrix[i].length` - `1 <= m, n <= 10` - `-100 <= matrix[i][j] <= 100`

Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**. Implement the `LRUCache` class: - `LRUCache(int capacity)` Initialize the LRU cache with positive size `capacity`. - `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`. - `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, **evict** the least recently used key. The functions `get` and `put` must each run in `O(1)` average time complexity. ### Examples ```js const lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4 ``` ### Constraints - `1 <= capacity <= 3000` - `0 <= key <= 10^4` - `0 <= value <= 10^5` - At most `2 * 10^5` calls will be made to `get` and `put`.

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. ### Examples ```js // Input: l1 = [2,4,3], l2 = [5,6,4] // Output: [7,0,8] // Explanation: 342 + 465 = 807 // Input: l1 = [0], l2 = [0] // Output: [0] // Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] // Output: [8,9,9,9,0,0,0,1] ``` ### Constraints - The number of nodes in each linked list is in the range `[1, 100]`. - `0 <= Node.val <= 9` - It is guaranteed that the list represents a number that does not have leading zeros.

Given an integer array `nums` and an integer `k`, return the **kth largest element** in the array. Note that it is the kth largest element in **sorted order**, not the kth distinct element. You must solve it in **O(n)** time complexity on average. ### Examples ```js findKthLargest([3, 2, 1, 5, 6, 4], 2); // 5 // Explanation: Sorted: [1, 2, 3, 4, 5, 6]. 2nd largest is 5 findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4); // 4 // Explanation: Sorted: [1, 2, 2, 3, 3, 4, 5, 5, 6]. 4th largest is 4 findKthLargest([1], 1); // 1 ``` ### Constraints - `1 <= k <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4`

Given `n` pairs of parentheses, write a function to generate all combinations of **well-formed parentheses**. ### Examples ```js generateParenthesis(3); // ["((()))", "(()())", "(())()", "()(())", "()()()"] generateParenthesis(1); // ["()"] generateParenthesis(2); // ["(())", "()()"] ``` ### Constraints - `1 <= n <= 8`

You are given an `m x n` grid where each cell can have one of three values: - `0` representing an empty cell, - `1` representing a fresh orange, or - `2` representing a rotten orange. Every minute, any fresh orange that is **4-directionally adjacent** to a rotten orange becomes rotten. Return the **minimum number of minutes** that must elapse until no cell has a fresh orange. If this is impossible, return `-1`. ### Examples ```js orangesRotting([[2,1,1], [1,1,0], [0,1,1]]); // 4 // Explanation: After minute 0, 1, 2, 3, 4 the grid becomes: // [2,2,2] [2,2,2] [2,2,2] [2,2,2] [2,2,2] // [2,2,0] [2,2,0] [2,2,0] [2,2,0] [2,2,0] // [0,2,2] [0,2,2] [0,2,2] [0,2,2] [0,2,2] orangesRotting([[2,1,1], [0,1,1], [1,0,1]]); // -1 // Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten. orangesRotting([[0,2]]); // 0 // Explanation: Since there are no fresh oranges, 0 minutes have passed. ``` ### Constraints - `m == grid.length` - `n == grid[i].length` - `1 <= m, n <= 10` - `grid[i][j]` is `0`, `1`, or `2`.

You are given an `n x n` 2D matrix representing an image. Rotate the image by **90 degrees (clockwise)**. You have to rotate the image **in-place**, which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation. ### Examples ```js // Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] // Output: [[7,4,1],[8,5,2],[9,6,3]] // Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] // Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] ``` ### Constraints - `n == matrix.length == matrix[i].length` - `1 <= n <= 20` - `-1000 <= matrix[i][j] <= 1000`

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string `""`. ### Examples ```js longestCommonPrefix(["flower", "flow", "flight"]); // "fl" longestCommonPrefix(["dog", "racecar", "car"]); // "" // Explanation: There is no common prefix among the input strings. longestCommonPrefix(["interspecies", "interstellar", "interstate"]); // "inters" longestCommonPrefix(["throne", "throne"]); // "throne" ``` ### Constraints - `1 <= strs.length <= 200` - `0 <= strs[i].length <= 200` - `strs[i]` consists of only lowercase English letters.

Given an integer array `nums`, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the answer will fit in a **32-bit integer**. ### Examples ```js maxProduct([2, 3, -2, 4]); // 6 // Explanation: [2, 3] has the largest product 6. maxProduct([-2, 0, -1]); // 0 // Explanation: The result cannot be 2, because [-2, -1] is not a contiguous subarray. maxProduct([-2, 3, -4]); // 24 // Explanation: [-2, 3, -4] has the largest product 24. ``` ### Constraints - `1 <= nums.length <= 2 * 10^4` - `-10 <= nums[i] <= 10` - The product of any prefix or suffix of `nums` is guaranteed to fit in a **32-bit integer**.

Given the `root` of a binary tree, invert the tree, and return its root. ### Examples ```js // Input: root = [4,2,7,1,3,6,9] // Output: [4,7,2,9,6,3,1] // Input: root = [2,1,3] // Output: [2,3,1] // Input: root = [] // Output: [] ``` ### Constraints - The number of nodes in the tree is in the range `[0, 100]`. - `-100 <= Node.val <= 100`

Given the `root` of a binary tree, return its **maximum depth**. A binary tree's **maximum depth** is the number of nodes along the longest path from the root node down to the farthest leaf node. ### Examples ```js // Input: root = [3,9,20,null,null,15,7] // Output: 3 // Input: root = [1,null,2] // Output: 2 ``` ### Constraints - The number of nodes in the tree is in the range `[0, 10^4]`. - `-100 <= Node.val <= 100`

Given a reference of a node in a **connected undirected graph**, return a **deep copy (clone)** of the graph. Each node in the graph contains a `val` (int) and a list (`neighbors`) of its neighbors. ### Examples ```js // Input: adjList = [[2,4],[1,3],[2,4],[1,3]] // Output: [[2,4],[1,3],[2,4],[1,3]] // Explanation: There are 4 nodes in the graph. // 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). // 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). // 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). // 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). // Input: adjList = [[]] // Output: [[]] // Input: adjList = [] // Output: [] ``` ### Constraints - The number of nodes in the graph is in the range `[0, 100]`. - `1 <= Node.val <= 100` - `Node.val` is unique for each node. - There are no repeated edges and no self-loops in the graph. - The graph is connected and undirected.

Given an integer array `nums`, return the length of the longest **strictly increasing subsequence**. ### Examples ```js lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]); // 4 // Explanation: The longest increasing subsequence is [2, 3, 7, 18], therefore the length is 4. lengthOfLIS([0, 1, 0, 3, 2, 3]); // 4 lengthOfLIS([7, 7, 7, 7, 7, 7, 7]); // 1 ``` ### Constraints - `1 <= nums.length <= 2500` - `-10^4 <= nums[i] <= 10^4`

Given a string `s`, return the number of **palindromic substrings** in it. A string is a **palindrome** when it reads the same backward as forward. A **substring** is a contiguous sequence of characters within the string. ### Examples ```js countSubstrings("abc"); // 3 // Explanation: Three palindromic strings: "a", "b", "c". countSubstrings("aaa"); // 6 // Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". countSubstrings("racecar"); // 10 ``` ### Constraints - `1 <= s.length <= 1000` - `s` consists of lowercase English letters.

A **trie** (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: - `Trie()` Initializes the trie object. - `void insert(String word)` Inserts the string `word` into the trie. - `boolean search(String word)` Returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise. - `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise. ### Examples ```js const trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True ``` ### Constraints - `1 <= word.length, prefix.length <= 2000` - `word` and `prefix` consist only of lowercase English letters. - At most `3 * 10^4` calls **in total** will be made to `insert`, `search`, and `startsWith`.

Given an `m x n` integer matrix `matrix`, if an element is `0`, set its entire row and column to `0`'s. You must do it **in place**. ### Examples ```js // Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] // Output: [[1,0,1],[0,0,0],[1,0,1]] // Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] // Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]] ``` ### Constraints - `m == matrix.length` - `n == matrix[0].length` - `1 <= m, n <= 200` - `-2^31 <= matrix[i][j] <= 2^31 - 1`

Given the `head` of a linked list, remove the `n`th node from the end of the list and return its head. ### Examples ```js // Input: head = [1,2,3,4,5], n = 2 // Output: [1,2,3,5] // Input: head = [1], n = 1 // Output: [] // Input: head = [1,2], n = 1 // Output: [1] ``` ### Constraints - The number of nodes in the list is `sz`. - `1 <= sz <= 30` - `0 <= Node.val <= 100` - `1 <= n <= sz`

Given an array of meeting time intervals `intervals` where `intervals[i] = [start_i, end_i]`, return the **minimum number of conference rooms** required. ### Examples ```js minMeetingRooms([[0, 30], [5, 10], [15, 20]]); // 2 // Explanation: We need two rooms: // Room 1: [0, 30] // Room 2: [5, 10], [15, 20] minMeetingRooms([[7, 10], [2, 4]]); // 1 minMeetingRooms([[1, 5], [8, 9], [8, 9]]); // 2 ``` ### Constraints - `1 <= intervals.length <= 10^4` - `0 <= start_i < end_i <= 10^6`

Koko loves to eat bananas. There are `n` piles of bananas, the `i`th pile has `piles[i]` bananas. The guards have gone and will come back in `h` hours. Koko can decide her bananas-per-hour eating speed of `k`. Each hour, she chooses some pile of bananas and eats `k` bananas from that pile. If the pile has less than `k` bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko wants to finish eating all the bananas before the guards come back. Return the **minimum integer** `k` such that she can eat all the bananas within `h` hours. ### Examples ```js minEatingSpeed([3, 6, 7, 11], 8); // 4 // Explanation: At speed 4, Koko can finish in 8 hours minEatingSpeed([30, 11, 23, 4, 20], 5); // 30 minEatingSpeed([30, 11, 23, 4, 20], 6); // 23 ``` ### Constraints - `1 <= piles.length <= 10^4` - `piles.length <= h <= 10^9` - `1 <= piles[i] <= 10^9`

You are given two integer arrays `nums1` and `nums2`, sorted in **non-decreasing order**, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively. **Merge** `nums2` into `nums1` as one sorted array. The final sorted array should not be returned by the function, but instead be **stored inside the array** `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `nums2` has a length of `n`. ### Examples ```js // Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 // Output: [1,2,2,3,5,6] // Input: nums1 = [1], m = 1, nums2 = [], n = 0 // Output: [1] // Input: nums1 = [0], m = 0, nums2 = [1], n = 1 // Output: [1] ``` ### Constraints - `nums1.length == m + n` - `nums2.length == n` - `0 <= m, n <= 200` - `1 <= m + n <= 200` - `-10^9 <= nums1[i], nums2[j] <= 10^9`

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree. ### Examples ```js // Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] // Output: [3,9,20,null,null,15,7] // Input: preorder = [-1], inorder = [-1] // Output: [-1] ``` ### Constraints - `1 <= preorder.length <= 3000` - `inorder.length == preorder.length` - `-3000 <= preorder[i], inorder[i] <= 3000` - `preorder` and `inorder` consist of **unique** values. - Each value of `inorder` also appears in `preorder`. - `preorder` is **guaranteed** to be the preorder traversal of the tree. - `inorder` is **guaranteed** to be the inorder traversal of the tree.

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value. If `target` is not found in the array, return `[-1, -1]`. You must write an algorithm with `O(log n)` runtime complexity. ### Examples ```js searchRange([5, 7, 7, 8, 8, 10], 8); // [3, 4] searchRange([5, 7, 7, 8, 8, 10], 6); // [-1, -1] searchRange([], 0); // [-1, -1] searchRange([1], 1); // [0, 0] ``` ### Constraints - `0 <= nums.length <= 10^5` - `-10^9 <= nums[i] <= 10^9` - `nums` is a non-decreasing array. - `-10^9 <= target <= 10^9`

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `bi` first if you want to take course `ai`. - For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`. Return *the ordering of courses you should take to finish all courses*. If there are many valid answers, return **any** of them. If it is impossible to finish all courses, return **an empty array**. ### Examples ```js findOrder(2, [[1,0]]); // [0,1] // Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]. findOrder(4, [[1,0],[2,0],[3,1],[3,2]]); // [0,2,1,3] or [0,1,2,3] findOrder(1, []); // [0] ``` ### Constraints - `1 <= numCourses <= 2000` - `0 <= prerequisites.length <= numCourses * (numCourses - 1)` - `prerequisites[i].length == 2` - `0 <= ai, bi < numCourses` - `ai != bi` - All the pairs `[ai, bi]` are **distinct**.

You are given an integer array `nums`. You are initially positioned at the array's **first index**, and each element in the array represents your maximum jump length at that position. Return `true` *if you can reach the last index, or* `false` *otherwise*. ### Examples ```js canJump([2, 3, 1, 1, 4]); // true // Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. canJump([3, 2, 1, 0, 4]); // false // Explanation: You will always arrive at index 3. Its maximum jump length is 0, which makes it impossible to reach the last index. canJump([0]); // true ``` ### Constraints - `1 <= nums.length <= 10^4` - `0 <= nums[i] <= 10^5`

Given two strings `s` and `t` of lengths `m` and `n` respectively, return the **minimum window substring** of `s` such that every character in `t` (including duplicates) is included in the window. If there is no such substring, return the empty string `""`. The testcases will be generated such that the answer is **unique**. ### Examples ```js minWindow("ADOBECODEBANC", "ABC"); // "BANC" // Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. minWindow("a", "a"); // "a" minWindow("a", "aa"); // "" // Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string. ``` ### Constraints - `m == s.length` - `n == t.length` - `1 <= m, n <= 10^5` - `s` and `t` consist of uppercase and lowercase English letters.

A **permutation** of an array of integers is an arrangement of its members into a sequence or linear order. - For example, for `arr = [1,2,3]`, the following are all the permutations of `arr`: `[1,2,3]`, `[1,3,2]`, `[2,1,3]`, `[2,3,1]`, `[3,1,2]`, `[3,2,1]`. The **next permutation** of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the **next permutation** of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). Given an array of integers `nums`, find the next permutation of `nums`. The replacement must be **in place** and use only constant extra memory. ### Examples ```js // Input: nums = [1,2,3] // Output: [1,3,2] // Input: nums = [3,2,1] // Output: [1,2,3] // Input: nums = [1,1,5] // Output: [1,5,1] ``` ### Constraints - `1 <= nums.length <= 100` - `0 <= nums[i] <= 100`

You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return *the max sliding window*. ### Examples ```js maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3); // [3,3,5,5,6,7] // Explanation: // Window position Max // --------------- ----- // [1 3 -1] -3 5 3 6 7 3 // 1 [3 -1 -3] 5 3 6 7 3 // 1 3 [-1 -3 5] 3 6 7 5 // 1 3 -1 [-3 5 3] 6 7 5 // 1 3 -1 -3 [5 3 6] 7 6 // 1 3 -1 -3 5 [3 6 7] 7 maxSlidingWindow([1], 1); // [1] ``` ### Constraints - `1 <= nums.length <= 10^5` - `-10^4 <= nums[i] <= 10^4` - `1 <= k <= nums.length`

You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists in a **sorted order**. The list should be made by splicing together the nodes of the first two lists. Return *the head of the merged linked list*. ### Examples ```js // Input: list1 = [1,2,4], list2 = [1,3,4] // Output: [1,1,2,3,4,4] // Input: list1 = [], list2 = [] // Output: [] // Input: list1 = [], list2 = [0] // Output: [0] ``` ### Constraints - The number of nodes in both lists is in the range `[0, 50]`. - `-100 <= Node.val <= 100` - Both `list1` and `list2` are sorted in **non-decreasing** order.

A phrase is a **palindrome** if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string `s`, return `true` *if it is a **palindrome**, or* `false` *otherwise*. ### Examples ```js isPalindrome("A man, a plan, a canal: Panama"); // true // Explanation: "amanaplanacanalpanama" is a palindrome. isPalindrome("race a car"); // false // Explanation: "raceacar" is not a palindrome. isPalindrome(" "); // true // Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome. ``` ### Constraints - `1 <= s.length <= 2 * 10^5` - `s` consists only of printable ASCII characters.

Given an integer array `nums` sorted in **non-decreasing order**, remove the duplicates **in-place** such that each unique element appears only **once**. The **relative order** of the elements should be kept the **same**. Then return *the number of unique elements in* `nums`. Consider the number of unique elements of `nums` to be `k`, to get accepted, you need to do the following things: - Change the array `nums` such that the first `k` elements of `nums` contain the unique elements in the order they were present in `nums` initially. The remaining elements of `nums` are not important as well as the size of `nums`. - Return `k`. ### Examples ```js removeDuplicates([1,1,2]); // 2, nums = [1,2,_] // Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. removeDuplicates([0,0,1,1,1,2,2,3,3,4]); // 5, nums = [0,1,2,3,4,_,_,_,_,_] ``` ### Constraints - `1 <= nums.length <= 3 * 10^4` - `-100 <= nums[i] <= 100` - `nums` is sorted in **non-decreasing** order.

A **peak element** is an element that is strictly greater than its neighbors. Given a **0-indexed** integer array `nums`, find a peak element, and return its index. If the array contains multiple peaks, return the index to **any of the peaks**. You may imagine that `nums[-1] = nums[n] = -∞`. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in `O(log n)` time. ### Examples ```js findPeakElement([1,2,3,1]); // 2 // Explanation: 3 is a peak element and your function should return the index number 2. findPeakElement([1,2,1,3,5,6,4]); // 5 // Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6. ``` ### Constraints - `1 <= nums.length <= 1000` - `-2^31 <= nums[i] <= 2^31 - 1` - For all valid `i`, `nums[i] != nums[i + 1]`

Given two strings `text1` and `text2`, return *the length of their longest **common subsequence***. If there is no common subsequence, return `0`. A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. - For example, `"ace"` is a subsequence of `"abcde"`. A **common subsequence** of two strings is a subsequence that is common to both strings. ### Examples ```js longestCommonSubsequence("abcde", "ace"); // 3 // Explanation: The longest common subsequence is "ace" and its length is 3. longestCommonSubsequence("abc", "abc"); // 3 // Explanation: The longest common subsequence is "abc" and its length is 3. longestCommonSubsequence("abc", "def"); // 0 // Explanation: There is no such common subsequence, so the result is 0. ``` ### Constraints - `1 <= text1.length, text2.length <= 1000` - `text1` and `text2` consist of only lowercase English characters.

Given a string `s`, rearrange the characters of `s` so that any two adjacent characters are not the same. Return *any possible rearrangement of* `s` *or return* `""` *if not possible*. ### Examples ```js reorganizeString("aab"); // "aba" reorganizeString("aaab"); // "" // Explanation: It is not possible to rearrange the string. reorganizeString("vvvlo"); // "vlvov" ``` ### Constraints - `1 <= s.length <= 500` - `s` consists of lowercase English letters.

Given an array of characters `chars`, compress it using the following algorithm: Begin with an empty string `s`. For each group of **consecutive repeating characters** in `chars`: - If the group's length is `1`, append the character to `s`. - Otherwise, append the character followed by the group's length. The compressed string `s` **should not be returned separately**, but instead, be stored **in the input character array `chars`**. Note that group lengths that are `10` or longer will be split into multiple characters in `chars`. After you are done **modifying the input array**, return *the new length of the array*. You must write an algorithm that uses only constant extra space. ### Examples ```js compress(["a","a","b","b","c","c","c"]); // 6, chars = ["a","2","b","2","c","3"] // Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3". compress(["a"]); // 1, chars = ["a"] // Explanation: The only group is "a", which remains uncompressed since it's a single character. compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"]); // 4, chars = ["a","b","1","2"] // Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12". ``` ### Constraints - `1 <= chars.length <= 2000` - `chars[i]` is a lowercase English letter, uppercase English letter, digit, or symbol.

Given an array `nums` with `n` objects colored red, white, or blue, sort them **in-place** so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function. ### Examples ```js // Input: nums = [2,0,2,1,1,0] // Output: [0,0,1,1,2,2] // Input: nums = [2,0,1] // Output: [0,1,2] ``` ### Constraints - `n == nums.length` - `1 <= n <= 300` - `nums[i]` is either `0`, `1`, or `2`.

Given the `root` of a binary tree, return *the level order traversal of its nodes' values*. (i.e., from left to right, level by level). ### Examples ```js // Input: root = [3,9,20,null,null,15,7] // Output: [[3],[9,20],[15,7]] // Input: root = [1] // Output: [[1]] // Input: root = [] // Output: [] ``` ### Constraints - The number of nodes in the tree is in the range `[0, 2000]`. - `-1000 <= Node.val <= 1000`

Given an integer array `nums`, return `true` if any value appears **at least twice** in the array, and return `false` if every element is distinct. ### Examples ```js containsDuplicate([1,2,3,1]); // true containsDuplicate([1,2,3,4]); // false containsDuplicate([1,1,1,3,3,4,3,2,4,2]); // true ``` ### Constraints - `1 <= nums.length <= 10^5` - `-10^9 <= nums[i] <= 10^9`

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the `MinStack` class: - `MinStack()` initializes the stack object. - `void push(int val)` pushes the element `val` onto the stack. - `void pop()` removes the element on the top of the stack. - `int top()` gets the top element of the stack. - `int getMin()` retrieves the minimum element in the stack. You must implement a solution with `O(1)` time complexity for each function. ### Examples ```js const minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2 ``` ### Constraints - `-2^31 <= val <= 2^31 - 1` - Methods `pop`, `top` and `getMin` operations will always be called on **non-empty** stacks. - At most `3 * 10^4` calls will be made to `push`, `pop`, `top`, and `getMin`.

Given an integer array `nums` of **unique** elements, return *all possible subsets (the power set)*. The solution set **must not** contain duplicate subsets. Return the solution in **any order**. ### Examples ```js subsets([1,2,3]); // [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] subsets([0]); // [[],[0]] ``` ### Constraints - `1 <= nums.length <= 10` - `-10 <= nums[i] <= 10` - All the numbers of `nums` are **unique**.