Remove Nth node from end of list

Problem statement
Given a linked list:

remove the n^{th} node from the end of list and return its head.

Sample input

Sample output

Note: n will always be valid.

Solution
For this we will use a two pointer technique. That is, we will iterate over our list using two pointer i and j. First, we will fast-forward j n positions. That is, j will be n nodes ahead of i.

We will then iterate over the list using i and j by pointing them to the next nodes one-by-one. When j reaches the end of the list, we will know that i will point to the (n+1)^{th} node from the end of list. We will then adjust the next pointers accordingly and return the head of the list.

Full code

 

3Sum challenge

Problem statement
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = \left[-1, 0, 1, 2, -1, -4\right],

A solution set is: \left[ \left[-1, 0, 1\right], \left[-1, -1, 2\right] \right]

Solution
The idea behind the presented algorithm is to sort the array in ascending order first. Once the array is sorted we can iterate over the elements using two loops which gives us an \mathcal{O}(n^2) time complexity.

Since we need to find three elements a, b, c such that a + b + c = 0, we will use the outer iteration to fix a = nums[i]. For the rest of the elements b and c we will use an inner-loop with two pointers:
• A incrementing pointer, l, starting at i + 1
• A decrementing pointer, r, starting at len(nums)

If the sum = nums[i] + nums[l] + nums[r] is equal to 0, we have found ourselves a valid pair.If sum \textless 0 we have to increment nums[i] + nums[l] + nums[r]. We do this by increasing l (remember our array is sorted). If sum \textgreater 0 we need to decrement sum by moving r to the left.

We will also do some skipping of adjacent elements that are equal in order to avoid duplicate pairs.

Full code

 

Generate parentheses challenge

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

For example, given n = 3, a solution set is:

Solution

 

Longest palindromic substring challenge

Problem statement
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Sample input 1

Output 1

Sample input 1

Output 1

Solution
We are going to iterate over each character in the input string and assume that each character we iterate over is the middle of a new potential palindromic substring.

For instance, if are currently at index i we will assume that s[i] is the middle of palindromic substring. Obviously s[i] is a palindrome of length 1. We will then try to extend this palindrome to the left and to the right as long as the left and right edges have the same character.
If we s[left] and s[right] are not equal anymore we have a palindrome s[left + 1 ... r - 1]:

Since s can have even or odd number of characters we have to consider both cases when starting to extend our initial palindrome:

since in case of even our middle will consist of two characters (at indices i and i+1) and not just one.

Full code

 

Group anagrams challenge

Problem statement
Given an array of strings, group anagrams together.

Sample input

Sample output

Note: All inputs will be in lower-case.

Full code

 

Build power set of set

Problem statement
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

Sample input

Sample output

Full code

 

Swap list nodes in pairs challenge

Problem statement
Given a linked list, swap every two adjacent nodes and return its head.

For example:
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Full code

 

Container with most water challenge

Problem statement

Given n non-negative integers a_1, a_2, \dots, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Solution
We are going to solve this problem using two pointers l and r. Pointer l starts from the left-most side and r starts from the right-most side. We then keep track of our maximum container:

and then move one of the pointers based on the following conditions:

Let us explain the logic behind this algorithm using the illustration below.

For wall A we want to use wall D as its counterpart since D is taller than A and as far on the right as possible. Any wall to the left of D can be ignored because it will only make our container smaller as D is already taller than A. That is why it doesn’t make any sense to decrease our index r. With A and D we have a container size of 3.

We then increment our index ‘l’ because A is shorter than D. That is, move it to wall B in hopes that we can find a taller counterpart for our tall wall D. Now, wall B is taller than its predecessor and actually increases our container size to 4. We can see that since we previously increased the index pointing to the shorter of the two walls (A vs D) we were able to find a counterpart (B) for wall D that increased our container size.

Finally we again increase our index pointing to the shortest wall in hopes that we may find an even taller counterpart for D. Moving l to C we see that this does not increase our container size. Also since l and r meet, we stop the search and return 4.

The full code is listed below.

Full code

 

Merge overlapping intervals challenge

Problem statement
Given a set of intervals in any order merge the overlapping intervals and return the list of merged intervals.

Sample input

