Neetcode 150

Question 1

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.

Answer 1

HashSet and Intelligent Sequence Building

Question 2

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]

Answer 2

Precompute Left and Right Product Lists

Question 3

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"]]

Answer 3

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?

Question 4

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].

Answer 4

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.

Question 5

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]

Answer 5

Quickselect

Question 6

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].

Answer 6

Two Pointer Approach: Walk Inwards

Question 7

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.

Answer 7

Two Pointer Approach: Walk Inwards

Question 8

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

Answer 8

Stack: Push Open Parenthesis, Pop Closed Parenthesis

Question 9

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

Answer 9

Approach 1: Node(val, min)
Approach 2: Val Stack and Min Stack

Question 10

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

Answer 10

Stack
1. Push Numbers
2. Stop at Symbole
3. Pop 2 numbers
4. Perform Operation
5. Push Answer on Stack

Question 11

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.

Answer 11

Monotonic Stack

Question 12

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]

Answer 12

Monotonic Stack

Question 13

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.

Answer 13

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.

Question 14

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

Answer 14

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

Question 15

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 rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

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.

Answer 15

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]

Question 16

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

Answer 16

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.

Question 17

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

Answer 17

Binary Search: Indexes

• left, right = 0, (m * n )- 1
• row_idx = idx // len(col)
• col_idx = idx % len(col)

Question 18

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 * 104
• s consists of English letters, digits, symbols and spaces.

Answer 18

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++)
• Recalculate max window size (max(max_window, len(window)))

Question 19

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.

Answer 19

Sliding Window: Binary Search Fixed-Sized Windows (O(nlogn)) or Dynamically Sized Approach O(n)

1. Brute Force
   
   • Search Space Table (Index | Window Size)
   • Valid v.s. Invalid Windows
   • Subset and Superset Redundancies
2. Binary Search Fixed-Window Size
   
   • Flip Search Space Table (Window Size | Index).
   • Subset Redundancy allows for Binary Search Window Sizes
3. Dynamically Sized Window
   
   • Go back to Search Space Table (Index | Window Size)
   • window_size = 1
   • window_start_idx = 0
   • window_size++ until invalid window (Superset Redundancy)
   • window_start_idx++ until valid window.
   • Stop when window_start_idx + window_size > len(s)

Question 20

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

Answer 20

Sliding Window

1. Build a frequency map for s1.
2. Define a sliding window of size len(s2) at the start of s2.
3. Build window frequency map for the letters within this window.
4. Slide the window 1 position at a time through s2 while 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.

Question 21

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?

Answer 21

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_head
~~~

https://leetcode.com/problems/reverse-linked-list/

Question 22

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?

Answer 22

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.next

Recursive 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 list2
~~~

Time Complexity: O(len(list1) + len(list2))

Question 23

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?

Answer 23

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

Question 24

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.

Answer 24

One Pass: Global Minimum:

1. Set max_profit = 0
2. Set global_min = prices[0]
3. For every price:
   
   • Calculate the profit
   • Update global_min
   • Update max_profit

_Note_: Setting max_profit = 0, ensures if it is impossible to profit, the answer returned will be 0.

Question 25

Problem:

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

Example 1:

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

Example 2:

• Input: head = [1], n = 1
• Output: []

Example 3:

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

Answer 25

Two Pointer:

1. Traverse Linked List so left and right pointers are n nodes apart.
2. left.next = left.next.next

_Note_: This can be tricky implmentation. Use a PREHEAD to make life easier!

Question 26

Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Answer 26

Approach 1: Hash Map
1. In one pass, clone the linked list, but also:

- Store`[hash(original_node), copy_node`] key-value pairs in a hashmap

2. In a second pass: copy_node.random = hashmap[hash(original_node.random)]

Approach 2: Replace Hash Map with Linked List
1. In one pass, clone the original linked list, but also:

- `copy_node.random = original_node.random`
- `original_node.random = copy_node`

2. In a second pass: copy_node.random = copy_node.random.random

_Note_: Be careful of node.random = None!

Question 27

Problem:

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.

