The Only Algorithms Coding Interview Course You'll Ever Need

There are a lot of restrictions given by the problem statement, but we can use those restrictions to model our solution. First of all we know we can only use constant space, so any helper data structure is out of question here. We can't modify the input array, so the tricks with making the values at certain index negative and then checking for negative numbers won't work. Can we sort the array? Yes, if sort the array we will arrive at constant space complexity, but O(nlogn) time complexity by checking if the previous element in sorted array is equal to the current (making it the duplicate number). So the question is can we optimize this further? It might come as a surprise that the problem can be reframed to finding the entry point of a cycle just like in linked list (Linked List Cycle). The algorithm is also called "tortoise and hare" or Floyd algorithm. But how do we model the node links just like we have it in linked list with the next pointer?

Note that indices of array are in 0..n (inclusive) range while the values of array are in 1..n inclusive range, so we can be sure that any value of array will point to in-boundary index of array. What would happen if we had 0 as one of the values in array? Well if 0 is the first element we would get a cycle in 0, because it would point to itself (nums[0] = 0), but because of the problem restrictions we know that's not going to happen. So we can model the next relation as next of currentPointer is nums[currentPointer]. How do we detect the cycle? You can check Linked List Cycle, but we have a slow and fast pointer where the fast is moving twice the speed ("on your left joke"). Eventually if there is a cycle the pointers will meet (by the problem statement there is a cycle because there is a duplicate value which is mapped to more than one index).

How do we find the entry point in the cycle (also our duplicate value)? Let's say the distance of slow pointer is defined as d(slow), while the distance of fast pointer is d(fast). By our configuration we know that fast is twice faster than the slow pointer:

d(fast) = 2 * d(slow)

Let's also mark the distance between the starting point (head of the list) and the entry point as X, and distance between meeting point and entry point as a:

d(slow) = X + ad(fast) = X + nC + a2 * (X + a) = X + nC + a => X + a = nC

nC is the number of times fast pointer has gone through the cycle where C is the length of the cycle. So we have X + a = nC which means that if we move a fast pointer X steps it should complete one cycle and be at the entry point of cycle again. But what is X? X is distance from starting point (head of the list) and cycle entry point. So if we move slow pointer from the start X steps, and fast pointer from the meeting point X steps they will meet at the entry point of the cycle. We do this in the second loop, by moving the slow pointer again to the start of the list and then moving both slow and fast pointers step by step until they meet. When they meet we found our entry point and also the duplicate and solution for our problem.

We keep a board which is a array of arrays of characters as a helper data structure leading to O(n^2) space complexity, while for time complexity at each level we have one less option than at the level before (n * (n-1) * (n-2)... * 1 = n!) with a multiplier of n (because of for loop in base case) leading to n * n!. We first fill the board with empty cells marked with '.', then we call our recursive function helper which takes as parameter current row where we're trying to place the queen. If we have reached n rows we have a valid configuration which we add to our result list which will be later returned as final result from the main function. Otherwise, we try to place the queen in the current row, by trying all columns and checking with isValidPlacement function if we can place it at each of the columns. If we can place it, we mark the cell with 'Q' and try to solve the board with this selection by moving to the next row, finally we backtrack board[row][i] = '.'; so we can choose another column. The validation function first check if we have a queen in the same column as our current placement selection, and it returns false as validation result if we do. The same goes for the left and right diagonal check (the last two for loops), otherwise if there isn't a queen on the board attacking our selected cell, we return true.

