LC Blind 75

Question 1

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Answer 1

Naive Solution: cycle through list for each element and identify the indices of the target values

Optimal Solution: Create dict with [key, value] as [value, index] and check for target - value as a key. If in the dict, return values, if not then add to the dict

Question 2

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith 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.

Answer 2

Initialize currMin and currMax

Check if current delta with Min is > Max

check if value < min and reset if necessary

Consider Kadane’s Algorithm for max subarray problem in general

Question 3

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Answer 3

Fibonacci Number

Each step can be reached from two places - step (n-1) and step (n-2). To calculate each step’s possible outcomes one must calculate the prior two steps the whole way.

Question 4

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Answer 4

1. Loop through array, check if element in set. Return if true, add if not
2. compare length of array to set of array. Duplicates will result in a reduced size for the set

Question 5

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s, and return the matrix.

You must do it in place.

Answer 5

Optimal Speed Solution using O(m+n) space:

1. Set array for row and for column equal to length of appropriate dimension
2. iterate through whole array checking for zeroes. If detected, set appropriate row and col marker to 0.
3. Run through array again, setting any values that match the row or col 0 markers to be 0.

To make this O(1) space:
use the first row and column of the array as the markers

Question 6

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Answer 6

Sliding Window Technique

1. If s[r] has not been seen, increment the output.
2. If s[r] has been seen, but the value is less than the left marker, increment the output
3. If s[r] has been seen, but the value is greater than the left marker, move the left marker to the index past where it was seen
4. increment/set the index for the right marker in seen

Question 7

Maximum Depth of Binary Tree

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 7

Recursively check each layer, looking for leaf nodes. At leaf nodes return (1).

Anywhere the node splits, return the max of the helper function while adding 1 each layer.

Only edge case is empty tree, return 0.

Question 8

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Answer 8

0. Check base conditions: array fewer than 3 values and compare first two values.
1. Each step, we will iterate the array and rewrite the value with the optimal value at this point in the array. We will compare the previous value with the sum of the current and n-2 values.
2. After one iteration, we can return the final value

Question 9

Reverse a Linked List

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

Answer 9

