# Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: `1->2->3->4->5`

For k = 2, you should return: `2->1->4->3->5`

For k = 3, you should return: `3->2->1->4->5`

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: To reverse nodes in a linked list k at a time and return the modified list.

Q: What are the data?

A: A linked list and an integer k.

Q: What are the constraints?

A: From the example above, we should probably assume this is a singly linked list. We cannot change the value in the node (Actually this is a very good idea in modifying linked list). Constant memory only. If at some point, the number of nodes is not the multiple of k, these nodes should remain the same order.

Q: Have you seen it before or at least something similar?

A: Yes I think I have. A similar problem is to reverse a singly linked list in place. I solved it before and it only took constant memory. I think we can apply the solution of that problem to each K nodes for reversing purpose.

Q: Good. For the whole problem, what kind of strategy should we use? Suppose we have reversed K nodes in the list, what about the rest of list?

A:  We do the same for the rest and connect with the k nodes reversed previously.

Q: Can you describe it in more details?

A: OK, for the rest of the linked list we reverse the nodes in k-Group and connect with previously reversed k nodes. Ah I see where this is heading. We are looking at a recursion here.

Q: Yes we are. Now think about the base case of this recursion.

A: That would be the number of remaining nodes is not a multiple of k and we should just connect them with the previously reversed part.

Q: What about the recursive case?

A: Hmm, we should reverse the current k nodes at hand. reverse the next k nodes and connect with them. Then return the current reversed part so the previously reversed part can connect with it.

Q: OK not super clear but I guess you have the idea.  In the base case, how do you determine if the number of remaining nodes is a multiple of k?

A: Starting from where we are, go k steps further. If at any point, we hit null, then we know there are enough nodes for reversal.

Q: Good. The take-away message here is that recursion could be a very handy trick for solving linked list related problems. So keep it in your toolbox.

Code on github:

# Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character `'.'`.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: A program that solves Sudoku.

Q: What are the data?

A: A Sudoku puzzle. Actually a 9 x 9 character matrix, with partially filled cells. Empty cells are represented as ‘.’

Q: Any constraints?

A: None except for the Sudoku rules:

• Each row must have the numbers 1-9 occuring just once.
• Each column must have the numbers 1-9 occuring just once.
• Each block (check the link above for details about block) must have the numbers 1-9 occuring just once.

Q: Have you played Sudoku before?

A: Not even once. I guess this is my first and last attempt to play Sudoku. Based on the rules, I guess I have an idea for solve it. Just like the N-queens problem we solved last time, we will probably need backtracking: At an empty cell, I try to find a suitable number from a set of candidates to put it there and then move on to the next empty cell. If one does not work out, I find the next suitable number. If none of the candidates works out, then the number I placed at the previous empty cell was a bad choice and I need to go back to deal with it. This seems like a pattern that requires backtracking.

Q: Good, now to work with backtracking, are there anything you need?

A: Yes, I believe we need something to keep track of whether I could place a number in an empty cell or not, and a set of candidates for each empty cell.

Q: How do you know if you can place a number in an empty cell or not?

A: Hmm I have to check the row, column and block it resides in to see if that number already exists. The empty cells on the same row will share the info of this row. The same applies to columns and blocks. So we need three 9 x 9 boolean matrix: rowStatus, colStatus and blockStatus. Initially all values are set to false. If a number n is placed at cell (i, j), then we go and update rowStatus[i][n-1] = true, colStatus[j][n-1]=true, and blockStatus[getBlockInd(i,j)][n-1]=true.

Q: Good. Now what about the candidates for each empty cells you mentioned? It seems like you need to keep a lot of numbers at hand.

A: Hmm not necessarily. For each cell, there are only 9 options at most. I could try all of them every time but that seems a bit brutal. I could keep track of a number called startInd to save the index of the last number I tried at a certain cell. Next time I need another number at this cell, just get the number at the next index. If the next index is out of bound, that means none is a good fit. In that case, we set the  startInd of this cell to 0 and go backtracking to the previous cell.

Q: Sounds good. Now can you write some pseudo-code?

A: Sure.