Input
- ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output
- [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
- LRUCache 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

Answer 27

Approach: Doubly Linked List
1. Attributes:
- nodes: for constant time lookup
- head: first element in linked list
- tail: last element in linked list
- size: number of nodes in linked list
- capacity: number of nodes limit before eviction
2. \_\_insert_front\_\_: inserts new linked list head
3. \_\_remove\_\_: removes node from linked list
- Remove linked-list head
- Remove linked-list tail
- Remove linked-list mid
4. LRU Logic
- Cache Inserts: node inserted at linked list head
- Cache Updates: move node to linked list head
- Cache Eviction: remove linked-list tail

_Note_: When removing “middle” nodes remember to update prev pointer of next node (mid.next.prev = mid.prev)

Question 28

Problem

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.

Example 1:

• Input: l1 = [2,4,3], l2 = [5,6,4]
• Output: [7,0,8]
• Explanation: 342 + 465 = 807.

Example 2:

• Input: l1 = [0], l2 = [0]
• Output: [0]

Example 3:

• 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.

Answer 28

Elementary Math

def addTwoNumbers(self, l1, l2):
  prehead = ListNode()
  curr = prehead
  carry = 0
  while l1 is not None and l2 is not None:
      total = l1.val + l2.val + carry
      curr.next = ListNode(total % 10)
      curr = curr.next
      carry = total // 10
      l1 = l1.next
      l2 = l2.next
  while l1 is not None:
      total = l1.val + carry
      curr.next = ListNode(total % 10)
      curr = curr.next
      carry = total // 10
      l1 = l1.next
  while l2 is not None:
      total = l2.val + carry
      curr.next = ListNode(total % 10)
      curr = curr.next
      carry = total // 10
      l2 = l2.next
  if carry == 1:
      curr.next = ListNode(carry)
  return prehead.next

Note: Use total // 10 and total % 10 to calculate digit and carry_flag, respectively.

Question 29

Problem

Given an array, timestamps, where all timestamp[i] are strictly increasing, and a target, timestamp, find the greatest timestamp[i] that is less than or equal to the target timestamp.

Answer 29

Binary Search

Keep track of a max_timestamp which is guarenteed to be less than or equal to target if the Binary Search fails to find the target timestamp.

Question 30

Problem

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.

Answer 30

Approach: Top-Down

def maxDepth(root, depth=0):
  if not root:
    return depth
    return max(
      maxDepth(root.left, depth + 1),
      maxDepth(root.right, depth + 1)
    )

Approach: Bottom-Up

def maxDepth(self, root):
  if not root:
    return 0
  return max(
    maxDepth(root.left),
    maxDepth(root.right)
  ) + 1

Question 31

Problem

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

• Input: root = [1,2,3,4,5]
• Output: 3
• Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

• Input: root = [1,2]
• Output: 1

Answer 31

Approach: Bottom-Up

The longest path will be between 2 _leaf_ nodes.

In order to avoid overlapping longest paths in a Top-Down approach, compare heights starting from subtrees first (Bottom-Up)

def diameterOfBinaryTree(root):
  max_list = [0]
  diameterOfBinaryTreeHelper(root, max_list)
  return max_list[0]
def diameterOfBinaryTreeHelper(root, mx):
  if not root:
    return 0
  mxl = diameterOfBinaryTreeHelper(root.left, mx)
  mxr = diameterOfBinaryTreeHelper(root.right, mx)
  mx[0] = max(mx[0], mxl + mxr)
  return max(mxl, mxr) + 1

Question 32

Problem

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Answer 32

Approach: Top-Down
~~~
def isBalanced(root):
return isBalancedHelper(root)[0]
def isBalancedHelper(root, depth=0):
if not root:
return True, depth
l_balanced, l_depth = self.isBalancedHelper(root.left, depth + 1)
r_balanced, r_depth = self.isBalancedHelper(root.right, depth + 1)
if not l_balanced or not r_balanced:
return False, depth
if abs(l_depth - r_depth) > 1:
return False, depth
return True, max(l_depth, r_depth)
~~~

Approach: Bottom-Up

def isBalanced(root):
  return isBalancedHelper(root)[0]
def isBalancedHelper(root) -> bool:
  if not root:
    return True, 0
  l_balanced, l_height = isBalancedHelper(root.left)
  if not l_balanced:
    return False, -1
  r_balanced, r_height = isBalancedHelper(root.right)
  if not r_balanced:
    return False, -1
  if abs(l_height - r_height) > 1:
    return False, -1
  return True, max(l_height, r_height) + 1

Question 33

Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Answer 33

Approach: Recursion

def isSameTree(p, q):
  if not p and not q:
    return True
  if not p or not q:
    return False
  if p.val != q.val:
    return False
  return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Question 34

Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Answer 34

Approach: Brute Force
1. Create a function, isSameTree(root, subRoot)
2. Check every node in tree if subTree is the same:
- isSameTree(root.left, subRoot)
- isSameTree(root.right, subRoot)

Approach 2: Create a Merkle Tree
1. Create a Merkle Tree for root
2. Create a Merkle Tree for subRoot
3. Compare every node’s hash in tree against subRoot

Question 35

Problem

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).