1. Set base conditions: check for empty node
2. Define required variables: prev and curr to track reverse and forward linked list respectively. Set prev.next to be None.
3. while curr is not empty, set the next values as a temp variable. Then redirect the current node to prev (the reverse node. Then set prev to be curr (the reversed list including the most recent node). Then reset curr to be the next node we had set aside at the beginning.
4. These steps will repeat, reversing the list one step at a time. Return the reversed list (prev).

Question 10

Product of Array Except Self

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Answer 10

The trivial solution to this is to use the division operator, but that is one of the conditions listed. So we will make a two pass solution.

Pass 1: we will fill our output array with the product of each number leading up to that point, but not including that index.

Pass 2: we will do the same, but in reverse. This results in creating an output array that has multiplied all values together and managed to skip the value at each index.

Question 11

Longest Repeating Character Replacement

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.

Answer 11

Declare max length, max count, and count (dict).

Much like longest subsequence, we will be iterating and checking at each iteration if we’re at a new best or not.

First, we will increment the dict entry for the next character of the string.

Then we will check the max count as the max against itself and the count at the current character.

max length will always be k + max count. This is because whatever the max count in a range is, we can add k to that for our max length. If max length is less than k + max count, increment max length (it should never increment by more than one).

If max length did not grow, then we must contract the window from the back, decrement the character at max length distance from the front of the window.

This will repeat and is very similar to Kadane’s algorithm. We will return max length

Question 12

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Answer 12

Pieces to account for:

• Hash table to store needed char frequency (collections.Counter)
• Total characters needed (missing = len(t))
• Start and End initialized to 0
• Iterator i initialized to 0 (to account for left side window)

We will do a sliding window over the enumerate (s, 1)

Each step we will do the following

• Check if the char’s hash is greater than 0. If so, decrement missing by 1 and decrement the character’s hash
• If missing == 0, then all values have been located in the substring.
• If missing == 0, we will start sliding i/left forward until we find the true start of this substring. After we find the true substring, we will proceed with previous steps or increment i

Question 13

Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Answer 13

Dynamic Programming Solution

Begin by initializing the dp array, which is [0] + [amount + 1 for n in amount]. We will be checking the best solution for each value from 1 to amount.

Next, we will start a nested loop. The outer loop holding the coins, the inner loop ranging from (coin, amount). The inner loop will compare to find the min at each step comparing dp[i] and dp[i - coin] + 1. This is because we want whatever is lower of using this coin, and using the coin implies the latter. The former suggests that a previous denomination had a more optimal result and we will use that for now.

We will return the last value of the array IFF it is >= amount. Otherwise return -1.

Question 14

Same Tree

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 14

Recursive Solution:

Each step we want to check that the two tree values being compared are 1. not null, and 2. the same.

If p and q, then we will return the result of the vals of p and q, and the recursive step for left and right.

To account for Null/Null case, we will return p is q after this step to close the recursive step

Question 15

Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Answer 15

We will be recursively stepping through the tree, each time flipping the left and right children and then calling the invert function on the left and right children respectively.

Question 16

Detect Cycle in a Linked List

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Answer 16

The method we will be using is two pointers, one fast and one slow.

First we must check if the head is null and initialize the fast pointer (we will be using the head as the slow pointer).

Then while the fast and fast.next are valid, we will continue to loop through and increment the slow pointer (by one) and fast pointer (by two).

If there is a cycle, the fast pointer will “catch up” to the slow pointer and eventually equal it. If there is no cycle, then we will reach the end of the linked list.

Question 17

Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Answer 17

We will be approaching with iterative DFS approach.

1. First we must check the edge case of an empty graph and return
2. Next we must define the necessary pieces: nodeCopy (initialized instance of Node with empty neighbors), dic ({node: nodeCopy}), and stack (our iteration mechanic).
3. While stack is not empty we will pop values off (neighbor) and then iterate through each neighbor.
4. If we have not seen a neighbor before, we must establish an instance of the node (Node(neighbor.val, [])). This will be neighborCopy
   4a. Then we must set the dic[neighbor] to neighborCopy.
   4b. Next we will append neighborCopy to dic[Node].neighbors
   4c. Last we will append neighbor to stack
5. If we have seen the neighbor before, we will just append dic[neighbor] to dic[node].neighbors
6. return nodeCopy

Question 18

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Answer 18

We will be creating a dynamic programming approach

1. initialize current and max sum variables
2. iterate througheach num in nums from 1 to the end
3. at each step, set the current to the max of the current + num and the num. This will reset the count if any individual num is greater than the highest total before it.
4. set max to the max of current and max
5. return max

Question 19

Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Answer 19

Similar to Maximum Subarray - we will be performing a dynamic programming solution. The added complexity is accounting for polarity flip that negative values cause

1. initialize values for positive and negative products, as well as the answer all to the first value of nums
2. iterate through each values of nums[1:]
3. At each step, we will recalculate the positive and negative products by taking the respective max and min of the newly added pieces (e.g. max(num, posProd * num, negProd * num). These must be assigned to temporary variables at first so that values aren’t corrupted
4. replace the values for the positive and negative products and compare the answer for max
5. return max

Question 20

Find Minimum in Rotated Sorted Array

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.

Answer 20

We will be doing a modified binary search to find the minimum in the array.

1. initialize left and right to the start and end of the array
2. begin a while loop that persists while left < right
3. each loop, we will set mid to be the midpoint of left and right (left + right) // 2.
4. Next we will assess the current state of the binary search. if the nums of midpoint is greater than nums of right, then the minimum is somewhere on the right and we must adjust the left barrier accordingly (left = mid + 1). Otherwise, we must adjust the right barrier (right = mid).
5. In the end, the contents of nums[left] will be the min and we will return that

Question 21

Search in Rotated Sorted Array

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.

Answer 21

We will be doing a modified binary search to find the target element in the array.

1. First we must initialize left and right as 0 and the last index
2. Next we will enter a while loop that persists as long as left <= right.
3. Each iteration of this loop, we will calculate the midpoint between left and right (left + right) // 2 and check if the value of the midpoint is the target and return.
4. Then we will have a two tier if statement that will:
   4a. In the first tier check if the array is rotated left or right. We determine this based on the result of comparing the mid point to the left point (if midpoint greater, left rotated, else right rotated).
   4b. In the second tier we will determine how to set the next window. First we will check if the target is between left and mid or mid and right (depending on step 4a). If so, we decrement/increment the right/left value to adjust the window appropriately.
5. Ultimately, the window will keep adjusting until the value is found (and will be returned), or the value will not exist (and the loop will end and we return -1)

Notes: The premise of this problem is on assessing the direction and narrowing from the 4 possible outcomes (left/right + left/right)

Question 22

Three Sum

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.

Answer 22

We will be doing a modified sliding window technique to solve this problem.

1. First we must sort the array. This is very important because our solution will be O(n*n) and sorting is O(nlogn) and therefore will not impact the speed while allowing us to take a more systematic approach to the problem.
2. Next, we will initialize some variables. Specifically a solution array to hold any resulting triplets, and also a variable N representing the length of the array
3. We will start iterating through the array from the beginning. Each step, we must first check to make sure that our current value is not the same as the previous value. If so, continue. Otherwise, calculate the “target” which will be the negative value at nums[i] and set the left and right window indices (i + 1, N - 1)
4. Now for the crux of the solution. For each position, we will be starting at the positions immediately following the current position and the end of the array.
5. Next we will compare the sum of the 3 values (i, l, r) and if l + r = target, then we will add the triplet. After this we increment l. Care must be taken to guarantee no duplicates, and we must set another while loop to check that the new value of l is different from the previous l value.
6. If l + r > target, this means we need to reduce our value and therefore will shift our right value (ceiling) lower (r - 1).
7. Otherwise, l + r < target. This means that we need to increase the floor (l + 1)
8. After completing the iteration, we will return the array of triplets

Question 23

Container With Most Water

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Answer 23

We will be using a dp solution

1. First we must declare L, R, width, and res : 0, len - 1, len - 1, 0
2. Next we will iterate backwards from width to 0
3. At each step, we must check if L < R. Whichever is smaller will be the variable we manipulate for the current step.
4. We will alter both res and the smaller of L/R. res will be the max of res and height[X] * width. L/R will be increment or decremented. This will progressively compare the shrinking zone with the previous maximum.
5. return the result

Question 24

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Answer 24

DP + Greedy Binary Search

1. First we will declare an empty list to hold our results
2. Next, we will iterate through each element in the nums array as x.
3. For each value x we will:
   3a. Check if the results list is empty or if x is greater than the last element in the results list. If this is the case, we will append x to the results list.
   3b. Otherwise, we will do a binary search in the results list for the smallest number that is greater than or equal to x (using any method such as bisect_left()).
4. Next, we replace the value in the results list at the id calculated at step 3b.
5. return the length of the results list.

This solution is based on the fact that we know we only need the length of the subsequence. This means that as we get new values we may overwrite values in our results list that will result in a potentially “wrong” set of values, but that doesn’t matter because the length has been recorded.

This allows for any number of new iterations of longer subsequences to regenerate using the same framework.

This solution is O(nlogn) time and O(n) space but can be improved to O(1).

Question 25

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Answer 25

DP Bottom Up

1. We will begin by initializing the lengths of the two words to (m, n) our solution array to be in the shape of the grid of the words + 1, filled with 0s.
2. Next, we will have a two tier loop that will iterate through rows and then through columns.
3. In each inner loop, if the character in both words match, increment the value from the previous space.
4. If the values do not match, take the max of the value of the prior column and prior row
5. Return the last value of the grid

This solution will check each pair of letters for matches, and count what the max set of matches is.

The time complexity is O(mn) and the space complexity is O(mn)

Question 26

Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Answer 26

DP

Note - This solution is very “elegant” and requires only a few lines for very good performance. This results in a relatively hard to understand approach.

1. Initialize variables for the solution list (ok), max word length, and set of words
   1a. set ok to [True], and max word length = max(map(len,words + [’’]))
2. We will iterate through each letter of the input with i
3. we will check that any( ok[j] and words[j:i] for j in range(max(0, i - max len), i)),
   3a. This checks that the word at j is a word, and then searches for another word in the remaining slots for the loop location. If any of the iterables are True, then ANY will return True.
   3b. The statement must end with a comma, this will append the result to the end of the solution list.
4. To finish, return the final value of the solution list. If there were words in the dictionary to connect the whole string, then it will return True.

Question 27

Combination Sum

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Answer 27

Dynamic Programming Solution

1. initialize the dp array of [0] * [1 + target]. This will be the base for the solution loops.
2. Iterate through each num in nums. If num <= target, set dp[num] = 1
3. Two tier loop to populate the dp array
   3a. first tier iterate through range target + 1
   3b. iterate for num in nums.
   3c. If i - num > 0 add dp[i-num] to dp[i]. This will account for all permutations at each level.
4. Return the last value

Question 28

House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Answer 28

This solution will use the exact same premise as House Robber I.

0. We will break the solution into 2 parts. The group of houses including the first house [:-1] and the group of houses excluding the first house [1:]. This is because we cannot use both, we will return the maximum of these two
1. Build a helper function that completes a regular house robber and takes in starting and ending slices as arguments
2. account for edge cases (empty, single value)
3. return the max of cases front and back

Question 29

Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Answer 29

We will be using a dynamic programming solution for this problem. We will be analyzing the 1 step and 2 step jumps, similar to the stairs problem

0. Set up the dp array. [0 for i in range(len(s) + 1)]
1. Set base cases. dp[0] = dp[1] = 1, if s[0] = “0”, dp[1] = 0
2. One step jump. If the integer of the previous value is between 1 and 9, increment the current dp value by the previous dp value.
3. Two step jump. If the integer value of the previous two values is between 10 and 26, increment the current twice prior dp value.
4. return the final dp value.

Question 30

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Answer 30

This problem can be solved with a math solution or with a dynamic programming solution. We will use a dp solution because it will not face the same number restrictions as the math values.

1. check edge case - if either dimension is length 1 (or 0), we will return 1 (or 0, respectively).
2. We must build the dp array. This will be a 2d array the size [m][n] filled with 1s
3. We will iterate through each value of the dp array (from 1 to the end). For each value we will populate it with the sum of the values above and to the left of it.
4. Return the final array value

Question 31

Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Answer 31

We will be doing a dynamic programming solution centered around traversing the array backwards.

1. initialize the goal as the index of the last value
2. begin iterating backwards through the array. If the sum of the current index and the value at that index is greater than the goal, set the goal to the current index.
3. return not goal. This will be True if the goal reaches 0 and False otherwise.

Question 32

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Answer 32

We will be solving this problem by using a graph and checking for cycles/deadlock

We must set a few initial values, not all necessarily at the start:

1a. NOT_CHECKED, CHECKING, COMPLETED = 0, 1, 2
1b. requirement = collections.defaultdict(list)
1c. course_state = NOT_CHECKED for range numcourses

2. We must define a function to check for deadlocks:
   2a. returns True if course state is CHECKING, False if course state is COMPLETED. This is the initial assessment of state
   2b. If we are still inside the function, this means the value was NOT_CHECKED. We must update the state to CHECKING
   2c. Next, we will recursively address all the the prerequisite courses in requirement, checking their status as well.
   2d. If any of the prerequisites in requirement fails and has a deadlock, this will return True.
   2e. If all prerequisites successfully pass the iteration through requirement, then we set the state to “COMPLETED”
3. We must fill the requirement dict. We do this by iterating through course, pre_course in prerequisites and appending the pre_course to requirement[course].
4. Last, iterate through each course and check for deadlocks. If any are found, return False. Otherwise, return True.

Question 33

Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Answer 33

– Initialize Variables

1. Check for empty matrix, return empty array
2. declare sets p_visited and a_visited
3. declare rows and cols as the dimensions of the matrix
4. declare a tuple directions with the 4 cardinal direction coordinates ((0,1),(1,0),(-1,0),(0,-1))

– Solution Architecture

1. Iterate through each row in rows
2. traverse (row, 0) for p_visited
3. traverse (row, cols-1) for a_visited
4. Iterate through each col in cols
5. traverse (0, col) for p_visited
6. traverse (rows - 1, col) for a_visited
7. return a list of the intersection of a_visited and p_visited

– Traversal Function

1. Accepts 3 args (i, j, visited)
2. If (i,j) in visited, return
3. Add (i,j) to visited
4. For each direction in directions, set the next_i and next_j to the i/j + coordinate value of the direction.
5. If both next_i and next_j are valid and within rows/cols, if the matrix[next_i][next_j] > matrix[i][j] then traverse (next_i, next_j, visited)

Question 34

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

(This means rotating clockwise until all elements have been addressed)

Answer 34

We will be solving this with a while loop with sliding boundaries.

0. set variables for top, bottom, left, and right as the dimensions of the matrix. Also, initialize the solution array.
1. Begin the while loop with the conditions that top < bottom and left < right.
2. Paying attention to cardinality, create a for loop for each direction that spans the top/bottom or left/right and in the forward/backward direction required. Inside the loop, append the appropriate value to the answer array.
3. After the for loops, increment or decrement each value as appropriate to adjust the boundaries.
4. After the while loop, if len(ans) is less than height*width, we left one row or column in the matrix.
   4b. We will append the remaining values by iterating through each row in (top, bottom+1), each col in (left, right+1) and appending the value at [row][col]
5. return ans

Question 35

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Answer 35

There are many potential solutions to this problem using many available tools. The solution detailed will be a straight forward one. This solution will rotate the image by making two flips, one diagonal and one across.

0. initialize a variable for the length of the matrix for reference later
1. The diagonal flip. To begin the diagonal flip, we must iterate through the length of the matrix and through the range of the first value.
   1b. Inside of the inner loop, we will swap matrix values for [i][j] and [j][i] with each other.
2. The horizontal flip. To begin the horizontal flip we will iterate through each row and for each row we will iterate through the half the length of the matrix.
   2b. To complete the horizontal flip inside the inner loop, we will be setting row[j], row[~j] to equal their counterparts (~j being the bitwise operator resulting in n - 1 - j). This loop will repeat inwardly for each pair of columns for every row.
3. We don’t need to return anything, as this was all performed in place.

Question 36

Word Search

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.

Answer 36

We will be solving this problem with a backtracking DFS solution. This solution will check for the desired index and then branch out from that location, this will prevent unnecessary extra checks in some cases.

0. initialize variables self.found = False, and n,m,k to length of board, board[0], and word respectively.
1. Iterate i, j through product(range(m), range(n))
   1a. If self.found == True, return True. Otherwise execute dfs(0, i, j)
   1b. return False

_____________
dfs function

0. accepts 3 args (ind, i, j)
   1a. if self.Found, return
   1b. if ind == k then self.Found = True and return
   1c. if i or j is greater than or less than the boundaries, return
1. tmp = board[i][j]
   2a. if tmp != word[ind], return
2. board[i][j] = “#”, This prevents us from visiting this location again.
3. for x,y in [4 direction pairs] run dfs(ind + 1, i+x, j+y)
4. board[i][j] = tmp, which will replace the duplicate prevention character with the original

Question 37

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

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.

Answer 37

We will be solving this problem by counting elements.

0. initialize a dict to store element counts
1. iterate through each element of the first string, first checking for the element’s presence in the dict, and then adding one to the value.
2. iterate through each element of the second string, first checking for each elements presence (and returning False if not present) and then decrementing by one
3. iterate through each of the keys in the dict. checking that the value of each key is 0, return False otherwise.
4. return True

Question 38

Group Anagrams

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.

Answer 38

We will solve this problem by comparing each of the sorted words with each other.

0. initialize a dict
1. Iterate through each word in words
   1a. create a temp variable s = ‘‘.join(sorted(word))
   1b. if s in dict, append the word, else dict[s] = word
   1c. return dict.values() *This returns a list of the values, which will be a list of lists, which is the correct format.

Question 39

Valid Parentheses

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.

Answer 39

We will solve this problem using a stack.

0. initalize stack = [‘N’], and dict = {‘)’:’(‘,’]’:’[’,’}’:’{‘} - this maps the opening and closing brackets
1. Iterate through each character in the input string s.
   2a. If the character is in dict.keys(), if stack.pop != dict[i], return False
   2b. if the character is not in dict.keys(), append to the stack
2. return len(stack) == 1

Notes:

• we initialize stack to [‘N’] to cover the empty stack edge case
• we return len(stack) == 1 to account for extra characters and for the base length of 1

Question 40

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Answer 40

We will be solving this problem with a sliding window approach.

0. initialize variables for the left and right index to be 0 and the last index
1. begin a while loop that will break when the left index is greater than the right index
2. handle non alpha numeric cases with while loops for both the left and right indices. while they aren’t alnum, increment/decrement until they are
3. Compare the alphanumeric values of the string (be sure to make lowercase to handle for capitalization). If they are not equal, return False
4. return True

Question 41

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Answer 41

We will be solving the problem using Dynamic Programming, although there is a significantly better solution using “Manacher’s Algorithm” (To do later)

0a. create a square array of len(s) and fill all values with False
0b. Fill the diagonals with True and set ans = s[0]

1. Begin the outer loop j over range(len(s))
2. Begin the inner loop i over range(j)
3. Check if s[i] == s[j] AND dp[i+1][j-1] is True (inner substring is a palindrome) OR i=j+1 (length 1 substring)
   3a. set dp[i][j] to True
4. Check if j - i + 1 > len(ans)
   4a. set ans = s[i:j+1]
5. return ans

Question 42

Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Answer 42

This problem is very similar to “Longest Palindromic Substring” and we will take a similar approach to solve the problem. Once again, we will be using a DP solution, but the optimal solution uses the Manacher Algorithm.

0a. create a square array of len(s) and fill all values with False
0b. Fill the diagonals with True (can be done inside the outer loop as well) and count = 0
1. Begin the outer loop and iterate backwards over len(s).
1a. In the outer loop, increment count
2. Begin the inner loop from i+1 to len(s)
2a. Check for 2 character case: if j == i + 1 AND s[i] == s[j], dp[i][j] = True and increment count.
2b. Check dp case: if j > i+1 AND dp[i+1][j-1] AND s[i] == s[j], dp[i][j] = True and increment count.
3. Return count

Question 43

Merge Two Sorted Linked Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a 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.

Answer 43

We will solve this problem with interval insertion.

0a. Check the edge cases of list1 and list2 both being empty or one of them being empty.
0b. Initialize seek and target to be list1 and list2 such that seek is the list with the lower value
0c. Set head to seek
1. Begin a while loop that will execute as long as seek and target are valid
2. While seek.next and seek.next.val > target.val, seek = seek.next
3. swap seek.next and target
4. seek = seek.next
5. return head

Question 44

Merge K Lists

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.

Answer 44

We will be solving this problem with divide and conquer method.

mergeKLists Function:

0. Check edge cases of zero lists and 1 list
1. Set mid to the midpoint of the len(lists)
2. Set l,r to recurse into mergeKLists Function with the respective slicing [:mid] and [mid:]. This will allow us to recursively merge the lists together, ending with the two halves
3. return self.merge(l,r)

merge Function:

This merge function will function similarly to the Merge Two Sorted Linked Lists problem and take in (l, r) as arguments.

0. initialize dummy = p = ListNode()
1. begin a loop while l and r are valid.
2. if l.val < r.val, then p.next = l, and l = l.next
   2b. otherwise, p.next = r, and r = r.next
   2c. p = p.next
3. p.next = l or r. This will append any leftover elements from l or r (which will be from none or one of them) to the end of p.
4. return dummy.next

Process:

Ultimately, this will recurse until it is list groupings of 2 or less sorting with each other. As they roll back up they will once again merge into each other until all recursions have been processed, resulting in a sorted linked list.

Question 45

Remove Nth Node from End of Linked List

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

Answer 45

We will solve this problem using a two pointer solution.

0. First we will create our pointers fast = slow = head
1. step through fast n times moving on to fast.next each time
2. Check for edge condition of no more space in the list. if not fast, return head.next
3. while fast and fast.next, step both fast and slow
4. set slow.next to slow.next.next
5. return head

Notes:
We move forward n times, then move forward with both pointers until the end of the list is reached with the fast pointer. This leaves the slow pointer N nodes from the end. We then bypass the node by setting the next value to next.next.

Question 46

Reorder Linked List

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.

Answer 46

This will be a 3 part solution, combining elements of other Linked List problems. Finding the midpoint (Remove Nth Node from End of List), reversing the second half of the list (Reverse a Linked List), and merging the two halves from the beginning (Merge Two Linked Lists).

Finding the Midpoint:

0. Set slow = fast = head
1. while fast.next and fast.next.next, step slow by one and fast by two

Reversing the Second Half:

2. set prev, curr = None, slow.next. This is necessary for having the end of the linked list point to None and starting with the midpoint of slow.next
3. begin a while loop that persists while curr is valid
   3a. nextt = curr.next
   3b. curr.next = prev
   3c. prev = curr
   3d. curr = nextt
4. slow.next = None

Merging the Two Halves:

5. set head1, head2 = head, prev
6. begin while loop that persists while head2
   6a. nextt = head1.next
   6b. head1.next = head2
   6c. head1 = head2
   6d. head2 = nextt