```// Initialization
// scan through the board and keep track of all the empty cells
emptyCells = getEmptyCells(board);
// update the status based on the initial board

int i = 0; // the index of an empty cell we are dealing with
while(true){
Cell cell = emptyCells.get(i);
int row = cell.row;
int col = cell.col;
char num = getSuitableNum(row, col, rowStatus, colStatus, blockStatus);
if(num == '.'){ // no suitable num, previous bad choice
if(isOutofBound(--i, emptyCells.size())) return;
Cell previousCell = emptyCells.get(i);
row = previousCell.row;
col = previousCell.col;
char previousVal = board[row][col];
board[row][col]='.';
undoStatusChange(rowStatus, colStatus, blockStatus, row, col, previousVal);
}else{
board[row][col] = num;
updateStatusChange(rowStatus, colStatus, blockStatus, row, col, num);
if(isOutofBound(++i, emptyCells.size())) return;
}
}

// for details of utility functions like undoStatusChange, isOutofBound, and getSuitableNum, please check the real Java code at the bottom link.
```

Q: I see you are passing the rowStatus, colStatus and blockStatus around a lot. Is there anyway that we can organize them in a better way?

A: Hmm maybe I should put them all in one Class so I could just pass in one object instead.

Q: Sounds good, now let’s solve this with real code.

A: OK 🙂

Code on github:

# N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

```[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]```

A follow-up question: Now, instead outputting board configurations, return the total number of distinct solutions.

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Well, this is a classic problem, isn’t it? However, all I know is that it’s classic and I’ve never really read about any article of NQueens, except for the title NQueens. So lucky for me, I got the chance to solve it with no prior knowledge.

Q: What is the unknown?

A: All possible board configurations that satisfy the requirements.

Q: What are the data?

A: An N x N chess board (or just an N x N matrix).

Q: What are the constraints?

A: No two queens on the board can attack each other. In other words, no two queens can be on the same row, column or cross.

A: I don’t have anything fancy, but possibly a naive way of solving it: for example, I could put a Queen in an available cell (no other Queens can attack) on the chess board. Then cross out all other cells this Queen can attack. Then on the second row, I place another Queen in an available cell and then cross out cells she can attack. On the next row I do the same thing until we place all N Queens on the chess board.

Q: What if on a certain row, there is nowhere you can place a new Queen?

A:  Hmm, that means the placement of the Queen on the previous row was a bad move.

Q: So what should you do about it?

A: Well, undo it then. Undo the cross out of board cells caused by that bad move. Get the queen up and place it somewhere else on that row, if there are any available cells left.

Q: What if there are no available cells neither?

A: Hmm, then the bad move’s previous move was bad. We have to do the same thing for it as above.

Q: Good. Now, can you summarize your thought and maybe find out the pattern in it?

A: I place a Queen in an available cell on a row, and cross out cells she can attack. Then on the next row, again I place a Queen in an available cell and cross out cells she can attack. If I cannot place any Queen, that means the previous move was bad and we undo that move and its cross-out, then place that Queen in another available cell. If that’s not possible, then the previous previous move was bad and we should….  OK I get it. This has something to do with recursion, doesn’t it? And in fact, even if we find a solution, we still need to undo previous move and its cross-out since we are looking for all possible solutions, not just one. Other moves may also lead to solutions.

Q: Good catch. Now can you think of an abstract version of your thoughts? Possibly some pseudo code?

A: OK. So if we are dealing with recursion, we should always think about base case and recursive case. The base case should be that N queens are all on the board. Maybe we should keep track of how many Queens on the board? Or on the second thought, maybe not. Based on my thoughts above, since we are moving to the next row if and only if we can place a Queen on the current row, a solution is found if we are on row N (row index from 0 to N-1). This is the time we stop recursion and return the current board configuration.

```// suppose we call this function solveNQueens

// base case
if (rowInd == N) {
SaveTheBoard(board);
return;
}
```

OK, moving on to the recursive case. I don’t want to repeat myself again so let’s look at some pseudo codes.

```// since we want all possible solution, we should check all possible cells. Therefore we use the loop. Say we are on row K.
for(int i = 0; i < N; i++){
if (isAvailable(board[K][i])){
placeTheQueen(board, K, i);
crossOutCells(board, K, i);
solveNQueens(board, K + 1, N);
undoPlaceAndCrossOut(board, K, N); // always undo
}
}
```

Q: Good. Just one question before we move on to real code. How do you plan to do the cross out and undoCrossOut?

A: Oh I could create a boolean matrix[N][N] and if a cell is crossed out, set the corresponding cell to true. In undoCrossOut just set it to false.

Q: Hmm, not quite. Think about this: A cell C2 on the second row is set to true (crossed out by a Queen on the first row). You place a Queen on the second row somewhere and C2 gets crossed out again (set to true). Later you find that your move on the second row isn’t ideal. You undo the move and C2 is set to false. That doesn’t seem right. Since it can be attacked by the Queen on the first row.

