[Java] Reverse integer

Given a 32 bit integer, reverse it.

Example:

123 becomes 321

The initial thought was to treat the integer as a bit array, swapping each from left to right.

This would have some tricks in the implementation, especially since Java uses 2's complement for negative representation, but could be done and has a complexity of O(32) at most as we consider each bit in the number.

However, turns out there is a much better approach that uses divide and conquer logic to achieve the same result:

 public static int reverseBits(int n){  
     //take half of the bits from MSB to mid portion  
     //take half of the bits from mid to LSB portion  
     //swap them  
     //repeat the process with always smaller masks and portions  
     //mask is always 32 bit in size  
   
     //initial swap, throw away 16 LSB and 16 MSB, combine them together  
     //now we have the two halves reversed  
     n = n >>> 16 | n << 16;  
   
     //mask for left portion: 1111 1111 0000 0000 1111 1111 0000 0000  
     //mask for right portion: 0000 0000 1111 1111 0000 0000 1111 1111  
     //then shift by half of previous size (8 bit)  
     n = (n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8;  
   
     //mask for left portion: 1111 0000 1111 0000 1111 0000 1111 0000  
     //mask for right portion: 0000 1111 0000 1111 0000 1111 0000 1111  
     //then shift by half of previous size (4 bit)  
     n = (n & 0xf0f0f0f0) >>> 4 | (n & 0x0f0f0f0f) << 4;  
   
     //mask for left portion: 1100 1100 1100 1100 1100 1100 1100 1100  
     //mask for right portion: 0011 0011 0011 0011 0011 0011 0011 0011  
     //then shift by half of previous size (2 bit)  
     n = (n & 0xcccccccc) >>> 2 | (n & 0x33333333) << 2;  
   
     //mask for left portion: 1010 1010 1010 1010 1010 1010 1010 1010  
     //mask for right portion: 0101 0101 0101 0101 0101 0101 0101 0101  
     //then shift by half of previous size (1 bit)  
     n = (n & 0xaaaaaaaa) >>> 1 | (n & 0x55555555) << 1;  
   
     //now all the bits have been moved around in the reverse place  
     return n;  
   }  

The idea is to split the integer in two halves, shift them by half the size of the integer, and combine them back.

Repeating this process on each half will in the end give the desired result.

[Java] Find missing integer in array of unique elements

Given an array of length N of unique positive integers in range 0..N both inclusive, find the missing one.

We have two linear approaches, one uses a mathematical formula, the other some bit magic.

Math:

all numbers in range 0..N summed up can be calculated with the formula:

N * (N + 1) / 2

If we sum up all elements in the array, our missing number is the expected sum minus the actual sum

Bit:

if the array was of size N + 1 and all integers in range 0 .. N were present and sorted, each would sit at the index same as the number itself, for example:

idx: 0 1 2

num: 0 1 2

Since we know only one number is missing, there must be some index where the value doesn't match the index.

Since N + 1 is NOT a valid index in the array, we can initialize a variable to that, then XOR that variable with all values and indices in the array.

All repeated elements (index and value) would cancel out, leaving only the missing one as result.

You can check my implementation of findMissingNumber on my Gist (math) and Gist (bit) along with some tests in FindMissingNumberJTests (math) and FindMissingNumberJTests (bit).

[Java] Count number of bits set to 1

Given a positive integer N, find for each integer in range 0..N inclusive, how many bits are set to 1.

We could for each integer in range 0..N consider its binary representation and pick off all bits set to 1 counting them.
This would make us do at most 32 operations for each number, being 32 a constant we'd have linear time but performance is still impacted.

We can however reuse information we stored earlier (especially in this case it's part of our answer anyway)
Drawing the binary sequence for 0..8 gives us:

• 0: 0000
• 1: 0001
• 2: 0010
• 3: 0011
• 4: 0100
• 5: 0101
• 6: 0110
• 7: 0111
• 8: 1000

And we notice that N and N*2 have exactly the same amount of bits set, just shifted left one position, example:

• 3 and 6
• 2, 4 and 8

What is left out is odd numbers like 5 and 7. But in that case, it's just about setting the lsb to 1 from the previous number, example:

• 5 = 4 + 1
• 7 = 6 + 1

so to create an odd N, we can simply start from N/2, shift it up one position AND check if we should set the lsb to 1 in this new number.
 

If we know how many bits are set in N/2, we skip all of this process and just reuse that value adding one to it if the lsb should be 1. We know if it should be 1 by checking N & 1.

This is also equal to saying number of bits set in N is N/2 + N mod 2 as anything modulo 2 will always be either 0 or 1, specifically 0 if N is even and 1 if N is odd.

We repeat this process for all numbers in our range and we have the solution.

Since the output is part of the solution, our space complexity is O(1) and our time is O(N).

All operations we use are division by 2 and modulo by 2, which are a right bit shift and a bitwise AND.

You can check my implementation of countOnes on my Gist along with some tests in CountOnesJTests.

[Java] Sum two integers without sum operator

Given two integers, return a + b without using sum operator.

Seems like it's time for more bit magic. 

We process our numbers bit by bit starting from LSB, we track a carry, a position in the result sum, and the result sum.

Getting the LSB can be done by:

n & 1

If 1 the bit was set to 1

Then we can calculate the result of the sum:

it will be a 1 only if there is an odd number of ones between lsbA, lsbB and carry:

• 1 + 1 = 0, unless carry was 1
• 1 + 0 = 0, unless carry was 1
• 0 + 0 = 0, unless carry was 1

res = lsbA ^ lsbB ^ carry

Then we can push that bit in the correct place in the final result:

res = res << position

And set it in the final sum:

sum |= res

Also we need to increase position for the next iteration, but we can't use sum operator:

position = -(~position)

We can then calculate the carry for the next iteration:

it will be a 1 if there were at least two ones between lsbA, lsbB, carry:

• 0 + 1 + 0 = 1 no carry
• 1 + 1 + 0 = 0 with carry
• 0 + 0 + 1 = 1 no carry
  
• 1 + 1 + 1 = 1 with carry 

carry = (lsbA & lsbB) | (lsbA & carry) | (lsbB & carry)

we then drop the lsb from both a and b WITHOUT preserving sign (we need it come to us for processing, we can't leave it set in MSB):

a = a >>> 1

b = b >>> 1

and repeat this process until both a and b are 0

One last thing to do after all of this, if there was still a carry left AND we are not trying to set it in position 32 (MSB), set it in the final sum.

You can check my implementation of sum on my Gist along with some tests in SumJTests.

[Java] Increment number without using sum operator

Here's another piece of bit magic that works on those systems where numbers are stored using 2's complement.

Since a negative number is stored using that form, and that form is obtainable by inverting all the bits then adding one, we can get the number + 1 by inverting all bits first and then flipping its sign:

n = -(~n)

This works for both negatives and positives.

[Java] Find all paths from source to dest in a directed acyclic graph

Given a DAG, find all paths from source to target.

Since it is a DAG, there are no cycles, therefore we can't go back to an already visited vertex during a visit.

We can therefore add the source to a stack, then use recursion to find all paths from source to target.

In the recursive function, we look at the current node (top of stack) and for each one of its edges, we add the destination to the stack and call recursion on that destination.

When the top of stack is the target, we scan the scan and track all elements as a solution, they will be in inverted order from last vertex to first. However, a foreach loop on a Stack (in Java) gives element in order from bottom to top, so there is no need to invert them in our result.

When we get back from a recursive call, we remove ourselves from the stack as we have fully explored our subgraph.

This code works in O(V) space as that's how deep the recursion could go, and our stack also matches the recursion in size.

For time complexity, I assumed we would get a O((V+E)^2) upper bound as without cycles we cannot go back to previously visited vertices but some paths might overlap and we would walk down the same edge multiple times.

This might not be the case if we look for ALL paths from ALL vertices, however we only consider ONE start vertex in this case.

I think it made sense as a similar problem which is topological sorting is linear and in this case we're looking at all paths between the two farthest nodes.

Turns out it's exponential in reality:  If all vertices are connected (without cycles) for each new node excluding start and end, we have a choice of either including it in a path or not, which would give a O(2^V) upper bound.

You can check my implementation of findAllPathsFromSourceToDestInDAG on my Gist along with some tests in FindAllPathsFromSourceToDestInDAGJTests.

[Java] Find index in circular array so that rolling sum never falls below zero

The title is actually a simplification of the following problem:

given a car with unlimited fuel capacity, an array indicating the amount of fuel that can be put in the car at a specific city i and another array indicating the amount of fuel necessary to travel from city i to the next, return the index of any city that allows making a round trip passing through all other cities in the order they appear.

Example:

gasAtCity = 1,1

gasForNextCity = 1,1

Any index is correct, start at city 0 we will the tank with 1 unit of fuel, we spend 1 unit of fuel and reach city 1 with 0 fuel left. We fill the tank there with 1 unit of fuel, spend 1 unit of fuel to go to the next city which bring us back to the start and end our journey.

gasAtCity = 1,1

gasForNextCity = 2,2

No city is correct since no matter where we start, we won't ever have enough fuel in the tank to reach the next city.

gasAtCity = 1,1,2

gasForNextCity = 1,2,1

Start from last city is the only possible choice as starting from earlier places will leave us at some point with not enough fuel to continue the trip.

[Java] Find minimum in rotated sorted array of unique elements

We've seen how to search for an element in a sorted array of unique element, which was rotated an unknown amount of times.

Now we want to find the minimum element in that array.

The approach is the same, however the minimum element can be in two places:

• at the beginning, if the array was not rotated of rotated enough times it went back to its initial state
• somewhere in the array AFTER a BIGGER element than itself

We can therefore do a binary search testing for this condition: which adjacent elements are such that the first is bigger than the second. When we find that pair, the second element will be the smallest.

This is because the array has unique elements and was sorted, therefore there is only one place where this pair exists and it's where the last and first meet.

If we view the array as a circle, a sorted array as last and first meeting at the very borders.

At each iteration of the search we have the following cases:

• a[mid] > a[mid + 1]: the smallest is in mid + 1
• a[floor] > a[mid]: a rotation happened and the split point will be on the left side, ceil = mid - 1
• otherwise the rotation is somewhere on the right, floor = mid + 1

This code runs in O(logN) time and constant space.

You can check my implementation of minimumRotatedSortedArray on my Gist along with some tests in MinimumRotatedSortedArrayJTests.

[Java] Max subarray product

Given an array of integers, find the maximum subarray product. The product of all elements in the array is guaranteed to fit in an integer.

Example:

-2,0: return 0

-2,20,-1: return 40

1,2,3: return 6

[Java] Eulerian path that covers all edges

Given a list of flight tickets and a start airport, find if possible an itinerary that uses all tickets. If there are more such itineraries, return the earliest lexicographically sorted one.

Example:

a,b - c,d start at a: there is no path

a,b - a,c - b,c - c,a start at a: return a,b,c,a,c since it's alphabetically earlier than a,c,a,b,c

This exercise is a bit simpler since we are given the start vertex and it's asking us to find a Eulerian path for the given directed graph.

The complexity for that would be O(E) where E is number of edges as we tray to visit each at most once and either we'll find a path or not.

However we are asked to return the earliest lexicographically sorted path, therefore when choosing a next vertex to visit, we can't pick any edge as we would normally do, but need to choose the earliest one.

This can be done by sorting the edges first, bringing the total time to O(E log E). Using an adjacency list, we could replace the list with a PriorityQueue instead to have this done for us while building the graph.

We can then have a map with key = vertex, value = priority queue to track our graph.

The idea then is to do a DFS and start from the source and:

• remove the next vertex from the queue of destinations of this vertex
• if the queue is now empty, remove the vertex from the map, otherwise, update map for this vertex to reflect having followed this edge
• call recursion of next vertex

When the queue of destinations for a vertex is empty, we can't progress further from that vertex, so we add it as HEAD of our result path

When we return from the initial call, we have one check to do: the adjacency list of all vertices must be empty (we were removing edges while doing DFS) as we want to have visited all edges.

If that is not the case, there was no path, we return an empty list.

You can check my implementation of eulerianPath on my Gist along with some tests in EulerianPathJTests. 

I have also added optional code that would perform the check whether a path exists and would help in finding a potential start and end vertices in case they were not given.

[Java] Longest increasing subsequence

Given an array of integers, find the longest increasing subsequence. If there are more, find any.

[Java] Calculate nth root

Given a number, calculate the nth root within a certain precision epsilon.

Without using square functions, we need to approximate the result ourselves.

We could start from epsilon, calculate the nth power of it, then verify whether it differs from the given number by at most the given epsilon.

If yes, we have our result, otherwise, we increase our start value by epsilon and repeat.

This can be done iteratively in constant space but has a terrible time complexity O(all possible numbers between epsilon and N with precision epsilon).

We can improve on this by using binary search as in the end we're looking for a value within a range.

We set our floor to 0 and our ceil to N, then our mid point is at each time the candidate for our nth root.

We multiply mid with itself to calculate the nth power, and verify if we're within epsilon of the given number, which means we have found the root.

If not, we check whether we overshot or undershot and set ceil or floor respectively to mid. We do NOT use mid plus or minus something since we're dealing with doubles and any fluctuation might lead to a wrong result.

Additionally mid is the midpoint between floor and ceil, and since we're dealing with floating point values it's guaranteed it will never be equal to either bound (unless we have reached the minimum possible precision of the double type).

The complexity now is O(log all possible numbers between 0 and N with precision epsilon) which is much better than before.

Space complexity stays the same since we're doing the iterative approach.

You can check my implementation of nRoot on my Gist along with some tests in NRootJTests.

[Java] Disjoint array partition

Given array of positive integers including zeros and duplicates, partition it in portions left and right such that every element in left is smaller than every element in right. Keep left as small as possible.

Example:

1,2,3 partition 1 - 2,3

3,2,1 partition 3,2,1 - empty

1,1,0,3,2 partition 1,1,0 - 3,2

1,1,3,2 partition 1 - 1,3,2

Looking at our examples, we can solve this in O(N) time and space by keeping track of the following information:

• minimum so far of all elements from right to left
• maximum so far of all elements from left to right

This is because we can notice that for each position from left to right we want to break there (and therefore generate the smallest partition) only if max at that position is less than or equal to min at the next position. 

In that case, every element BEFORE us (including us) will be less than or equal to every element AFTER us, satisfying the given condition.

We can improve slightly on space by noticing we don't need to remember max values, but only need the last one, so we can replace the max array with a variable.

We still need the min array though, for example: 

5,0,3,8,6

if we tracked only 0 as min, we would break at the end of the array since max until there is never less than 0.

By checking against the min value at the next position though, we break on 3, which is the correct answer. 

You can check my implementation of disjointPartition on my Gist along with some tests in DisjointPartitionJTests.

[Java] Simple regex matcher

Given a simple regex that allows characters, dots and stars, find if a given text matches a given pattern.

dot '.' = any character

star '*' = 0 or more repetitions of previous character

We have already seen a slightly more complex regular expression matcher which does a similar thing but I realized that matcher did NOT use caching.

The complexity becomes exponential due to the behavior of star, since "0 or more" means we have a choice: match on this char and continue with same pattern or keep this char and continue with next piece of pattern.

For example:

text = abbbb

pattern = ab*b

Due to this possible choice, our complexity is O(2^N) for both time and space.

We can cache however the pairs (index of text char, index of pattern char) where failed to find a match, so that for repeated patterns example:

text = abbbb

pattern = ab*b*b*.*.*b

When we reach a portion that we already investigated in the past, we skip it and continue

This uses O(N^2) space and O(N^2) time as we check each pair once. 

We have to be very careful in our base cases:

text = "", pattern = "" is a match

text = "", pattern = ".*" or any char followed by star or any sequence of chars followed by stars (.*b*n*), is a match

text = "", pattern = "." or any sequence, is not a match

text = anything, pattern = "", is not a match

We therefore find the following cases:

• pattern is not a star: try matching with text and continue if successful
• pattern is a star: branch options (1) match on this char and continue on next char with same pattern or (2) stay on this char and continue on next char in pattern

If we encounter a failure when doing any of these inspections, we cache it

If at any point we can make a successful match, we stop and return true.

You can check my implementation of regexMatch on my Gist along with some tests in RegexMatchJTests.

[Java] N queens

Given a NxN board and N queens, count how many placements exist where no queen blocks another.

This is an extension of a problem known as eight queens, which feels like dynamic programming, but is slightly different from the usual approach of finding a recursion, then caching.

The reason is that the solutions are NOT incremental. Finding a solution for a smaller N is NOT expanded to a bigger N, therefore we can't reuse already computed work. And usually when we do DP, we cache something, but in this case there is no possibility.

[Java] Collect all nodes at given depth in binary tree

Given a binary tree, return all nodes at a given depth.

We could do a level traversal with a queue BFS style, adding markers in the queue to determine when a new level is reached. Once we arrive at the desired level, we add all nodes between the current marker and the next to the solution.

Complexity is O(N) time and space in worst case. Although for BFS space worst case happens when tree is balanced (all nodes at a certain level are added to the queue).

We can also do DFS which has O(N) time and space complexity again, but worst case for space in DFS is when tree is a branch (call stack is the whole tree).

If we do BFS we can iteratively collect the result, if we do recursive DFS, we need to pass in input a structure where we will collect the result.

The order of elements in the result can be controlled by deciding whether to move left or right first.

You can check my implementation of getAllValuesAtDepth on my Gist along with some tests in GetAllValuesAtDepthJTests.

[Java] Subset of sum K

Given an array of positive integers, with possible duplicates, find if a subset exists whose sum is a given target.

Example:

1,2,3 target 3 result = {1,2} or {3}

1,2,3 target 5 result = {}

This is clearly a dynamic programming problem, however I think the approach of using a matrix as cache makes it a bit harder to backtrack to a valid solution.

[Java] Reconstruct sentence from text - word break

Given a string representing a text and a dictionary of words, return a possible reconstruction of a sentence built by breaking off the given text using whitespaces to separate valid words.

Example:

text = "bedbath", words = {bed, bath} return "bed bath"

text = "bedbath", words = {bed} return ""

My initial idea used a Aho-Corasik trie which I though would give a linear time solution by greedily matching longest prefixes, then falling back to shorter ones while walking on the string.

This is partially true unfortunately as it works when prefixes are contained within each other, however it fails when the last character of a word is the start character of another word, and we have a fail link between them.

In that case, we would incorrectly assume we have matched two words (technically true) but in reality we matched two substrings. The shared character cannot be used for both words.

Example: text = "catsand", words = {cats, sand} return ""

If we match until "catS", then we can't continue, however we can follow the fail link to root and continue on the "S" edge for "Sand". We mistakenly assume that "S" appeared twice.

So it's fallback to DP, where we apply a similar approach to the trie matching BUT we break off any valid word we encounter and continue matching from the NEXT character onward.

Therefore for each character in the string, we have two choices: break off a word here (if the current suffix forms a dictionary word) or expand the current suffix and break later.

This translates to a O(2^N) time solution. We can however use O(N) cache space to bring the cost down to O(N^2) if we cache the indexes from where we have found in the past that no valid break can be made. This means we explore all pairs of prefix-postfix once.

If we want to reconstruct the sentence and not just return a boolean saying whether the break can be done, we can use StringBuilder objects to track the matched words up to a certain point, discarding their content if we reach a failure node or appending if we can progress with the matching.

In the end, we will have the text that is broken down to the shortest words possible to make it.

Example:

string = aaab
words = a, aa, aaa

recursion tree looks like:

                        aaab
           a,0            aa,1                aaa,2 

       a,1    aa,2         a,2                  b,3

a,2            b,3          b,3

b,3

Where we start from the whole string and for each matched suffix (a dictionary word) we break off at the current index and explore from there.

As you can see we have many repeated calculations, which we can cache.

You can check my implementation of reconstructSentence on my Gist along with some tests in ReconstructSentenceJTests.

[Java] Count out of order pairs in array

Given an array of unique integers, count all out of order pairs. A pair of elements is out of order if its position in the array is less than the position of the other element, but its value is bigger.

In short, count the pairs that have the first element bigger than the second, in the order that the elements appear.

A first attempt to solve this problem in complexity better than O(N^2) gave a O(N^2) solution due to a data structure limitation.

[Java] Find deepest node of tree

Given the root of a binary tree, find any of the deepest nodes.

This problem is similar to finding the depth of a tree, only this time we collect a pair (node, depth) and when we recurse on each node, we pick from it the node that was deepest among the two left and right children.

We can do this in O(N) time and space worst case (tree is a branch).

You can check my implementation of getDeepestNode on my Gist along with some tests in GetDeepestNodeJTests.

[Java] FourSum

Similar to ThreeSum, but this time we need to find all unique quadruples that sum up to a given target.

I think if we were required to only count all possible quadruples, we could do this in O(N^2) time and space, but finding all unique quadruples means discarding already used elements and since our array can contain duplicates I think O(N^3) is what we can do.

We use a class Quadruple that stores four integers, we also define a hashCode and equals so that if all elements in different quadruples are same, no matter in which order they appear, then we consider the quadruples same.

I thought about XORing all values in both objects, then ANDing them and check if result is 0, but negative elements are allowed, therefore we get a wrong result (at least in Java with the 2's complement representation of negatives). I ended up adding elements of both objects to two sets, then comparing the sets for equality.

The approach to solve the problem is scanning the array in O(N^2) time to generate all sums of two elements, and track them in a map where the key is the sum and the value is the list of all pairs with that sum in the form (element1, element2, index1, index2).

This also gives O(N^2) space usage.

Then we scan again the array and for each pair we check if the map contains the complement we need: target - sum of pair.

If it does, we scan the list of pairs to remove duplicates (other pairs that have at least one index in common with the current pair), then add the result to the output only if we have not seen that quadruple already (store it in a set).

Total time is O(N^3) and space is O(N^2).

Of critical importance is the implementation of hashCode and equals for the Quadruple class since the set will deduplicate ONLY if it can verify equality.

Maybe an approach similar to the second option of threeSums where we sort the array first, then do the two nested loops with a third loop on the remaining portion of the array could give O(N^2) time if we still use O(N) or O(N^2) extra space, but I couldn't figure it out.

You can check my implementation of fourSum on my Gist along with some lazy tests in FourSumJTests.

[Java] Buddy strings

Given two strings, check whether exactly ONE swap of two different characters can be made in any string to form the other.

Example:

abc,abc: false

asd,jkl: false

aa,aa: true

ab,ab: false

ab,ba: true

The main issue is that we FORCE a swap, even if strings are equal already.

After checking for string length which must be at least 2 and both must have same length, we can walk both strings at the same time, counting number or unmatched characters. 

If we ever have more than 2 mismatched characters, we stop and return false as we can only swap two characters at most (eg: asd,jkl), otherwise we track the indices of the mismatched ones.
 

Also we check if a string has any duplicate characters, this is necessary as we MUST perform a swap, even if the strings are equal. Therefore we need to have the possibility to do a harmless swap between two duplicates (eg: aa,aa is ok but ab,ab is not).
 

At the end we have the following cases:

• no unmatched chars found: we must force a swap between duplicates, if there are any
• one unmatched char found: we cannot swap it with anything
• exactly two unmatched chars found: we need to verify whether the two strings have matching chars at the inverted indices so we can swap them

This will work in O(N) time and space.

You can check my implementation of checkBuddyStrings on my Gist along with some tests in CheckBuddyStringsJTests.

[Java] Break palindrome

Given a palindrome string, change any character in order to form the lexicographically earliest non palindrome.

Example:

"a" return ""

"aa" return "ab"

"aba" return "abb"

We have two options: change an initial 'a' character in the first half (excluding middle point) or change a last 'a' or 'b' character in the second half (excluding middle point).
For odd length palindromes, changing the middle point will still yield a palindrome, so we must skip the midpoint. For odd length palindromes, the middle point is in between two chars, so we're good.

If first half of the string is all 'a', then changing any might give a non palindrome, however it won't be the lexicographically earliest, example: 'aa' could give 'ba' but the earliest is 'ab'

This means, if we can't change any 'a' from the left side, we must change the last char from the right to either 'a' or 'b' and will be left with the solution.

The only case where we can't give a solution at all is if the string only has one character, which is always a palindrome.

We can do this in O(N) time and space. The time is actually O(N/2) worst case, but we need to generate the new string, which requires us to copy the input somewhere where we can edit it, which costs O(N).

You can check my implementation of breakPalindrome on my Gist along with some tests in BreakPalindromeJTests.

[Java] Subarray of sum K

Given an array of integers with duplicates, negatives and zeros, find a subarray that reaches a target sum.

The sum must be formed by at least two elements.

Example:

2, -1, -2, 5

target 5, no result

target -3, one result: -1,-2

The linear time approach builds upon this observation: having the rolling sum (prefix sum) for each position, if at any point the current sum - target results in an already seen sum, it means there are two subarray sums whose difference is exactly K, which implies there is a subarray whose sum is exactly K.

We can see the current sum as every element from the first to the current element and wonder whether we can use any previous sum (which is contained in the current one) to calculate the middle portion between that sum and the current index.

This however could be a single element, therefore we can't use a simple Set to track this information. If we use a Map instead to store pairs: sumAtIndex, Index we can then easily check whether the subarray we would consider as result has at least two elements: index - indexOfSum must be greater than 1.

Specifically:

if currentSum (curr) - K = any of the previous prefix sums (other), there is a subarray between other and curr whose sum is K.

To avoid the case where the first element is equal to K, we must initialize the map to (0, -1).

It took a while to visualize this, in our example with K = -3:

• get 2, rolling sum is 2 check 2 - K = 5 which is not in the map, put current sum in map and continue

current subarray sum is made of elements: 2

map = (0,-1), (2,0)

• get -1, rolling sum is 2 - 1 = 1, check 1 - K = 4 which is not in the map, put current sum in map and continue

current subarray sum is made of elements: 2 , -1

map = (0,-1), (2,0) , (1,1)

• get -2, rolling sum is 1 - 2 = -1, check -1 - K = 2 is in the map

current subarray sum is made of elements: 2 , -1, -2. We have the sums of subarrays (2), (2, -1) stored.

Could we remove any of those sums to retrieve the sum of elements between those subarrays and ourselves? Yes in O(N) time, but we don't need to check all of them as we are only interested in knowing whether any subarray in between sums up to K so we can approach it from the opposite direction. If we remove K from the current sum, we are deleting (if any) a subarray in the middle whose sum is K.

If that subarray existed, we sould reach a prefix sum we've already seen. In this case from current subarray sum (2, -1, -2) we remove K (-3) which corresponds to subarray (-1, -2) and are left with sum of 2 which was subarray (2). Therefore between (2) and current index we had (-1, -2) which is our answer.

We just need to check if that subarray is formed by more than one element:

index of sum 2 is 0, current index is 2. 2 - 0 is greater than 1 so that subarray contains at least two element, we can stop.

You can check my implementation of subarrayOfSumK on my Gist along with some tests in SubarrayOfSumKJTests.

[Java] Binary search on rotated array

Given an array of unique items, which was sorted and then rotated an unknown number of positions left or right, find whether an element exists in the array in O(logN) time.

We can do a normal binary search, but each time we need to understand where to continue searching.
Given a middle element, either the left or right side will be sorted and the other side not as there will be at least one element whose successor is not in order, unless array is all ascending or mid is the break point.

After checking the middle element, we look at both sides to determine where the item would be and move  in the correct direction:

• element at floor < element at mid: left side is sorted

if element at floor <= target < element at mid, search there, otherwise search on the right of mid

• otherwise left side is not sorted

if right side is sorted (element at mid <= element at ceil) AND element at mid < target <= element at ceil we search on right side of mid, otherwise search on left side

You can check my implementation of rotatedBinarySearch on my Gist along with some tests in BinarySearchRotatedJTests.

[Java] Find the next bigger number using same digits

Given a number, find the next number which is bigger than the given one and has the same digits.

Example:

9876 - no next exists

6789 - 6798

8276 - 8627

We first need to convert the number to an array for digit manipulation, we can convert it first to a string and then to the array.
Then, we need to identify (if any) a digit that can be swapped in another place. If it exists, it will be the first digit from the right which is smaller than the next digit.

Example: 9876
has no valid digit since that is already the biggest number that can be made with those digits, notice all digits are in decreasing order

Example: 6789
the first digit smaller than the next from the right is 8, we can use it to make 6798 which is the next bigger number than 6789 using same digits

But simply swapping two digits is not enough, example: 8276, a swap would give 8672 which is bigger but not the next, that would be 8627.
We notice that after the swap, the rest of the digits on the right of the swapped one are sorted in increasing order.

If we do that, we have our answer, this reordering can be done in linear time since in the first portion we stop as soon as we find an element that breaks the increasing sequence right to left.

If there was no such element, we are in the first example where no next number can be built.

Complexity is O(N) for both time and space.

You can check my implementation of smallestBiggerNumWithSameDigits on my Gist along with some tests in SmallestBiggerNumWithSameDigitsJTests.

[Java] Test if binary tree is symmetric

Given a binary tree, check whether it is mirrored along a line that runs across the root.

By drawing an example we can deduce what is the recursion to apply:

   1

  2 2

4 3  3 4

We notice that a single node is always mirrored. Given two nodes, children of nodes at a previous level, they are mirrored only if they have the same value and their subtrees are identical, but swapped left and right.

We can do this recursively in O(N) time and space.

You can check my implementation of isMirrored on my Gist along with some tests in IsMirrorJTests.

[Java] Generate power set of set

A power set is the set of all possible subsets of a set. For example for {1,2} it is {{}, {1}, {2}, {1,2}}

It contains 2^N elements.

We can use DFS recursion to generate it, removing one element from each subset we generate at each step, skipping repeated sets.

This can be done in O(N) space (we won't add more than N calls on the stack) and O(N 2^N) time since there are 2^N sets to generate AND everytime we create a new set we need to copy over all its elements in a NEW set.

You can check my implementation of generatePowerSet on my Gist along with some tests in GeneratePowerSetJTests.

[Java] Simplify unix path

Given a string representing a unix path, simplify it to remove dots and repeated slashes, condensing only to the folders appearing in the final path.

Example:

/../ return / as we can't move up from root

/asd/../lol return /lol as we went into asd, then moved out from it

We can do this in O(N) time and space by using a queue.

We first split the string over the "/" character to separate all folders and special characters.

If there are repeated slashes together (eg "//") the split would return an empty string for them.

We then loop over all strings in the split and check the following cases:

• encounter a single dot "." or an empty string "": we skip this as the dot means "stay in this folder" and the empty string means we had consecutive slashes
• encounter a double dot "..": if the queue is not empty, we remove from the tail the last folder we added as we just moved out of it
• in all other cases, we have a folder name, we add it to our queue

Then, we can recreate the path by appending all elements in the queue together

This won't be O(N^2) since removing from the queue at most will make us walk the whole string twice (we can't remove more than we add).

You can check my implementation of simplifyPath on my Gist along with some tests in SimplifyPathJTests.

[Java] Toeplitz matrix

A matrix is called toeplitz matrix if all element along the left to right diagonals are same.

Given a matrix, test whether it is a toeplitz matrix.

We can verify the given condition with two consecutive loops. The first will check all diagonals for the first row starting with the previous to last element until the first of the row.

The last element of the row is on a diagonal with itself, therefore there is nothing to check.

We repeat the process for all diagonals for the first column starting with the second element until the previous to last. The first element was already checked as first element of the row at the previous step, and the last element again is on a diagonal with itself.

We can do this in O(NM) time and constant space.

You can check my implementation of isToeplitz on my Gist along with some tests in ToeplitzMatrixJTests.

[Java] Maximum product of three elements in array

Given an array of integers with possible duplicates, negatives and zeros, find the largest product that can be made using three elements in the array.

We notice that if the array was sorted, we would have the smallest (possibly negative) elements at the beginning and the largest (also possibly negative) at the end.

Given an ordered sequence of elements, we can find the largest product in two ways:

• pick the 3 largest elements and multiply them together: if they are all positive, that is the maximum achievable. If one is 0, it's also the maximum as all other elements would either be 0 or negative, giving a smaller value than 0. If all are negative, the result would be the biggest negative number that can be made by multiplying those elements.
• pick the 2 smallest and the largest and multiply them together: this is to consider the case where the smallest elements are both negative and their multiplication would return a positive, multiplying them with the biggest will yield the largest product for those three elements

By choosing the biggest of those two, we have our answer. This could be done in O(N log N) time and space for sorting.

But we then notice that all we need are 5 elements: 3 largest ones and 2 smallest ones, we can simply create 5 variables and scan the array in one pass in O(N) time and constant space to track those elements to achieve the same result.

Careful: the if conditions to decide which elements to track must be chained together otherwise you might propagate the largest/smallest element everywhere.

You can check my implementation of maxThreeProduct on my Gist along with some tests in MaxThreeProductJTests.

[Java] Find all pairs with difference K in array

Given an array of unique integers and a target K, find all pairs of elements that satisfy the formula X - Y = K

The output should preserve the order of elements for Y. Example:

0,-1,1 target 1 result: (1,0), (0, -1)

We can add all elements to a set, then walk the array again and consider each element as the Y in the equation.

We then check if the complement X = K + Y is in the set, and if so, we add it to the output.

We can do this in O(N) time and space.

You can check my implementation of pairsWithDifferenceK on my Gist along with some tests in PairsWithDifferenceKJTests.

[Java] Binary tree right side view

Given a binary tree, return a list containing all elements we would side at each level if we were looking at the tree from the right side.

Example

  1

 /\

 2 3

return 1,3 since 2 is hidden by 3 on its level.

We can solve this with a BFS or even recursively.

[Java] Justify text

Given an array of words and a page size, return a list of lines that have been padded to fit the given page size.

If a line can fit only one word or is the last line, pad on the right, otherwise pad between words and add excess padding starting from the left.

This can be done in linear time in the size of the output text by walking on the input array and tracking how many words we are adding to the current line, plus how much space is left.

Whenever we add a word, we also check if we could fit the next, as in that case we would add at least a space on the current line.

When we can't add more words to a line or the line is full, we process all words in the start,end range we found so far and correctly pad between them.

The complexity is in calculating how wide each space should be and how much padding we need to add to those spaces:

spaceSize = (page size - length of words on the line) / (number of words on the line - 1)

Then we need to calculate if there is excess padding which needs to be distributed among those breaking points:

remainingPadding = (page size - length of words on the line) % (number of words on the line - 1)

When we add a word, we add spaceSize spaces after it, then one space from remainingPadding (if any are left) 

In the special case of single word or last line, spaceSize will be 1 and remainingPadding will be 0

We then check if the line has still some space left (only can happen in the special case above) and if so, we add enough padding spaces to the right side. 

We only process each string in input twice (first we read and add, then we push to result) and in terms of spaces we only add the ones required. At most in one line there can be M characters, that's the size of the page so in worst case each line can contain only one word and some spaces, the total amount of characters we process among words and spaces is O(NM) where N is the number of input words and M is the page size. This is linear in the size of the output.

Regarding space, we use a StringBuilder, therefore at most we add M words to it each time, bringing space to O(M).

You can check my implementation of fullJustify on my Gist along with some tests in FullJustifyJTests.

[Java] Move array elements preserving order

Given an array of integers, move all zero elements to the end while preserving the order of the other elements.

We are supposed to alter the given array, therefore let's make use of it.
We want to scan the array to find all non zero elements and put them to the front of the array, then fill the rest of the positions with zeros.

We notice though that the first non zero element would be placed at the beginning of the array, then the next non zero would be placed after that and so on.

If an element is non zero and there were no zeros before it, it stays in its place.

Therefore we can use a pointer to track where would we insert a non zero element, then scan all other elements of the array. 

When we encounter a non zero element, we copy it to the location pointed by our pointer UNLESS it's exactly our position. If we did move, we replace the current position with a zero. In both cases, we increase the pointer.

We can process the array in O(N) time using constant space.

You can check my implementation of moveZeros on my Gist along with some tests in MoveZerosJTests.

[Java] Longest wiggle subsequence

A wiggle sequence is a series of numbers where elements are strictly increasing or decreasing.

Given an array of numbers, find the longest wiggle subsequence. Example:

1,1 - longest is 1

1,2,3 - longest is 2

1,2,1 - longest is 3

The sequence can start going up or down, then all other elements must alternate between going down or up.

[Java] String length compression decode

Given a text representing a compressed string, return the uncompressed version. 

Compression works as such: if a substring is repeated K times, we represent as K[substring] which can be nested. Example:

K[ssL[a]] means we repeat 'a' L times (call it T) and then repeat 'ssT' K times.

K is always > 0 and the string will always be well formed.

[Java] Draw fractal H tree

Fractals certainly build beautiful shapes, in this exercise we are tasked with creating an H tree, that is a tree where given a starting point which is the center of the horizontal line in the H, all corners of the H repeat the pattern until a given depth.

Example:

depth = 0, no tree

depth = 1, H

depth = 2;

H H

 H

H H

We can solve this recursively by calculating for a given center point, the boundaries of the horizontal line and drawing that, then for those boundaries, calculating the top and bottom point of the vertical lines at those centers and drawing those, finally going deeper and repeat the pattern.

The total number of H we draw is linked to the depth: 4^depth, which is also the running time of our algorithm as we must go through all those points to draw the H.

Using a stack, we only add at most depth points to it from a given start, therefore keeping the space to a minimum.

You can check my implementation of drawHTree on my Gist. No tests for this since I didn't actually implement the line drawing portion.

[Java] Matrix spiral visit

Here is a problem where the challenge lies solely in correct index handling: given a NxM matrix (could be square) return an array which is the result of a clockwise spiral visit from top left corner.

Example:

12

34

result = 1,2,4,3

The problem description itself is the solution, we simply need to correctly set boundaries for our visit and process all elements in the matrix.

This is another exercise where drawing out a sample greatly helps with handling those boundary cases, I think the smallest sample that shows the correct logic is a 3x3 matrix.

We can view the matrix as a series of arrays wrapped around each other, and we process one of them each time.

We can do this in O(NM) time and O(1) space using 4 indices, representing the current boundaries:

• start row: indicates the top boundary of the matrix we are processing
• end row: indicates the bottom boundary of the matrix we are processing
• start col: indicates the left boundary of the matrix we are processing
• end col: indicates the right boundary of the matrix we are processing

By making our indices inclusive we have an easier time handling the logic. This means a boundary index indicates the first or last element we want to add (no out of bounds handling necessary)

Initially our boundaries are:

• start row: 0 (top row)
• end row: matrix.length - 1 (bottom row)
• start col: 0 (left col)
• end col: matrix[0].length - 1 (right col) 

Then, until we have added all elements in the matrix to our result, we execute 4 loops in succession, each processing one of the four boundaries.

When each of these loops end, we update the boundaries for the next.

We walk the matrix in a spiral and always add the bounds working our way inside:

• all of top: start row (left right) but start from NEXT column since we already added the first row element before (is first of column we just processed). NOTE: at the very beginning we already are on the correct position for this row so we only update the column AFTER all other boundaries have been processed
• add all of right: end column (top down) but start from NEXT row since we already added the first column element before (is last of row we just processed)
• add all of bottom: end row (right left) but start from PREVIOUS column since we already added the last row element before (is last of column we just processed)
• add all of left: start column (bottom up) but start from PREVIOUS row since we already added the last column element before (is first of row we just processed) 

We can see that we need to move only ONE boundary after each loop by drawing a 3x3 matrix and executing this logic on it.

We can also see that while we do have 4 loops within one outer loop, we are only processing each element once.

You can check my implementation of spiralVisit on my Gist along with some tests in SpiralVisitJTests.

[Java] Catalan numbers - Number of unique binary trees with N nodes

Here is another quite difficult problem: given an integer N, find how many valid binary search trees can be built using N nodes.

Being a problem on trees, we can try approaching it with recursion, which means we need to find some formula and base case to generalize the structure.

Drawing this problem out definitely helps reaching a solution, but the number of results grows quite rapidly even for small values of N so honestly spotting a pattern early was not super easy, N = 4 is the first where I think it's possible to see the recurrence.

Base case(s) are quite easy, a tree with 0 and 1 nodes can only be represented in one way: no nodes, or the single root.

Then we need to generalize, for a given root and at least another node, the root is one node and all remaining N-1 nodes can either be:

- all on the left side (keys are smaller than root)

- all on the right side (keys are bigger than root)

- some on the left and some on the right

The last case actually covers the previous two as well, we can simply see it as zero nodes being on the other side.

If some nodes are left and some are right and we are the root, it means some nodes in range 1..root-1 are on the left and nodes in range root+1..N are on the right, if we view all nodes as the numbers in the range 1..N and the root is value X, we will have the full sequence 1..X..N for a single value X.

Therefore for a given root, the number of ways its children can be combined is:

number of ways left subtree can be built * number of ways for right subtree can be built

If we repeat this process for all N possible roots, we get our final answer. Definitely using a cache here helps as the number of combinations rises terribly fast.

I am not sure if having the problem described as counting binary search trees rather than simply binary trees would help of complicate finding a solution, in any case, the answer is same for both.

It also turns out there is a sequence called Catalan numbers which represents exactly this pattern and is a special case of combinations. However, the n choose k formula involves factorials and for even small inputs, those can easily overflow the space of an integer. We can still use those numbers to test our solution though ;)

Both the top down and bottom up cached approaches will use O(N) space and O(N^2) time. As usual this is easier to see in the bottom up approach where we must explicitly run the inner loop to generate all 1..X..N combinations for the value of N being considered at that moment.

You can check my implementation of numOfBSTs and numOfBSTsBottomUp on my Gist along with some tests in NumOfBSTsJTests.

Euclid's greatest common divisor and least common multiple

The GCD of two numbers is the biggest number that divides both. I was going through some books and found Euclid's formula, which I am fairly certain is one of those formulas I learned in the past and just forgotten.

Anyway, the book was mentioning it has complexity O(logN) where N is the sum of the two numbers:

gcd(a, b){

  if(b == 0 ) return a;

  return gcd(b, a % b);

}

However, this assumes the modulo operation is done in constant time regardless of the input numbers, a  more realistic complexity is somewhere O(N logN) as the modulo might need to be computed in linear time.

A better approach uses bit operations instead and gives a O((logN)^2) time since the operations it uses can be computed in O(logN) time:

gcd(a, b){

  return gcd(a, b, 1);

}

gcd(a, b, res){

  if(a == b) return res * a;

  if(a % 2 == 0 && b % 2 == 0) return gcd(a >> 1, b >> 1, res << 1);

  if(a % 2 == 0) return gcd(a >> 1, b , res);

  if(b % 2 == 0) return gcd(a, b >> 1, res);

  if(a > b) return gcd(a - b, b, res);

  return gcd(a, b - a, res);

}

As an added bonus, we can use this to compute the LCM which is the smallest number divisible by both:

lcm(a,b){

return a * b / gcd(a, b);

}

You can find gcd and lcm on my Gist.

[Java] Number of elements with unblocked view

Here is an easy one to balance the last, given an array representing the height of people standing behind each other from left to right, find how many people have an unobstructed view in front of them.

We can do this in O(N) time and constant space by walking the array from right to left tracking each time the tallest person we have found. If the current person is NOT taller than the current tallest, he won't be able to see.

You can check my implementation of witnessOfTheTallPeople on my Gist along with some tests in WitnessOfTheTallPeopleJtests.

[Java] Length of longest filesystem path

Wow this exercise was harder than expected, also yay for String methods.

Given a string representing a filesystem, find the length of the longest path to a file.

The string has the following format (without spaces):

root  \n \t dir \n \t \t file_in_dir.ext

which represents the path: root/dir/file_in_dir.ext that has a total length of 24 characters.

We are told filenames will always include a dot followed by an extension and directories will never contain a dot.

[Java] Falling dominoes

Given an array representing dominoes, determine the final position of each piece. Array contains the following chars:
. = domino is standing still
R = domino is falling right
L = domino is falling left

The original problem used a string as input, however that is simply an array of characters, therefore the logic is the same.

Example:

R. = RR

R.L = R.L as center piece is being pushed from both sides

R..L = RRLL as center pieces can fall once but the get stuck in the middle

We can scan the input twice, from left to right and then right to left trcking partial outcomes in two arrays.

We then scan both arrays and determine the final position of a piece with the following cominations:

• (. .) piece is standing still
• (. R) (R R) piece is falling right
• (. L) (L L) piece is falling left
• (R L) piece is being pushed from both sides, leave it as it was in the input
  

We can get rid of the additional arrays altogether and just use the output array for all our operations. Still scan the array twice, first time left to right to determine which pieces would be falling right and we toggle a boolean to track whether pieces are falling right or not.
A piece falls right if it is AFTER another piece that also is falling right AND the NEXT piece is NOT falling left.

Second time we scan both input and partial result array right to left at the same time and repeat the process however we now have information about right falling pieces therefore we can determine the final domino position.
We use the same toggle to indicate whether pieces are falling left or not this time. We have the following cases:

1. piece in input was standing still: if we are now falling left, look at the partial result, if that piece is marked as falling right we are pushing on it from both directions, leave it as it was in the input, otherwise mark it as falling left
2. piece in input was falling right: toggle the falling switch to false
3. piece in input was falling left: toggle the falling switch to true
   

We need to be careful in handling boundary cases for example when a piece that was standing still at the borders of the array is being pushed to fall, in that case no other force can balance it and we need to correctly update it to fall.

This provides a solution in O(N) time and constant space.

You can check my implementation of fallingDominoes on my Gist along with some tests in FallingDominoesJTests.