[Java] Ways to traverse a grid

Given two integers N and M representing the number of rows and columns in a grid, calculate in how many ways we can traverse from top left to bottom right moving only right or down.

We can notice that the starting cell cannot be reached by moving, so we set its value to 0. All cells on the first row and column can only be reached in one way that is moving always right or down. We set them to 1.

All other cells can be reached by moving right or down from a previous left or top cell, which means they can be reached by continuing either of those paths, therefore they can be reached by summing up the ways of reaching the previous top and left cells.

This approach takes O(MN) time and space.

However it turns out there is a better approach that works in constant space and O(M+N) time.

Since each inner cell can be reached by summing some combinations of reaching previous cells, it means we are enumerating permutations of right and down movements up to a certain cell.

Therefore the magic fomula is (N+M)! / (N! * M!)

However, we need to use N-1 and M-1 as we are calculating the inner portion of a matrix where we actually move either direction, example:

0111

1###

1###

1###

We only do the calculation for the # cells as the boundary ones only offer one way of reaching them.

Because we only need to calculate three factorials, and the biggest is N+M, our runtime is O(N+M) - beware of overflows though!

You can check my implementations of waysToTraverseGrid and waysToTraverseGridCombinations on my Gist along with some tests in WaysToTraverseGridJTests.

[Java] Remove consecutive nodes with zero sum from linked list

Given a singly linked list, remove all consecutive nodes that sum up to 0 from it.

Examples:

0 return null

6, -6 return null

10, 4, -4 return 10

10, 4, -3, -1, 2 return 10, 2

We use two pointers, one is sitting before the head, the other walks the list.
We keep summing values of nodes up and each time we store in a map the pair(sum up to this node, node) then we check the current sum, we can have the following cases:
(1) sum is 0: this means from start to end all elements sum to 0, we need to remove all of them and we need to carefully handle the head:
- if start pointer is null, it means this 0 sum includes the head, we will update it
- if start pointer is not null, it means this 0 sum occurs from a node (which might be the head), we update the NEXT of it
(2) sum is a value we already encountered: this means that AFTER the last node where we saw that sum until the end all elements sum to 0, we update the NEXT of the current start to cut them out
(3) otherwise we store the value in the map and move on to the next element

Whenever we perform a cut, we rest the counter to 0 and clear the map since we remove all consecutive nodes whose sum is 0, therefore after a cut we restart from the last node we kept.

This works in O(N) time and uses O(N) space.

You can check my implementation of removeNodesWithZeroSum on my Gist along with some tests in RemoveNodesWithZeroSumJTests.

[Java] Longest palindromic subsequence

Given a string, find the longest palindromic subsequence it contains.

A non palindromic string, still contains a palindromic subsequence, as a single character is a valid palindrome.

If a string contains a palindromic subsequence, there will be some characters that appear in a certain order on both sides of the middle element of the palindrome (either a single character for odd length palindromes or the space in between two characters for even length palindromes).

For example:

acca, acfca are palindromes

acbgca contains more palindromic subsequences, the longest being acbca or acgca

abccga contains more palindromic subsequences, the longest is acca

For any given palindromic subsequence, we must find the same characters in the same order on both sides of the middle point in the original string.

If we reverse the original string in O(N) time, we can then use our logic to find the longest common subsequence to find this palindrome in O(MN) time and space, which in this case is O(N^2).

Example:

abccga reverses to agccba

And the longest common subsequence to both is acca

asd reverses to dsa

and the longest common subsequence to both is any single character

You can check my implementation of longestPalindromicSubsequence on my Gist along with some tests in LongestPalindromicSubsequenceJTests.

[Java] Longest common subsequence

Give two strings, find the longest common subsequence. A subsequence is a sequence of characters, not necessarily adjacent, that appear in a specific order in both strings.

Example:

sda, dlolsla

longest common subsequence is "sa" of length 2, other subsequences are "d", "s" and "a".

[Java] Minimum cost of painting houses using K colors

We have N houses in a row and K available colors. Given a NxK matrix where each cell represents the cost of painting house N with color K, find the minimum cost of painting all the houses such that no two adjacent houses have same color.

We notice the solution can be reached using DFS recursive approach where we explore the costs of painting each house using all colors except for the one used for the previous house.

Starting from the first house we have all K choices available, however the second house will have K-1 choices since we used a color already for the first, and so on.

This means we have a O(K^N) runtime as for each house we must explore all those color choices. Our space usage will be O(N) as for each house we explore all others and that would be the depth of our stack.

We can improve on this by caching results as we go such that when we encounter the same (house, excluded color) combination again, we already have our best answer and can return that without further calculation.

We can create another NxK matrix or use a Map where the pair(house, excluded color) is the key and the value is the minimum cost of painting the current house EXCLUDING that color + cost of painting the next excluding the BEST color chosen for the current house.

By doing this, we reduce our runtime to O(NK) as for each house we explore all K colors and use O(NK) space as well for our cache.

You can check my implementation of minCostToPaintHouses on my Gist along with some tests in MinCostToPaintHousesJTests.

[Java] Maximise profit to cut rod

Given a rod of length N and an array indicating the profit from selling a rod of length i + 1, find the best way to cut up the rod in order to maximise the profit of selling all the pieces. Not cutting the rod at all is also a valid option.

Example:

[1,5,2,7]

means our profit for selling a rod piece of length 1 is 1, length 2 is 5, etc

If we picked length 4, the best would be cutting it in two pieces of length 2 for a total profit of 10.

We can use a DFS recursive approach where for each rod size from 1 to N and all possible cuts of a rod of that size, we pick the best between profit of NOT cutting rod and profit of cutting on that length + best profit of cutting the remainder.

Since we have two possible choices at each step, our algorithm runs in O(2 ^N) time and uses O(N) space as at most our DFS depth will reach the length of the rod.

[Java] Find all duplicates between two sorted arrays

Given two sorted arrays, find all elements that appear in both arrays, return a sorted array of those as result.

Since either array could be much bigger than the other, if we use a two pointer approach where we walk both arrays at the same time and determine which pointer to increase we get a O(M+N) runtime, if instead we use binary search on the bigger array for each element in the smaller, we get a O(M log N) runtime.

Two caveats on this solution, we had created a generic binary search method, but it uses Java generics and in Java int[] is not same as Integer[]. For convenience we therefore use Integer[] as input.

Additionally, we need to output an int[] but we do not know beforehand the size of it (will be at most min(M,N)) so we store results as we go in a queue which will allow us to create the sorted output array in the end.

You can check my implementation of findDuplicatesInArraysBinarySearch on my Gist along with some tests in FindDuplicatesInArraysBinarySearchJTests.