A: Hmm, then I guess I can use an integer matrix then. Every time a cell gets crossed out, we increase the value in the corresponding cell. As long as the value in a cell is greater than 0, it is not available.

Q: Sounds good. Now go on to do some real coding.

Code on github:

Now for the follow up question, it is actually simpler. We don’t even need the board. All we need is just a counter and we increase the counter only in the base case. But sure to return the counter. (The code below mentions a mistake I made about Integer type)

# Sqrt(x)

Implement `int sqrt(int x)`.

Compute and return the square root of x.

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

OK, how hard can this be, right? just find the first integer n such that n * n <= x and (n+1) * (n + 1) > x. Well mathematically this is correct, but if we transfer this idea to a program directly, we may run into the following two problems:

• Time Limit Exceeded (well the OJ has a time limit for this question. O(N) is not acceptable)
• Integer Overflow! It is possible that n*n is greater than the limit of Java integer (from -2^31 to 2^31 – 1).

I was stuck. Then someone on the discussion board mentioned: Think about math back in elementary school. n * n <= x is equivalent to what? Stupid me, n <= x / n. So if we avoid using plus and multiplication in comparison, we can avoid the integer overflow problem using subtraction and division. And I think this idea can extend to other primitive types as well. For something like (a+b)/2 we could re-write as a/2 + b/2.

As for the time limit problem, we can consider two improvements:

• The naive algorithm would go from 1 to x. This is not necessary. We can simply check from 0 to x/2. Why? Because when x > 4, (x/2)^2 is always larger then x.
• Is it necessary that we must go for a linear search? It’s a sorted sequence from 1 to x/2 and we are trying to find a number with a certain property. And this reminds me of binary search.

With these three improvements,  we can solve this question efficiently.

Code on github:

# MergeSort with practical improvement

Well MergeSort is a non-trivial sorting algorithm with time complexity O(NlogN) and space complexity O(N). It has very simple concept with both top-down and bottom-up approaches.

There are some practical improvements according to the book Algorithms, 4th Edition from Princeton University.

• Overhead for sorting small arrays: for array with size less than a CUTOFF value (it is set to 7), use insertion sort instead.
• Before merging: if the largest value of the left sorted half is less than the smallest value of the right sorted half, there is no need for merging.
• can’t remember…

The improved code is on github:

The bottom-up version:

# Binary Tree Postorder Traversal Non-recursive Version

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree `{1,#,2,3}`,

```   1
\
2
/
3```

return `[3,2,1]`.

Note: Recursive solution is trivial, could you do it iteratively?

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

Well the recursive solution is indeed trivial but quite elegant. However, sometimes we may hit a stack overflow exception and that’s why we need the iterative version. To convert a recursive solution into an iterative one, we have to implement our own stack.

So what should we put in our own stack? Think about the recursive version. For example, for each node that does not satisfy the condition of the base case, the function immediately calls on itself with the current node’s left child (if it exists), leaving its right child (if it exists) and its current value unprocessed. So the items going to the stack are nodes that are not fully processed: either its left or right child has not been visited yet.