We implement the same BFS logic of having first the initial candidates (already rotten oranges in this problem) and then searching for the next level of candidates which are neighbors of rotten oranges. We do that as long as we have a non-empty queue. We mark each visited neighbor by setting its value to 2 (rotten orange). Initially we also count the total number of oranges and then in our queue traversal we decrement that so we can use that information to see if we have visited all the oranges (or if it's not possible to visit them all). For each level we increase the time, and we return time - 1 as our final result since we don't count the first set of candidates (they're already rotten in the "0 minute"), otherwise if we couldn't reach all oranges, we return -1. The time and space complexity are proportional to the size of the grid O(mn).

This is a simple problem utilizing well known binary search. But the right implementation of binary search can be tricky, here are steps you should take when implementing binary search (or some modification of it):

1. Is there any total or implicit order (order as in sorted array), you first thought should be to utilize binary search.

2. Determine the low and high. In most cases low and high would represent the start and end of input array/list.

3. Define a loop invariant that will be true for the whole execution of the loop (in this case low <= high)

4. Calculate mid element. The only tip here is to use low + (high-low)/2 instead of (low + high)/2, we do this to prevent overflow (think of high being a big number and adding low to it would overflow the integer)

5. Eliminate elements (in most cases half of array). So, if we don’t find an element we have to check if the current element at mid position is either larger or smaller than the target. If it's smaller there is no point in searching in the left half (since the array is sorted and any element before mid will be also smaller than target). Same goes when the mid element is larger than the target, then we don't have to search for it in the right half. Since we're eliminating half array each iteration we get to O(log n) time complexity (in other words how many time can we half an array of n elements).

We perform Depth-First Search (DFS) on the input matrix by going to all four neighbors in four directions (but doing it depth wise since we will be exhausting one direction until it's out of boundary). It's a standard template on how to do a DFS on matrix like structure:

• You define a helper method taking as parameters the input matrix, current position (row and column) and its current property currentColor and info about the desired property.

• You call the helper method and first check if we're out of boundary with our current position (index or either row or column negative or larger than equal to the size of array), then we check if the color at the position is currentColor and we return from the helper function if it's not.

• We also check if the current position pixel has already been painted to the desired color, so that we don't end in an infinitive loop visiting one pixel again and again, it's the same as if you would keep a matrix visited checking if you already visited every element in the matrix.

• We make the current position pixel our desired color.

• We move down, up, left and right by either incrementing or decrementing row or column.

The time and space complexity are O(mn) which is the size of the matrix since we can traverse all elements and we have recursions stack (space complexity) corresponding to the size of the matrix/grid.

Of course, this is the optimized solution, so let's break down the thinking process leading to this solution. Your first hint should be that there is explicit recurrence in the problem statement: we have to reach a known goal (n stairs), and to get there we can only take 1 or 2 steps. So, let's say we're almost at the n step (mission completed) what previous stairs are we interested in? Well since we can only use 1 or 2 steps, we are only interested in stairs n-1 and n-2. So the recurrence relation would be waysToClimb(n) = waysToClimb(n-1) + waysToClimb(n-2). How can we guarantee that the ways will be distinct? Well, the difference is in the last step (in other words you will either use 1 or 2 steps to reach the final goal from the sub goal). Now that we have this formula it's easy to spot that this falls under the category of DP (dynamic programming) problems. So how do we solve those? Here is a "framework" I've used to get my mind around DP problems (it consists of 6 steps):

1. Category

2. States

3. Decisions

4. Base Case

5. Code

6. Optimize (Time or Space Complexity)

So, let's break down each of these steps:

Most of the DP problems fall into one of the following categories:

1. 0/1 Knapsack

2. Unbounded Knapsack

3. Shortest/Critical Path

4. Fibonacci Sequence

5. Longest Common Substring/Subsequence

All these categories will be mentioned later once they fit to the problem statement. For now, let's focus on this problem, since the final state is dependent on the step before and two steps before it perfectly matches Fibonacci Sequence.

Next on how do we find states? States are generally information we need to keep as we move to the optimal/base case. It can be a helper sum array, indices, index difference, so basically the minimal number (because we have to reduce the space complexity) of information we need to carry with us as we move to the optimal/base solution.

What decisions we need to make to arrive at the optimal/base case? In this problem it's easy since it's given by problem statement, you can either take 1 or 2 steps, so your decision from the current state is either to take 1 or 2 steps.

Base case comes from the recursion stop point logic, in essence when do we stop calculating our formula. It can be that we have reached (or started) from base states (states given as part of the problem, in our case we know that we can reach stair 1 in only one way that is take 1 step, and step 2 in 2 ways 1+1 or 2). When we reach n stairs we know that we are at our desired step/goal.

Using this logic, we can code up a solution using recursion:

• Java

• JavaScript

• Python

• C++

public int climbStairs(int n) {   

if (n <= 2) {        return n;    }   

return climbStairs(n-1) + climbStairs(n-2);

}

But the complexity of this solution is O(n) for space complexity (because of the recursion stack) and time complexity O(2^n) (at each step for n steps we have 2 calls). How do we reduce complexity, well we know that our pain point is time complexity so we can shift a bit of responsibility/cost to space. We can use memoization (note different than memorization), so what does it mean? It means that we can store expensive recursion calls in auxiliary data structure (often variables like this are called memo) like hashmap, hashset and similar. This helps us to only calculate value for the subproblem (previous stair) once and every other time retrieve the value from the memo (you can think of it as cache for expensive operations):

• Java

• JavaScript

• Python

• C++

class Solution {   

public int climbStairs(int n) {       

Map<Integer, Integer> memo = new HashMap<>() {{            put(1, 1);            put(2, 2);        }};       

return climbStairs(n, memo);   

}   

private int climbStairs(int n, Map<Integer, Integer> memo) {       

if (memo.containsKey(n)) {            return memo.get(n);        }       

memo.put(n, climbStairs(n - 1, memo) + climbStairs(n - 2, memo));       

return memo.get(n);   

}}

This is a top down approach (starting with desired goal and breaking down to subproblems) and will result in O(n) for both space and time complexity (at most n elements stored in hashmap). Can we optimize further?

Well let's first introduce the bottom up approach:

• Java

• JavaScript

• Python

• C++

public int climbStairs(int n) {   

if (n <= 1) {        return 1;    }   

int[] dp = new int[n + 1];   

dp[1] = 1; dp[2] = 2;   

for(int i = 3; i <= n; ++i){        dp[i] = dp[i-1] + dp[i-2];    }   

return dp[n];

}

We get the same space complexity, but we first calculate the "leaf" (if you imagine the recursion as a tree) subproblems and then move upwards. One thing we can note is that for each stair we only need to hold the value at 2 steps behind and value at the value 1 step behind, so do we need the whole array? No, we can reduce the space complexity to constant by tracking only two stairs, for each stair we are trying to apply the formula for (as shown in the initial solution).

So, there we have it, we moved from encrypting what the problem really is, to recursive approach using the recurrence relation formula we found by analyzing the problem statement, we moved to top down and bottom-up approach to reduce complexity by using memorization and then finally optimized further by removing the need for helper data structure thus reducing the space complexity.

Whenever you have a clear relation between different elements given by the problem statement you should think if you can reframe the initial problem to a graph problem. In our case the elements are courses, and the obvious relations are given by prerequisites. We can only finish all courses if there are no cycles in the graph (second example, you can't start course 0 before you start 1, but you can't start course 1 before you start 0 so it's impossible to finish the course since if modeled courses as a graph we would have a cycle). To find if graph contains cycle we perform topological sort: Topological sort of directed graph is a linear ordering of its vertices such that, for every directed edge U -> V from vertex U to vertex V, U comes before V in the ordering. Why does topological sort detect cycle in graph? In Topological Sort, the idea is to visit the parent node followed by the child node. If the given graph contains a cycle, then there is at least one node which is a parent as well as a child thus breaking topological order. So, if we can visit all elements count == numCourses we know there is an existing topological order, otherwise if there is a cycle topological order would break and we wouldn't have visited all elements.

So how do we perform topological sort:

• We represent the graph in adjacency-list representation (each node mapped to its neighbor), also we track the degree of a node (number of incoming edges to each node)

• We use prerequisites array to form the adjacency-lists and increase the degree for each node

• Next, a queue is created with initial candidates picked so they have degree == 0 (course that can start without waiting for completion of any other course)

• Each time we poll another course from the queue of candidates we check its neighbors and if there are any potential candidates after we have visited the current node which we can be added to the queue (--degree[neighbour] == 0)

For space complexity we have O(E+V) since we're building a graph of E edges and V vertices. Since we visit all edges and vertices in the topological sort we have O(V+E) time complexity.

We already know how to merge lists together using the approach we implemented in Merge Two Sorted Lists so we can just use it here too as the second part of the mergesort process. To break the linked list into two parts (and keep on halving those halves recursively) we can use the slow and fast pointer approach, where the faster pointer is moving 1 node faster than the slower (double the speed), so when the fast arrives at the last element, the slow one will be at the middle. We can use this information because the slow pointer now has next set to the start of the second half of the linked list, while the first half starts at the original list head. To break those halves into two, and prevent infinite loop we do slow.next = null which breaks the connection between the halves. We recursively call the sortList on both halves and merge the two lists using our mergeTwoLists helper function. Note that space complexity here is O(logn) since we have recursion stack only contributing to it, but it is possible to reduce the space complexity down to constant O(1) if we turn this solution into iterative one. Notice that we're breaking the list down to sublists with only one node, then combining those into sorted sublists with two nodes and so on. We can use that information and start diving by some factor (e.g. first all 1-node size lists, than 2-nodes lists...) each time doubling the factor.

You can think of trie as a k-ary search tree where each node can have k children, in this case each TrieNode can have 26 children (since we only deal with lowercase English letters), also note that each TrieNode holds the information isWord which indicates that current node is the end letter of the inserted word. At the Trie constructor we define the root which will be the entry point for both read and writes to the trie. For inserting the word, we start with our root and check if it has child at index corresponding to the first letter in the word letter - 'a', if not we create it (with its set of children), then we move to that new node following the edge that matches the first letter. We follow the same pattern for all other letters of the word we're inserting into the trie. The same goes for search and startsWith we utilize the searchPrefix method which will traverse the trie and return the TrieNode matching the last letter in the prefix, note that for startsWith it is enough to just check if the returned node is not null, but for search(word) we also have to check node.isWord flag.