Sample output

Solution
The first step we are going to take is sort the intervals in ascending order based on their ending time.

Next, we are going to traverse over the sorted list and as long as two adjacent intervals interval_1 and interval_2 overlap (interval_2.start \le interval_1.end) we keep merging them by taking min(interval_1.start, interval_2.start) as the new start and interval_2.end as the new end for our new interval.

Once no more adjacent intervals are merging we add the newly created interval to our new list and resume the traversal until we have visited all intervals in the original list.

Full code

 

KnightL on a chessboard challenge

Problem statement
KnightL is a chess piece that moves in an L shape. We define the possible moves of KnightL(a,b) as any movement from some position (x_1, y_1) to some (x_2, y_2) satisfying either of the following:

x_2 = x_1 \pm a and y_2 = y_1 \pm b, or
x_2 = x_1 \pm b and y_2 = y_1 \pm a

Note that (a, b) and (b, a) allow for the same exact set of movements. For example, the diagram below depicts the possible locations that KnightL(1,2) or KnightL(2,1) can move to from its current location at the center of a 5 \times 5 chessboard:

Observe that for each possible movement, the Knight moves 2 units in one direction (i.e., horizontal or vertical) and 1 unit in the perpendicular direction.

Given the value of n for an n \times n chessboard, answer the following question for each pair where 1 \le a,b \textless n:

  • What is the minimum number of moves it takes for KnightL(a,b) to get from position (0,0) to position (n - 1, n - 1)? If it’s not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each KnightL(a,b) according to the Output Format specified below.

Input Format
A single integer denoting n.

Constraints
5 \le n \le 25

Output Format
Print exactly n - 1 lines of output in which each line i (where 1 \le i \textless n) contains n - 1 space-separated integers describing the minimum number of moves KnightL(i,j) must make for each respective j (where 1 \le j \textless n). If some KnightL(i,j) cannot reach position (n - 1, n - 1), print -1 instead.

For example, if n = 3, we organize the answers for all the (i, j) pairs in our output like this:

Sample Input 0

Sample Output 0

Explanation 0

The diagram below depicts possible minimal paths for KnightL(1,1), KnightL(1,2), and KnightL(1,3):

One minimal path for KnightL(1,4) is:

(0,0) \rightarrow (1,4) \rightarrow (2,0) \rightarrow (3,4) \rightarrow (4,0) \rightarrow (0,1) \rightarrow (4,2) \rightarrow (0,3) \rightarrow (4,4)

We then print 4 4 2 8 as our first line of output because KnightL(1,1) took 4 moves, KnightL(1,2) took 4 moves, KnightL(1,3) took 2 moves, and KnightL(1,4) took 8 moves.

In some of the later rows of output, it’s impossible for KnightL(i,j) to reach position (4,4). For example, KnightL(3,3) can only move back and forth between (0,0) and (3,3) so it will never reach (4,4).

Solution
We are going to solve this problem by searching for a solution recursively for every (i,j). From each current position (r,c) we know which new position (newRow, newCol) we can reach. The possible values of (newRow, newCol) given a current position (r,c) and a pair (i,j) can be easily computed as follows:

We then have 8 (not necessarily valid) new positions we can reach from (r,c). Example: for a given newRow = rows[1] the corresponding newCol will be cols[1]. That is, an entry at index idx in rows corresponds to an entry at cols[idx].

We then call our search function recursively for every pair (newRow, newCol) we can reach from a given current position (r,c).

For our recursive algorithm to work we need to have a terminating condition:

where count is the current number of steps it took us to reach this far for a given function call.

Obviously thats not all. In order to avoid jumping between two positions indefinitely we need to store some sort of state so our algorithm will stop in case we can never reach (n - 1, n - 1). That is, we are only going to jump to a new state if we haven’t visited that state already or if we may have found a shorter path to that state in case the state has been visited before.

Our state is a combination of row, column and number of steps it took us to get there. We are going to jump to (newRow, newCol) only when:
– we haven’t visited (newRow, newCol) before, or,
– we have visited (newRow, newCol) before but the number of steps it took us to get there is larger than count + 1

Finally we need to keep track of our minimum number of steps for every (i,j).

Full code