[Java] Find duplicate element in array in constant space and linear time

Sooo.. spoiler alert: this one was way harder than it should be thanks to 0-index arrays.

Given an array of integers in the range 1..N and length N+1 find one of the possible duplicate elements in O(N) time and O(1) space WITHOUT altering the input.

Those constraints are quite strong since finding a duplicate in O(N) time and space is pretty easy: place all elements in a HashSet while iterating over the input and return as soon as a duplicate is found.

Finding a duplicate in O(N log N) time and O(log N) space is also easy: sort the input - using a kickass quicksort implementation otherwise good luck keeping those costs down - and then walk over it comparing elements in pairs until the duplicate is found.

Finding it without destroying the input and without using additional space is also easy in O(N^2) time: for each element, loop over the full array until a duplicate is found.

[Java] Convert expression to reverse polish notation

The closing chapter of my RPN journey, how to convert an infix notation expression to a postfix notation one, so from 3 + 4 we get 3 4 +

Here as well it appears immediately that a String is not the most comfortable input structure, so we stick to an array.
First idea was to scan the input and tokenize it in a left side portion and right side portion for each operator we found:

3 - 4 x 5

would become first:

3, 4 x 5, -

Then finally:

3, 4, 5, x, -

[Java] Evaluate reverse polish notation in constant space

Yes it is possible, yes it took me one full day research included, but the RPN can be evaluated in O(N) time and O(1) space, sacrificing the input in the process.

There are some key points to this but let's start with the general idea. To get the algorithm down from O(N) space (the stack) to O(1) we cannot use additional costly structures; luckily our input is all we need, if we are allowed to destroy it while processing. This is often the case with this type of optimization, an in place algorithm.

Consider the following expression corresponding to 3 - (4 x 5): 3 4 5 x -

For RPN reading from left to right, the operator always follows the two operands it should work on and once we evaluated an expression, we no longer need the original data but only the result, so 3 4 5 x - can be rewritten as 3 20 -

We can therefore recycle the processed space (always 3 elements, two operands and an operator) in the input structure to somehow track which elements should we process next. This means we need to point to the next unprocessed element in the sequence, so that the next operator can retrieve its two operands as if they were adjacent.

[Java] Evaluate reverse polish notation using a stack

Reverse polish notation, aka the WTF! way of writing arithmetical expressions, presents an interesting exercise on stacks.

The goal is to write a program to evaluate RPN expressions eg: 3 4 + would return 7.

The input can be passed in many ways, good candidates are arrays and lists, a stack directly or a string, although in this case, you would need a separator character to understand when does a number start and end.

The idea here is to process the input sequence from left to right without creating the stack beforehand. If we encounter a number (operand), we push it onto the stack and when we encounter an operator, we pop two items from the stack, then apply the operator in the (gotcha!) REVERSE order because the stack is LIFO and this matters for the asymmetrical operations such as - and /

An interesting note, dividing by 0 a double will NOT throw an exception, we must test if we got infinite as result!

For the implementation I use a String array as input and a Double stack to allow decimal results. Only the four basic operations (sum, subtraction, multiplication, division) are supported, but the code can easily be expanded to support more and even unary operations (pop one item instead of two).

As last note: why can't we do this in constant space while parsing the string itself? Because of situations such as: 3 - (4 x 5) which translates to 3 4 5 x -

Therefore we cannot expect an operator to always follow two operands.. So: String as input = bad.

The current implementation therefore uses O(N) space and time. But you can check here for an implementation that uses O(N) time and O(1) space!

You can check the implementation on my Gist along with some test cases in RPNJTests.

You can find here the code to convert an expression to reverse polish notation.

[Java] Generate string permutations recursively

Ahhhh, string permutations. The timeless classic. Also painfully slow with its O(N!) time and space complexity. Let's put a twist on it and do it recursively just because we can.

Also, just because we can, we use StringBuilders instead of Strings. Is this a good idea? Is the cost of creating lots of StringBuilders offsetting the cost of creating a new String object everytime? That's what method timing is for, we'll leave this as "exercise" for the reader.

Anyway, enough introduction, let's go to the meat: we call a recursive method which will have as input the size of the result string to create, the string we built so far, the string of unused characters so far and the output collection.

Then, for each unused character, we add it to the current string and recurse on the remaining ones leaving that out. The base case is when we no longer have characters to use; if the string we built is the correct length, we add it to the result set and return, otherwise simply return.

Note: StringBuilder.deleteCharAt alters the source directly instead of returning a new object, therefore calling this method as StringBuilder(x.deleteCharAt) and StringBuilder(x).deleteCharAt makes quite the difference!

You can check the implementation on my Gist along with some test cases in PermutateJTests.

[Java] Zip singly linked list

List zipping means interleaving the list nodes from the top and bottom of a given list to create a new list.

Eg with this input list:

A -> B -> C -> D

the zipping is:

A -> D -> B -> C

Doing this in constant space and quadratic time is trivial, but there is a better solution that avoids scanning the list every time with two pointers running one ahead of the other to find the current last element in the list.

Again as with most linked list problems, the correct handling of the pointers is the trickiest part. The idea is to spend some time to preprocess the list in O(N) time to split it in two halves, and reverse the second half; this way, we now simply need to walk both lists and interleave the nodes in order to produce our result.

[Java] Reverse singly linked list

Here is a simple algorithm to reverse a singly linked list in O(N) time and O(1) space. The only tricky part is the correct handling of the pointers :)

The idea is to start with a previous pointer to null and a pointer to the head of the list, then:

1) track the next element in a temporary variable
2) reverse the current element pointer
3) consider the current element as the previous for next iteration
4) move the current element to the next one to handle
5) when no more elements are left to be processed, the previous pointer will be the new list head

 //reverse singly linked list  
 public static SingleLinkedListNode reverseList(SingleLinkedListNode head){  
   if(head == null) return head;  
   
   SingleLinkedListNode prev = null, next, curr = head;  
   
   /*  
   1) track next element  
   2) reverse current element pointer  
   3) track current element as previous for next iteration  
   4) move current element to the next one to handle  
   */  
   while (curr != null) {  
     next = curr.next;  
     curr.next = prev;  
     prev = curr;  
     curr = next;  
   }  
   
   //at this time this will point to the beginning of the reversed list!  
   return prev;  
 }  

You can check more singly and doubly linked lists utilities on my Gist along with some test cases in SingleLinkedListJTests.