2022-01-21
134. Gas Station

Topic: Array, Greedy
Difficulty: Medium

Problem:
There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th station to its next (i + 1)^th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

• gas.length == n
• cost.length == n
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

2022-01-22
1510. Stone Game IV

Topic: Math, Dynamic Programming, Game Theory
Difficulty: Hard

Problem:
Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Constraints:

• 1 <= n <= 10^5

2022-01-23
1291. Sequential Digits

Topic: Enumeration
Difficulty: Medium

Problem:
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints:

• 10 <= low <= high <= 10^9

2022-01-24
520. Detect Capital

Topic: String
Difficulty: Easy

Problem:
We define the usage of capitals in a word to be right when one of the following cases holds:

• All letters in this word are capitals, like "USA".
• All letters in this word are not capitals, like "leetcode".
• Only the first letter in this word is capital, like "Google".

Given a string word, return true if the usage of capitals in it is right.

Example 1:

Input: word = "USA"
Output: true

Example 2:

Input: word = "FlaG"
Output: false

Constraints:

• 1 <= word.length <= 100
• word consists of lowercase and uppercase English letters.

2022-01-25
941. Valid Mountain Array

Topic: Array
Difficulty: Easy

Problem:
Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Image: https://assets.leetcode.com/uploads/2019/10/20/hint_valid_mountain_array.png

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

2022-01-26
1305. All Elements in Two Binary Search Trees

Topic: Tree, Depth-First Search, Binary Search Tree, Sorting, Binary Tree
Difficulty: Medium

Problem:
Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Image: https://assets.leetcode.com/uploads/2019/12/18/q2-e1.png

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Image: https://assets.leetcode.com/uploads/2019/12/18/q2-e5-.png

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

• The number of nodes in each tree is in the range [0, 5000].
• -10^5 <= Node.val <= 10^5

2022-01-27
421. Maximum XOR of Two Numbers in an Array

Topic: Array, Hash Table, Bit Manipulation, Trie
Difficulty: Medium

Problem:
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

• 1 <= nums.length <= 2 * 10^5
• 0 <= nums[i] <= 2^31 - 1

2022-01-28
211. Design Add and Search Words Data Structure

Topic: String, Depth-First Search, Design, Trie
Difficulty: Medium

Problem:
Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

2022-01-29
84. Largest Rectangle in Histogram

Topic: Array, Stack, Monotonic Stack
Difficulty: Hard

Problem:
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg

Input: heights = [2,4]
Output: 4

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

2022-01-30
189. Rotate Array

Topic: Array, Math, Two Pointers
Difficulty: Medium

Problem:
Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

2022-01-31
1672. Richest Customer Wealth

Topic: Array, Matrix
Difficulty: Easy

Problem:
You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the i​​​​​^​​​​​​th​​​​ customer has in the j​​​​​^​​​​​​th​​​​ bank. Return the wealth that the richest customer has.

A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example 1:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

Example 2:

Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation: 
1st customer has wealth = 6
2nd customer has wealth = 10 
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.

Example 3:

Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17

Constraints:

• m == accounts.length
• n == accounts[i].length
• 1 <= m, n <= 50
• 1 <= accounts[i][j] <= 100

2022-02-01
121. Best Time to Buy and Sell Stock

Topic: Array, Dynamic Programming
Difficulty: Easy

Problem:
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.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 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

2022-02-02
438. Find All Anagrams in a String

Topic: Hash Table, String, Sliding Window
Difficulty: Medium

Problem:
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may 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.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters.

2022-02-03
454. 4Sum II

Topic: Array, Hash Table
Difficulty: Medium

Problem:
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Constraints:

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

2022-02-04
525. Contiguous Array

Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium

Problem:
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

2022-02-05
23. Merge k Sorted Lists

Topic: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort
Difficulty: Hard

Problem:
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.

Example 1:

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

Example 2:

Input: lists = []
Output: []

Example 3:

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 won't exceed 10^4.

2022-02-06
80. Remove Duplicates from Sorted Array II

Topic: Array, Two Pointers
Difficulty: Medium

Problem:
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,\_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,\_,\_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

2022-02-07
389. Find the Difference

Topic: Hash Table, String, Bit Manipulation, Sorting
Difficulty: Easy

Problem:
You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

2022-02-08
258. Add Digits

Topic: Math, Simulation, Number Theory
Difficulty: Easy

Problem:
Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

Input: num = 0
Output: 0

Constraints:

• 0 <= num <= 2^31 - 1

Follow up: Could you do it without any loop/recursion in O(1) runtime?

2022-02-09
532. K-diff Pairs in an Array

Topic: Array, Hash Table, Two Pointers, Binary Search, Sorting
Difficulty: Medium

Problem:
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

• 0 <= i < j < nums.length
• |nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

Example 1:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Constraints:

• 1 <= nums.length <= 10^4
• -10^7 <= nums[i] <= 10^7
• 0 <= k <= 10^7

2022-02-10
560. Subarray Sum Equals K

Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium

Problem:
Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7