The output must be an array of arrays, where each sub-array represents a level of a tree.

Answer 35

Approach: Queue of Queues
1. Initialize a queue
2. Initialize a sub_queue
3. Add root to sub_queue
4. While sub_queue in queue:
- Dequeue sub_queue
- Initialize a new_sub_queue
- FOR EACH node in sub_queue:
- Add children to new_sub_queue

Approach: Count Levels

def levelOrder(root):
  if not root:
    return
  q = collections.deque()
  q.append(root)
  levels = []
  while q:
    size = len(q)
    level = []
    for i in range(size):
    n = q.popleft()
    level.append(n.val)
    if n.left:
      q.append(n.left)
    if n.right:
      q.append(n.right)
    levels.append(level)
  return levels

Question 36

Problem

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Answer 36

Approach: Last Node of Each Level

Question 37

Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

Answer 37

Approach:
~~~
def lowestCommonAncestor(root, p, q):
while root:
if p.val > root.val and q.val > root.val:
root = root.right
elif p.val < root.val and q.val < root.val:
root = root.left
else:
return root
~~~

Question 38

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 runs in O(n), but can use extra space.

Example 1:

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

Example 2:

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

Answer 38

Bucket Sort

1. Create a FrequencyMap(Key=Symbol, Value=Frequency)
2. Reverse Key-Value pairs in FrequencyMap to FrequencyMap(Key=Frequency, Value=Symbol)
3. Iterate backwards through range of frequencies (0 to len(input)) and retrieve the top k elements

Note: The range of frequencies for any symbol is restricted to 0 to len(input).

Slight Optmization: The reversed FrequencyMap can be stored in a list instead of another dictionary.

Question 39

Problem

Given a binary tree root, a node X in the tree is named “good” if in the path from root to X there are no nodes with a value greater than X.

Return the number of “good” nodes in the binary tree.

Follow-up: Can you do this with depth-first search and breadth-first search?

Answer 39

Top-Down: Max Node in Path

def \_\_init\_\_(self):
  self.count = 0
def goodNodes(self, root):
  self.goodNodesHelper(root, root.val)
  return self.count
def goodNodesHelper(self, root, mx):
  if not root:
    return
  mx = max(mx, root.val)
  self.goodNodesHelper(root.left, mx)
  if root.val >= mx:
    self.count += 1
  self.goodNodesHelper(root.right, mx)

Note: Counting “good” nodes can use preorder, inorder, postorder traversals

Question 40

Problem

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.

Answer 40

Approach: In-Order Traversal

The in-order traversal of a valid binary search tree will strictly increasing, otherwise the binary search tree is invalid.

def \_\_init\_\_(self):
  self.prev = float('-inf')

def isValidBST(self, root):
  if not root:
    return True
  l_valid = self.isValidBST(root.left)
  if root.val <= self.prev:
    return False
  self.prev = root.val
  return l_valid and self.isValidBST(root.right)

Question 41

Problem

Given the root of a binary search tree, and an integer k, return the k-th smallest value (1-indexed) of all the values of the nodes in the tree.

Answer 41

Approach: In-Order Traversal

def kthSmallest(root, k):
  k = [k]
  ans = [root.val]
  self.kthSmallestHelper(root, k, ans)
  return ans[0]

def kthSmallestHelper(root, k, ans):
  if not root:
    return
  self.kthSmallestHelper(root.left, k, ans)
  k[0] -= 1
  if k[0] == 0:
    ans[0] = root.val
    return
    self.kthSmallestHelper(root.right, k, ans)

Question 42

Problem

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 root of the binary tree.

Example Input:
- preorder = [3,9,20,15,7]
- inorder = [9,3,15,20,7]

Answer 42

Space Complexity O(n)
Time Complexity O(n)

Question 43

Problem

Given a sorted 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.

Example 1:

