Problem
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.
Example:
- Input:
nums = [100,4,200,1,3,2] - Output:
4 - Explanation:
The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
HashSet and Intelligent Sequence Building
Problem
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].
You must write an algorithm that runs in O(n) time and without using the division operation.
Example:
- Input:
nums = [1,2,3,4] - Output:
[24,12,8,6]
Precompute Left and Right Product Lists
Problem
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.
Example:
- Input:
strs = ["eat","tea","tan","ate","nat","bat"]] - Output:
[["bat"],["nat","tan"],["ate","eat","tea"]]
HashMap(K=frozen_set(Anagrams Letters), V=Strings)
Note: frozen_set(Anagrams Letters) only works because there are no duplicates. For handling duplicates, use a Char Frequency Map/Array as Key?
Problem
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.
Example
- Input:
nums = [2,7,11,15], target = 9 - Output:
[0,1] - Explanation:
Because nums[0] + nums[1] == 9, we return [0, 1].
HashMap(K=Number, V=Index)
Note: This can be done in one pass, since all the elements are distinct and an answer must exist. This means eventually a complement will be added to the hashmap.
Problem
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
You must write an algorithm that uses O(1) space and runs in O(n) average time
Example 1:
- Input:
nums = [1,1,1,2,2,3], k = 2 - Output:
[1,2]
Example 2:
- Input:
nums = [1], k = 1 - Output:
[1]
Quickselect
Problem
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example:
- Input:
numbers = [2,7,11,15], target = 9 - Output:
[1,2] - Explanation:
The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Two Pointer Approach: Walk Inwards
Problem
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.
Example:
- Input:
height = [1,8,6,2,5,4,8,3,7] - Output:
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.
Two Pointer Approach: Walk Inwards
Problem
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example
- Input: s = "()"
- Output: true
Stack: Push Open Parenthesis, Pop Closed Parenthesis
Problem
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.
Example
Input:
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
Output:
[null,null,null,null,-3,null,0,-2]
Explanation:
MinStack 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
Approach 1: Node(val, min)
Approach 2: Val Stack and Min Stack
Problem
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
- The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’.
- Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
Example:
- Input:
tokens = ["2","1","+","3","*"] - Output:
9 - Explanation:
((2 + 1) * 3) = 9
Stack
1. Push Numbers
2. Stop at Symbole
3. Pop 2 numbers
4. Perform Operation
5. Push Answer on Stack
Problem
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example:
- Input:
nums1 = [4,1,2], nums2 = [1,3,4,2] - Output:
[-1,3,-1] - Explanation:
The next greater element for each value of nums1 is as follows:4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
Monotonic Stack
Problem
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example:
- Input:
temperatures = [73,74,75,71,69,72,76,73] - Output:
[1,1,4,2,1,1,0,0]
Monotonic Stack
Problem
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
You are given two integer array position and speed, both of length n, where position[i] is the position of the i-th car and speed[i] is the speed of the i-th car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return the number of car fleets that will arrive at the destination.
Example:
- Input:
target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] - Output:
3 - Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12.The car starting at 0 does not catch up to any other car, so it is a fleet by itself.The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.Note that no other cars meet these fleets before the destination, so the answer is 3.
Stack: of Arrival Times
- Think about the relation of the arrival time v.s. starting position
- Sort by position
- Calculate arrival times (sorted by position)
- Iterate through the array backwards and treat like a Monotonic Stack where each “next greatest value” signifies the start of a new fleet.
Problem
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 likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
- Input:
piles = [3,6,7,11], h = 8 - Output:
4
Example 2:
- Input:
piles = [30,11,23,4,20], h = 5 - Output:
30
Example 3:
- Input:
piles = [30,11,23,4,20], h = 6 - Output:
23
Binary Search: Eating speeds from 1 to max(piles)
- Min rate is 1 and max rate is the largest pile
- Figure out total hours, guessed_hours from guessed eating rate
- IF guessed_hours > hours, THEN search for a faster eating rate
- IF guessed_hours <= hours,
- THEN update max_hours closest hours without going over.
- AND THEN keep searching for faster eating rate
Problem
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2]if it was rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
- Input:
nums = [3,4,5,1,2] - Output:
1 - Explanation:
The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
- Input:
nums = [4,5,6,7,0,1,2] - Output:
0 - Explanation:
The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
- Input:
nums = [11,13,15,17] - Output:
11 - Explanation:
The original array was [11,13,15,17] and it was rotated 4 times.
Binary Search Variation: compare guess to the start or end of the array.
- WRAPPED (search right): nums[guess] > nums[end], nums[guess] >= nums[start]
- SHIFTED (search left): nums[guess] <= nums[end], nums[guess] < nums[start]
Problem:
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 possible 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.
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
Example 3:
- Input:
nums = [1], target = 0 - Output:
-1
Binary Search Variation.
Break down into SHIFTED v.s. WRAPPED sequences by comparing guess, target, and start or end of array.
Given an input array [3, 4, 1, 2] the SHIFTED sequence = [1, 2] and the WRAPPED Sequence = [3, 4]
During the binary search we need to figure out where the guess and target is by comparing to the start:
- IF nums[guess] < nums[start] THEN guess is in SHIFTED sequence.
- IF nums[guess] >= nums[start], THEN guess is in WRAPPED sequence.
If the guess and target are in the same shifted or wrapped sequence, proceed with normal binary search. If guess and target are in different sequences, then break binary search rules and move left or right keeping in mind that the wrapped sequence is always to the left of the shifted sequence.
Problem:
You are given an m x n integer matrix matrix with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
Example 1:
- Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output: true
Example 2:
- Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
- Output: false
Binary Search: Indexes
left, right = 0, (m * n )- 1row_idx = idx // len(col)col_idx = idx % len(col)
Problem
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
- Input:
s = "abcabcbb" - Output:
3 - Explanation:
The answer is "abc", with the length of 3.
Example 2:
- Input:
s = "bbbbb" - Output:
1 - Explanation:
The answer is "b", with the length of 1.
Example 3:
- Input:
s = "pwwkew" - Output:
3 - Explanation:
The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.
Sliding Window: Use Two Pointer Sliding Window with Hashset (or ASCII Array)
Key Idea: IF substring(i, j) has a duplicate character where d is the index of that duplicate character, THEN all substrings where left = i to i + N will also contains duplicate characters.
Therefore, stop incrementing right++ and increment left++ past i + N.
Algorithm
- Increase sliding window (
right++) until duplicate character is found - Duplicate character found:
- Drop leading chars (
left++) until the dupe char, in the sliding window, is dropped - Add new duplicate character to end of window (
right++)
- Drop leading chars (
- Recalculate max window size (
max(max_window, len(window)))
Problem
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Follow-up: Describe an O(nlog(n)) approach
Follow-up: Describe an O(n) approach
Example 1:
- Input: s = “ABAB”, k = 2
- Output: 4
- Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.
Example 2:
- Input: s = “AABABBA”, k = 1
- Output: 4
- Explanation:
- Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.
- The substring “BBBB” has the longest repeating letters, which is 4.
- There may exists other ways to achieve this answer too.
Sliding Window: Binary Search Fixed-Sized Windows (O(nlogn)) or Dynamically Sized Approach O(n)
- Brute Force
- Search Space Table (Index | Window Size)
- Valid v.s. Invalid Windows
- Subset and Superset Redundancies
- Binary Search Fixed-Window Size
- Flip Search Space Table (Window Size | Index).
- Subset Redundancy allows for Binary Search Window Sizes
- Dynamically Sized Window
- Go back to Search Space Table (Index | Window Size)
window_size = 1window_start_idx = 0window_size++until invalid window (Superset Redundancy)window_start_idx++until valid window.- Stop when
window_start_idx + window_size > len(s)
Problem
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1’s permutations is the substring of s2.
Example 1:
- Input: s1 = “ab”, s2 = “eidbaooo”
- Output: true
- Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:
- Input: s1 = “ab”, s2 = “eidboaoo”
- Output: false
Sliding Window
- Build a frequency map for
s1. - Define a sliding window of size
len(s2)at the start ofs2. - Build window frequency map for the letters within this window.
- Slide the window 1 position at a time through
s2while updating the window’s frequency map by removing the character leaving the window and adding the character entering the window.
Comments: The tricky part is finding all optimizations:
- Modifying a single window frequency map, instead of rebuilding from scratch every slide.
- Using an ASCII array instead of a hashmap
- Use a number_matches instead of an array for quicker comparisons.
Problem
Given the head of a singly linked list, reverse the list, and return the new head of the reversed list.
Follow-up: Can you do this both iteratively and recursively?
Two Pointers:
~~~
def reverseList(self, head):
if head is None or head.next is None:
return head
prev, curr, after = None, head, head
while curr is not None:
after = after.next
curr.next = prev
prev = curr
curr = after
return prev
~~~
Recursive:
def reverseList(self, head):
if head is None or head.next is None:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_headhttps://leetcode.com/problems/reverse-linked-list/
Problem
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Follow-up: Can you do this both iteratively and recursively?
Iteratic Solution
PREDHEAD! PREDHEAD! PREDHEAD!
def mergeTwoLists(list1, list2):
prehead = new Node()
while list1 is not None and list2 is not None:
if list1.val < list2.val
prehead = list1
list1 = list1.next
else:
prehead = list1
list1 = list1.next
while list1 is not None:
prehead = list1
list1.next = list1
while list2 is not None:
prehead = list2
list2.next = list2
return prehead.nextRecursive Solution:
def mergeTwoLists(list1, list2):
if list1 is None:
return list2
if list2 is None:
return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list1 if list1.val < list2.val else list2Time Complexity: O(len(list1) + len(list2))
Problem
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Follow-up: Can you do this both iteratively and recursively?
Approach 1: Iterative
1. Find middle of the list
2. Split into two linked lists
3. Interweave two linked lists
4. Add middle to end of interweaved linked lists
Approach 2: Recursive 4 pointers
1. Recurse to tail of linked list with a reference to head
- Base Case: if tail.next is None: return head, tail
2. Going up the call stack
- front, back = recursive_call(head, tail.next)
- Stop:
- Odd linked list: front.next is None
- Even linked list: front.next.next is None
- Re-link: front, back, and tail.
- Return after, tail
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.
One Pass: Global Minimum:
- Set
max_profit = 0 - Set
global_min = prices[0] - For every price:
- Calculate the
profit - Update
global_min - Update
max_profit
- Calculate the
_Note_: Setting max_profit = 0, ensures if it is impossible to profit, the answer returned will be 0.
