2024-03-16
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.

2024-03-17
57. Insert Interval

Topic: Array
Difficulty: Medium

Problem:
You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i^th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^5
• intervals is sorted by start_i in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10^5

2024-03-18
452. Minimum Number of Arrows to Burst Balloons

Topic: Array, Greedy, Sorting
Difficulty: Medium

Problem:
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

• 1 <= points.length <= 10^5
• points[i].length == 2
• -2^31 <= x_start < x_end <= 2^31 - 1

2024-03-19
621. Task Scheduler

Topic: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting
Difficulty: Medium

Problem:
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

​Return the minimum number of intervals required to complete all tasks.

Example 1:

Input: tasks = "A","A","A","B","B","B", n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3^rd interval, neither A nor B can be done, so you idle. By the 4^th cycle, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = "A","C","A","B","D","B", n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = "A","A","A", "B","B","B", n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

2024-03-20
1669. Merge In Between Linked Lists

Topic: Linked List
Difficulty: Medium

Problem:
You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the a^th node to the b^th node, and put list2 in their place.

The blue edges and nodes in the following figure indicate the result:

Image: https://assets.leetcode.com/uploads/2020/11/05/fig1.png

Build the result list and return its head.

Example 1:

Image: https://assets.leetcode.com/uploads/2024/03/01/ll.png

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Example 2:

Image: https://assets.leetcode.com/uploads/2020/11/05/merge_linked_list_ex2.png

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints:

• 3 <= list1.length <= 10^4
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 10^4

2024-03-21
206. Reverse Linked List

Topic: Linked List, Recursion
Difficulty: Easy

Problem:
Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Image: https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

2024-03-22
234. Palindrome Linked List

Topic: Linked List, Two Pointers, Stack, Recursion
Difficulty: Easy

Problem:
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg

Input: head = [1,2,2,1]
Output: true

Example 2:

Image: https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg

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

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

2024-03-23
143. Reorder List

Topic: Linked List, Two Pointers, Stack, Recursion
Difficulty: Medium

Problem:
You are given the head of a singly linked-list. The list can be represented as:

L_0 → L_1 → … → L_n - 1 → L_n

Reorder the list to be on the following form:

L_0 → L_n → L_1 → L_n - 1 → L_2 → L_n - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Image: https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000

2024-03-24
287. Find the Duplicate Number

Topic: Array, Two Pointers, Binary Search, Bit Manipulation
Difficulty: Medium

Problem:
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses 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

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

2024-03-25
442. Find All Duplicates in an Array

Topic: Array, Hash Table
Difficulty: Medium

Problem:
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n)time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

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

Example 3:

Input: nums = [1]
Output: []

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

2024-03-26
41. First Missing Positive

Topic: Array, Hash Table
Difficulty: Hard

Problem:
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

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

2024-03-27
713. Subarray Product Less Than K

Topic: Array, Sliding Window
Difficulty: Medium

Problem:
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

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

Constraints:

• 1 <= nums.length <= 3 * 10^4
• 1 <= nums[i] <= 1000
• 0 <= k <= 10^6

2024-03-28
2958. Length of Longest Subarray With at Most K Frequency

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

Problem:
You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.

Example 3:

Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
It can be shown that there are no good subarrays with length more than 4.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= nums.length

2024-03-29
2962. Count Subarrays Where Max Element Appears at Least K Times

Topic: Array, Sliding Window
Difficulty: Medium

Problem:
You are given an integer array nums and a positive integer k.

Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,3,2,3,3], k = 2
Output: 6
Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].

Example 2:

Input: nums = [1,4,2,1], k = 3
Output: 0
Explanation: No subarray contains the element 4 at least 3 times.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= k <= 10^5

2024-03-30
992. Subarrays with K Different Integers

Topic: Array, Hash Table, Sliding Window, Counting
Difficulty: Hard

Problem:
Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

• For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

Example 2:

Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

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

2024-03-31
2444. Count Subarrays With Fixed Bounds

Topic: Array, Queue, Sliding Window, Monotonic Queue
Difficulty: Hard

Problem:
You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i], minK, maxK <= 10^6

2024-04-01
58. Length of Last Word

Topic: String
Difficulty: Easy

Problem:
Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

Constraints:

• 1 <= s.length <= 10^4
• s consists of only English letters and spaces ' '.
• There will be at least one word in s.

2024-04-02
205. Isomorphic Strings

Topic: Hash Table, String
Difficulty: Easy

Problem:
Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s and t consist of any valid ascii character.

2024-04-03
79. Word Search

Topic: Array, String, Backtracking, Matrix
Difficulty: Medium

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

Example 1:

Image: https://assets.leetcode.com/uploads/2020/11/04/word2.jpg

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Image: https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Image: https://assets.leetcode.com/uploads/2020/10/15/word3.jpg

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: 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.

Follow up: Could you use search pruning to make your solution faster with a larger board?

2024-04-04
1614. Maximum Nesting Depth of the Parentheses

Topic: String, Stack
Difficulty: Easy

Problem:
A string is a valid parentheses string (denoted VPS) if it meets one of the following:

• It is an empty string "", or a single character not equal to "(" or ")",
• It can be written as AB (A concatenated with B), where A and B are VPS's, or
• It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

• depth("") = 0
• depth(C) = 0, where C is a string with a single character not equal to "(" or ")".
• depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's.
• depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"
Output: 3

Constraints:

• 1 <= s.length <= 100
• s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
• It is guaranteed that parentheses expression s is a VPS.