Pages
11/08/2021
[Java] Array of doubled pairs
Given an array of integers return true if it is possible to reorder its elements in pairs so that arr[2 * i + 1] = 2 * arr[2 * i] for all i up to length/2
In other words, given an array of integers allowing negatives and duplicates, find if it is possible to use each element in a pair where the first element in the pair is half the value of the second element of that pair. Elements cannot be reused among different pairs.
08/08/2021
[Java] Satisfiability of equations
Given a series of equality and inequality equations, determine whether they can be satisfied.
Equations are in the form:
a==b
a!=b
where a,b are the two variables involved.
Example:
a==b, b==c, c==a: OK
a==b, b==c, c!=a: KO
Similar to the graph coloring we saw before, we can apply the same method here but expand it to more colors.
We create an adjacency list from all equality equations, the linked variables (connected components) must all have the same color, we proceed by starting with a color and then assigning it to all variables connected to each other, we repeat this process for all variables without color, each time using a different color.
Then we parse all inequality equations and verify if any conflict arises.
This algorithm runs in O(V) space and O(E) time as we explore all edges (equations) once. We use V space for the stack when coloring as at most we can add each vertex only once (we only add if vertex has no color).
You can check my implementation of equationsPossible on my Gist along with some tests in EquationsPossibleJTests.
[Java] Graph bipartition (2 coloring)
Given a graph, return a possible 2 coloring of it.
The algorithm is simple, for each node in the graph, if it doesn't yet have a color, run a DFS from it.
The DFS will assign a default color (eg; 1) to the node, if it doesn't already have one, then for each neighbor:
- if it already has a color which is NOT different from the current node color, break and fail
- if it doesn't have a color, assign the OPPOSITE of the current node color (eg use formula 1 - node color to invert between 0 and 1), then run a DFS from that node
In the end, if we stopped early it means the graph can't be colored with only 2 colors (there is no possible bipartition), otherwise we will have a possible 2 coloring or our graph as output.
This algorithm runs in O(V) space and O(E) time as for each node we explore all its neighbors once (we don't invoke DFS again unless neighbor had no color) and at most we can put V nodes on the callstack for recursion.
You can check my implementation of twoColor on my Gist along with some tests in TwoColorBipartitionJTests.