• Input: nums = [-1,0,1,2,-1,-4]
• Output: [[-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.
  - nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
  - The distinct triplets are [-1,0,1] and [-1,-1,2].
  - Notice that the order of the output and the order of the triplets does not matter.

Example 2:

• Input: nums = [0,1,1]
• Output: []
• Explanation: The only possible triplet does not sum up to 0.

Example 3:

• Input: nums = [0,0,0]
• Output: [[0,0,0]]
• Explanation: The only possible triplet sums up to 0.

Answer 43

Approach: Two Sum II (Sorted) Two Pointer Walk Inwards

1. two_sum optimizations
- Normal Two Sum II (Sorted), except search for multiple answers

2. threeSum optimizations:
- Skip duplicate terms (when prev_val == curr_val)
- Return immediately upon positive number, since it is impossible for the sum of two greater numbers to be smaller

def two_sum(left, right, target, nums, ans):
  while left < right:
    total = nums[left] + nums[right]
    if total > target:
      right -= 1
    elif total < target:
      left += 1
    else:
      ans.add(tuple(sorted((nums[left], nums[right], -target))))
      # Continue to search for MULTIPLE solutions
      left += 1
      right -= 1

def threeSum(nums):
  nums.sort()
  pdx, idx, size, ans = 0, 0, len(nums), set()

  two_sum(idx + 1, size - 1, -nums[idx], nums, ans)
  pdx = idx
  idx += 1

  while idx < size:
    if nums[idx] == nums[pdx]:
      idx += 1
      continue  # Skip duplicates
    if nums[idx] > 0:
      idx += 1
      continue  # Sum of two greater numbers cannot be smaller
    two_sum(idx + 1, size - 1, -nums[idx], nums, ans)
    pdx = idx
    idx += 1
  return ans

Question 44

Problem

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.

Your are not allowed to modify the original input array nums.

Example 1:

• Input: nums = [-1,0,1,2,-1,-4]
• Output: [[-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.
  - nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
  - The distinct triplets are [-1,0,1] and [-1,-1,2].
  - Notice that the order of the output and the order of the triplets does not matter.

Example 2:

• Input: nums = [0,1,1]
• Output: []
• Explanation: The only possible triplet does not sum up to 0.

Example 3:

• Input: nums = [0,0,0]
• Output: [[0,0,0]]
• Explanation: The only possible triplet sums up to 0.

Answer 44

Approach: Two Sum (Unsorted) HashMap

1. Skip Duplicates in Outer-Loop Optimization

The possible generated Tuples are…

• Iteration 1. (nums[idx], TwoSum(nums[idx+1:]))
• Iteration 2. (nums[idx+1], TwoSum(nums[idx+2:]))
• Iteration 3. (nums[idx+2], TwoSum(nums[idx+3:]))
• ...

Notice…

• nums[idx+3:] is a subset of nums[idx+2:]
• nums[idx+2:] is a subset of nums[idx+1:]

Thus, given a duplicate number in the outer-loop, where nums[idx+2] == nums[idx], it is impossible for Iteration 3 to generate a tuple not generated in Iteration 1.

2. Skip Elements Seen in Outer-Loop in Inner-loop Optimization

For the sake of argument, start with the following example:

• A = [1, 2, 3, 4], i = 1, j =2
• Tuple: A[i] + A[j] + ? = 0

If j is allowed to iterate over A[0:i], at some point:

• A = [1, 2, 3, 4], j_prime = 1, i_prime = 2
• Tuple: A[i_prime] + A[j_prime] + ? = 0

So, if j is allowed to iterate over A[0:i], a duplicate tuple will be encountered.
- i_prime = j
- j_prime = i
- A[i_prime] + A[j_prime] + ? = A[i] + A[j] + ?

def threeSum(self, nums):
  size = len(nums)
  ans, avoid_duplicates = set(), set()
  seen = {}
  for idx in range(size):
    if nums[idx] not in avoid_duplicates:
      target = -nums[idx]
      for jdx in range(idx + 1, size):
        complement = target - nums[jdx]
        if complement in seen and seen[complement] == idx:
          if nums[jdx] not in avoid_duplicates:  # Not necessary
            ans.add(tuple(sorted((nums[idx], nums[jdx], complement))))
            seen[nums[jdx]] = idx
      avoid_duplicates.add(nums[idx])
  return ans

Question 45

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

• Input: n = 3
• Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

• Input: n = 1
• Output: ["()"]

Answer 45

Approach: Backtracking

1. Base Case
- Ran out of "(" and ")" to place

2. Backtrack Condition(s):
- Not enough "(" placed to append ")"

3. Recursive Step
- Append a "(" or ")"

def generateParenthesis(n):
  def build(o, c, curr):
    if o >= n and o <= c:
      ans.append(curr)
    if o < n:
      build(o + 1, c, curr + '(')
    if o > c:
      build(o, c + 1, curr + ')')
    ans = []
    build(0, 0, '')
    return ans

Question 46

Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer 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]]

Example 3:

• Input: nums = [1]
• Output: [[1]]