So the stack is for tree nodes, but we also need to know whether the children of each node have been visited. The original node class does not support this. One simple solution is to wrap the TreeNode class in another class and I call it NodeInfo (it is a private class inside the PostorderTraversal class) and we create a stack of NodeInfo:

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
private class NodeInfo{
TreeNode node;
boolean isLeftVisited;
boolean isRightVisited;

public NodeInfo(TreeNode node){
this.node = node;
isLeftVisited = false;
isRightVisited = false;
if(node.left == null) isLeftVisited = true;
if(node.right == null) isRightVisited = true;
}
}
```

OK, how does this work? Remember that for post order traversal, it has the following order:

• Visit left subtree
• Visit right subtree
• Visit current node

So we can push our root wrapped in NodeInfo object to the stack. Then, as long as the stack is not empty:

• we peek at the top node.
• if the node has left child and it is not visited, set isLeftVisited to true and visitSubtree(left)
• else if the node has right child and it is not visited, set isRightVisited to true and visitSubtree(right)
• else if both children are visited, pop the top node and add its value to an ArrayList solution.

How do we visit the subtree?

while the node is not a leaf:

• push itself to the stack
• if it has unvisited  left child, set isLeftVisited to true and point itself to its left child
• else if it has unvisited  right child, set isRightVisited to true and point itself to its right child

When the loop ends, the node should point to a leaf node so just add its value to the ArrayList solution.

I had trouble at first worrying about visiting only one side of a node in the loop, like we are missing them. But then I realized that all nodes with unvisited children are push to the stack along the way to the leaves so no worries.

Code on github:

# Set Matrix Zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

Well, this is a rather easy question, without the last follow ups. I came up with O(m+n) space solution at the beginning and then struggled with the constant space solution.

The O(m+n) solution:

Get a boolean array of size m (called “rows”) and another of size n (called “cols”), then scan through the matrix. Say matrix[i][j] == 0, then we set rows[i] = true and cols[j] = true, which indicates that row i and column j should be set to zeros.

For the constant space solution, I had two thoughts. They failed, but I think it’s still worth writing down here:

• Maybe we can do this change in place, with recursion (getting too complicated).
• Bit operations. We use two integers rowCheck and colCheck, one for the rows and the other for the columns, initialized to 0. Think about their bit representation. rowCheck should have m bits while colCheck should have n bits. Say row 3 should be set to zeros, then the third bit in rowCheck should be set to 1. The program works fine for almost all test cases except for the last three. I haven’t figure out the reason yet. But it’s just good to know that bit operation is there for us to consider if constant space is required.

So, I peek at the discussion forum and found a great solution:

• For matrix cells that are neither on the first row nor on the first column, an zero in the cell matrix[i][j] means the same as having matrix[i][0] = 0 and matrix[0][j] = 0. So we can simply store the locations of zeros in the first row and first column.
• But what about the cells on the first row and column? If we do the first step above, we are overriding the values and we won’t know if there are any zeros in the first row and column originally. Therefore, we have to check if there are zeros in them first.
• Once the first two steps are done, we can use the info on the first row and column to set zeros in matrix[1:m][1:n]. Do not set cells on first row and column!
• Final step, if there are zeros originally on the first row and column, set zeros in corresponding cells.

Code on github:

# Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

```[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
```

You should return `[1,2,3,6,9,8,7,4,5]`.

(Java Code on Github at the bottom of the post. )

My thoughts and solutions:

I saw a similar problem before about rotating a matrix clockwise for 90 degrees. The standard answer solved it by treating a matrix as several layers of items and process them from the outer layer to the inner layer (I solved it in a different way though). Now I think we can still use this idea here.

What do we mean by layer? For the example above, we have 2 layers.

• Layer-0 contains 1,2 | 3, 6 | 9, 8 | 7, 4.
• Layer -1 contains only one item 5.

Let’s try a few more examples:

```[
[ 1, 2, 3, 4],
[ 7, 5, 6, 8],
[ 9,10,11,12],
[ 13,14,15,16]
[ 17,18,19,20]
]```

In this example, it is a 5 by 4 matrix with 2 layers.

• Layer-0 has 1,2,3 | 4,8,12,16|20,19,18|17,13,9,7.
• Layer-1 has 5|6,11|15|14,10.

Another example with 3 layers

```[
[ 1, 2, 3, 4 ,6, 1],
[ 7, 5, 6, 8, 1, 1],
[ 1, 2, 3, 4, 5, 1],
[ 6, 7, 8, 9, 2, 1],
[ 3, 4, 5, 6, 8, 1]
]```

Two things we can generalize from these examples:

•  for a M by N matrix, the number of layers can be calculated by:
```int smaller = (M < N) ? M : N;
int nLayers = smaller % 2 == 0 ? (smaller/2) : (smaller/2) + 1;
```
• For each layer, we have to go from left to right, top to bottom, right to left and bottom to top. And on different layers, these traverses start and end at different locations but there are rules we can follow. Try out a few examples on different layers and find out that rule: on layer L, we go left to right from matrix[?][?] to matrix[?][?] and we go top to bottom from matrxi[?][?] to matrix[?][?] …

Some corner cases we need to consider:

• when the matrix is empty
• a matrix like this [[1,2,3,4,5]]
• a matrix like this [[1], [2], [3], [4], [5]]
• a matrix like this [[1]]

So in the actual code, we need something to tell us if we are dealing with a one-column or one-row matrix.

• one-column matrix: startLeft == startRight (going from left to right and vice versa is starting at the same location since there is only one column)
• one-row matrix: startTop == startBottom (going from top to bottom and vice versa is starting at the same location since there is only one row)

Summary:

• we can start with normal cases and write pseudo code of it
• but before writing any actual code, think about the corner cases and we may need to change the pseudo code.

Code on github:

# ZigZag Conversion

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

```P   A   H   N
A P L S I I G
Y   I   R
```

And then read line by line: `"PAHNAPLSIIGYIR"`

Write the code that will take a string and make this conversion given a number of rows:

`string convert(string text, int nRows);`

`convert("PAYPALISHIRING", 3)` should return `"PAHNAPLSIIGYIR"`.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

OK, I actually saw a similar question before when I was tutoring a student learning a 100 level class. It was in python and instead of ZigZag, it was called something about building fence blocks. I know this provides no info for solving this problem to whoever is reading this, but I’m just trying to make a point that whatever we’ve done may help us in the future in different ways. So let’s keep trying out new things in our lives 🙂

A good way to solve this question is to play with the example.

Example 1:  “PAYPALISHIRING” and 3

To create the ZigZag version, we go through “PAY”, then “P”, then “ALI”, … till the end. That is to say:

1. scan and process 3 characters
2. scan and process 1 character
3. and repeat the first two steps till the end

Example 2: “PAYPALISHIRING” and 4

To create the ZigZag version, we go through “PAYP”, then “AL”, then “ISHI”, … till the end. That is to say:

1. scan and process 4 characters
2. scan and process 2 characters
3. and repeat the first two steps till the end

Now you can try more examples, but based on these two examples, we can at least generalize the following:

1. scan and process nRows characters
2. scan and process nRows – 2 characters
3. repeat the first two steps till the end

Here nRows have to be larger than 1. If nRows equals 1, we can simply just return the original string.

OK, now how do we process those characters in step 1? Look at the following figure, we see three rows. The first character P is on row 1, A on row 2 and Y on row 3. Each character processed in step 1 ended up in different places. Well, this indicates that we may need nRows number of containers to store the characters.

```P   A   H   N
A P L S I I G
Y   I   R```

What about the characters in Step 2? First of all, we have an order here. Once we are done with characters in the step 1, we should somehow notify the program that we are now in step 2. There’s no difference of how we process these characters between step 1 and 2, except that we should think about in which container we should put these characters.

Say we have nRows containers labeled as 0 to nRows – 1. So the characters in step 1 should be put into container_0 to container_nRows-1 one by one in this order. For those in step 2, they should be put into container_nRows-1-1 to container_1.

Since these are characters, we could use a StringBuilder object as a container. So, we got a basic plan now. We do need to think about some corner cases:

• The string is null or is an empty string
• nRows equals 1
• nRows equals 2 (better to check for this than being sorry later)

And we also need to think about creating variables to indicate whether we are in step 1 or 2.

Code on github:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given `1->2->3->4->5->NULL`m = 2 and n = 4,

return `1->4->3->2->5->NULL`.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well, I did a similar question before, but that experience didn’t come to me immediately. So this is how I proceeded:

1. When I see reverse, I think about the Stack structure.
2. Reversing a linked list does not necessarily mean moving the whole node around. It may just require you to reverse the value in the node.
3. Moving the node somehow to reverse the list.

The question explicitly requires one pass and in-place, so idea No.1 is a no, but still valuable thought for other problems. I moved on to idea No. 2 and I got stuck for while. So maybe it is not the right direction for this question. OK, so move on to idea  No.3. I kept asking myself this question: have you seen it before? Then suddenly something came up: I solved a question of reversing a whole list in-place and one pass before. And this question is just a more general version.

Say we have a list:

N1 -> N2 -> N3 -> NULL

If we reverse the whole list, it becomes:

N3 -> N2 -> N1 -> NULL

OK. to get N1 -> NULL is easy, we just set N1.next = NULL. What about N2 -> N1 ? The same, we set N2.next = N1. Wait! How do we get to N2? Eh, N2 = N1.next. But did we just set N1.next = NULL? So we won’t be able get N2 now, unless we save the reference to N2 somewhere else before setting N1.next = NULL.

```Node current = N1;
Node previous = NULL;

Node nextNode = current.next;
current.next = previous;
previous = current; //previous points to N1;
current = nextNode; //current points to N2;
```

I hope you get the idea. This code snippet should be wrapped in a loop to process the whole list. But knowing this does not make things easier. The corner cases can be tricky and it took me a while to make sure the answer was bug-free. Do it manually, not in any IDE.

Things to check:

• when there is only one node in the list.
• when m = 1
• when m == n

Code on github: