84.
Largest Rectangle in Histogram
You are given an array of integers heights representing the heights of bars in a histogram,
where each bar has a width of 1 and stands side by side on the x-axis. Determine the area of the
largest rectangle that can be formed entirely within the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed using the bars of height 5 and 6, giving a width of
2 and an area of 10.
Example 2:
Input: heights = [2,4]
Output: 4
79. Word Search
Given an m x n grid of characters board and a string word, determine whether word can be
traced out in the grid. Each letter of the word must come from a cell that is horizontally or
vertically adjacent to the previous one, and the same cell may not be reused within a single
word.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Example 2:
Input: word = "SEE"
Output: true
Example 3:
Input: word = "ABCB"
Output: false
127. Word Ladder
A transformation sequence from word beginWord to word endWord using a dictionary
wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that every adjacent
pair of words differs by exactly one letter, every si is present in wordList, and sk equals
endWord. Note that beginWord itself does not need to appear in wordList. Given beginWord,
endWord, and wordList, return the number of words in the shortest such transformation
sequence, or 0 if no valid sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which
contains 5 words.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: "cog" does not appear in wordList, so no valid sequence exists.
41. First Missing Positive
Given an unsorted integer array nums, return the smallest positive integer that does not appear
in the array. Your algorithm should run in O(n) time and use only constant extra space.
Example 1:
Input: nums = [1,2,0]
Output: 3
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
287. Find the Duplicate Number
You are given an array of integers nums containing n + 1 integers, where each integer lies in
the range [1, n] inclusive. Exactly one number in the array is repeated, possibly more than
once. Find that repeated number without modifying the array and using only constant extra
space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
16. 3Sum Closest
Given an integer array nums of length n and an integer target, find three integers in nums
whose sum is closest to target, and return that sum. You may assume that each input has
exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2 (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
242. Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
88. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, along with
two integers m and n representing the number of elements in nums1 and nums2 respectively.
nums1 has a length of m + n, where the last n elements are set to 0 and should be ignored.
Merge nums2 into nums1 so that the resulting array is sorted in non-decreasing order, stored
inside nums1.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
485. Max Consecutive Ones
Given a binary array nums, return the maximum number of consecutive 1's found in the array.
Example 1:
Input: nums = [1,1,0,1,1,1]
Output: 3
Example 2:
Input: nums = [1,0,1,1,0,1]
Output: 2
63. Unique Paths II
You are given an m x n grid represented by obstacleGrid, in which 1 marks an obstacle and 0
marks an empty cell. Starting at the top-left corner and only able to move down or right,
determine the number of distinct paths to reach the bottom-right corner while avoiding
obstacles.
Example 1:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Example 2:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
3558. Number of Ways to Assign Edge Weights I
There is an undirected tree with n nodes labeled from 1 to n, rooted at node 1, described by a
2D array edges of length n - 1 where edges[i] = [ui, vi] indicates an edge between nodes ui and
vi. Every edge starts with a weight of 0, and each edge must be assigned a weight of either 1 or
2. The cost of a path between two nodes is the sum of the weights of the edges along that path.
Choose any single node x situated at the maximum depth of the tree, and return the number of
ways to assign weights along the path from node 1 to x so that the total cost is odd. Because the
answer can be large, return it modulo 10^9 + 7. Edges that do not lie on the path from node 1
to x are disregarded.
Example 1:
Input: edges = [[1,2]]
Output: 1
Explanation: The single edge (1 -> 2) can be given weight 1 to make the cost odd, so there is
exactly one valid assignment.
Example 2:
Explanation (general case): If the deepest node is reached through a path of k edges, each edge
can independently be 1 or 2, and roughly half of the 2^k combinations yield an odd total cost.
132. Palindrome Partitioning II
Given a string s, partition it so that every substring in the partition is itself a palindrome.
Return the minimum number of cuts required to achieve such a partition.
Example 1:
Input: s = "aab"
Output: 1
Explanation: One cut splits the string into "aa" and "b", both of which are palindromes.
Example 2:
Input: s = "a"
Output: 0
Example 3:
Input: s = "ab"
Output: 1
229. Majority Element II
Given an integer array nums of size n, return all elements that occur more than floor(n / 3)
times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
167. Two Sum II - Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order,
find two numbers that add up to a specific target and return their indices as an array [index1,
index2], where 1 <= index1 < index2 <= [Link]. You may assume exactly one
solution exists, and the same element may not be used twice.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
48. Rotate Image
You are given an n x n 2D matrix representing an image. Rotate the image in place by 90
degrees clockwise, without allocating another matrix for the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
240. Search a 2D Matrix II
Design an efficient algorithm that searches for a target value in an m x n integer matrix. Each
row of the matrix is sorted in ascending order from left to right, and each column is sorted in
ascending order from top to bottom.
Example 1:
Input: matrix with rows sorted left to right and columns sorted top to bottom, target = 5
Output: true
Example 2:
Input: same matrix, target = 20
Output: false
110. Balanced Binary Tree
Given the root of a binary tree, determine whether it is height-balanced, meaning the depths of
the two subtrees of every node never differ by more than one.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
977. Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of
each number, also sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
23. Merge k Sorted Lists
You are given an array of k linked lists, each already sorted in ascending order. Merge all of
the linked lists into a single sorted linked list and return its head.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
25. Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified
list. k is a positive integer, and if the number of remaining nodes is not a multiple of k, the
nodes left over at the end should remain in their original order.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
14. Longest Common Prefix
Write a function that finds the longest common prefix string shared among an array of strings.
If no common prefix exists, return an empty string.
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
3751. Total Waviness of Numbers in Range I
You are given two integers num1 and num2 that describe an inclusive range [num1, num2].
The waviness of a number is defined as the total count of peaks and valleys among its digits,
where a digit is a peak if it is strictly greater than both neighboring digits and a valley if it is
strictly less than both neighboring digits. The first and last digits of a number can never count
as a peak or valley, and any number with fewer than three digits automatically has a waviness
of 0. Return the sum of the waviness values for every number in the range [num1, num2].
Example 1:
Input: num1 = 120, num2 = 130
Output: 3
Explanation: Within the range, 120, 121, and 130 each have a middle digit that forms a single
peak, contributing 1 each, while every other number in the range has a waviness of 0, giving a
total of 3.
Example 2:
Input: num1 = 198, num2 = 202
Output: 3
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray with the largest sum and return that
sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum, 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
94. Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its node values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
881. Boats to Save People
You are given an array people, where people[i] represents the weight of the ith person, and an
integer limit representing the maximum weight capacity of every boat. Each boat can carry at
most two people at the same time, provided their combined weight does not exceed limit.
Return the minimum number of boats required to carry every person across.
Example 1:
Input: people = [1,2], limit = 3
Output: 1
Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
169. Majority Element
Given an array nums of size n, return the majority element, defined as the element that appears
more than n / 2 times. You may assume that a majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
9. Palindrome Number
Given an integer x, return true if x reads the same forward and backward, and false otherwise.
Example 1:
Input: x = 121
Output: true
Example 2:
Input: x = -121
Output: false
Example 3:
Input: x = 10
Output: false
75. Sort Colors
Given an array nums containing n objects colored red, white, or blue and represented by the
integers 0, 1, and 2 respectively, sort the array in place so that objects of the same color are
grouped together and appear in the order red, white, blue.
Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]
236. Lowest Common Ancestor of a Binary Tree
Given the root of a binary tree along with two of its nodes p and q, find their lowest common
ancestor, defined as the deepest node that has both p and q as descendants (a node may be
considered a descendant of itself).
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Example 2:
Input: p = 5, q = 4
Output: 5
49. Group Anagrams
Given an array of strings strs, group the strings that are anagrams of one another together, and
return the groups in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
2196. Create Binary Tree From Descriptions
You are given a 2D integer array descriptions, where each entry [parenti, childi, isLefti]
indicates that parenti is the parent of childi in a binary tree, and isLefti tells you whether childi
is the left child (1) or right child (0) of parenti. Construct the binary tree described by these
edges and return its root. The value of each node equals the node number given in descriptions.
Example 1:
Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: the binary tree rooted at 50, with left child 20 (whose children are 15 and 17) and right
child 80 (whose left child is 19)
344. Reverse String
Write a function that reverses a string. The input string is given as an array of characters s, and
the reversal must be done in place using O(1) extra memory.
Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
752. Open the Lock
A lock has four circular wheels, each showing a digit from 0 to 9, and each wheel can be
rotated one step up or down at a time. The lock starts at the combination "0000". Given a list of
deadends, combinations that must never be reached, and a target combination, return the
minimum number of turns required to reach the target, or -1 if it cannot be reached.
Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
1833. Maximum Ice Cream Bars
You are given an array costs where costs[i] is the price of the ith ice cream bar, along with an
integer coins representing the amount of money you have. Return the maximum number of ice
cream bars you can buy using coins.
Example 1:
Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Example 2:
Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
33. Search in Rotated Sorted Array
An integer array nums, sorted in ascending order with distinct values, has been rotated at an
unknown pivot. Given the rotated array and a target value, return the index of target if it exists,
or -1 otherwise. The algorithm must run in O(log n) time.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
994. Rotting Oranges
You are given an m x n grid where each cell can be 0 (empty), 1 (a fresh orange), or 2 (a rotten
orange). Every minute, any fresh orange that is adjacent to a rotten orange becomes rotten as
well. Return the minimum number of minutes that must pass until no cell contains a fresh
orange, or -1 if that is impossible.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
46. Permutations
Given an array nums of distinct integers, return all the possible permutations of the array, in
any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
10. Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching that supports '.'
and '*', where '.' matches any single character and '*' matches zero or more occurrences of the
preceding element. The match must cover the entire input string, not just part of it.
Example 1:
Input: s = "aa", p = "a"
Output: false
Example 2:
Input: s = "aa", p = "a*"
Output: true
Example 3:
Input: s = "ab", p = ".*"
Output: true
26. Remove Duplicates from Sorted Array
Given an integer array nums sorted in non-decreasing order, remove the duplicates in place so
that each unique element appears only once, keeping the relative order, and return the number
of unique elements.
Example 1:
Input: nums = [1,1,2]
Output: 2, with nums updated to [1,2,_]
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5
97. Interleaving String
Given three strings s1, s2, and s3, determine whether s3 can be formed by interleaving the
characters of s1 and s2 while preserving the relative order of characters from each string.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s3 = "aadbbbaccc"
Output: false
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists, list1 and list2. Merge the two lists into a
single sorted linked list by splicing together the nodes of the two lists, and return the head of
the merged list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]