While I was waiting for some tests to complete I checked my Gmail and found a message from HackerRank suggesting a challenge. The Equal Stacks challenge may be found under Practice > Data Structures > Stacks > Equal Stacks. I read the description for the problem and decided to tackle it using stacks; how creative of me.
The problem states that one may remove cylinders to get all stacks the same height attempting to return the height for the tallest. That said; the tallest stack might be of height zero (0).
I decided that I could keep a variable per stack indicating the current height. It could be initialized by traversing each set of cylinders. Every time a cylinder is removed from a stack the height would be updated. This is possible, but not too elegant.
Another option would be read the values into a queue and then push them into a stack. While populating the stack we could add the previous cylinder height in order to eliminate the additional variables.
Following is the code I wrote to process input for testing. I wrote it not thinking that HackerRank could be providing the testing scaffolding; my mistake.
The code complete Java 8 code written using the Eclipse IDE follows:
package canessa.stacks.arrays;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the equalStacks function below.
*/
static int equalStacks(int[] h1, int[] h2, int[] h3) {
// **** compute the remaining heights on all stacks ****
for (int i = h1.length - 1; i > 0; i--)
h1[i - 1] += h1[i];
for (int i = h2.length - 1; i > 0; i--)
h2[i - 1] += h2[i];
for (int i = h3.length - 1; i > 0; i--)
h3[i - 1] += h3[i];
// **** traverse the stacks looking for the same height ****
int i = 0;
int j = 0;
int k = 0;
while ((i < h1.length) && (j < h2.length) && (k < h3.length)) {
// **** check if all stacks have the same height (we are done) ****
if ((h1[i] == h2[j]) && (h2[j] == h3[k]))
return h1[i];
// **** determine the max height of the stacks ****
int maxHeight = Math.max(h1[i], Math.max(h2[j], h3[k]));
// **** remove the next cylinder from the tallest stack ****
if (maxHeight == h1[i])
i++;
else if (maxHeight == h2[j])
j++;
else
k++;
}
// **** empty stacks ****
return 0;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
// BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(FileDescriptor.out));
String[] n1N2N3 = scanner.nextLine().split(" ");
int n1 = Integer.parseInt(n1N2N3[0].trim());
int n2 = Integer.parseInt(n1N2N3[1].trim());
int n3 = Integer.parseInt(n1N2N3[2].trim());
int[] h1 = new int[n1];
String[] h1Items = scanner.nextLine().split(" ");
for (int h1Itr = 0; h1Itr < n1; h1Itr++) {
int h1Item = Integer.parseInt(h1Items[h1Itr].trim());
h1[h1Itr] = h1Item;
}
int[] h2 = new int[n2];
String[] h2Items = scanner.nextLine().split(" ");
for (int h2Itr = 0; h2Itr < n2; h2Itr++) {
int h2Item = Integer.parseInt(h2Items[h2Itr].trim());
h2[h2Itr] = h2Item;
}
int[] h3 = new int[n3];
String[] h3Items = scanner.nextLine().split(" ");
for (int h3Itr = 0; h3Itr < n3; h3Itr++) {
int h3Item = Integer.parseInt(h3Items[h3Itr].trim());
h3[h3Itr] = h3Item;
}
int result = equalStacks(h1, h2, h3);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
}
}
As I mentioned, I did not see the scaffolding until I was ready to submit the code. I did notice that the equalStacks() function uses three arrays instead of three stacks. At least I got right the name of the function.
Back to square one. Created a new project and copied the scaffolding code for testing. Had to edit / comment and modify the first line. I did not wish to create the specified system environment variable in my system.
As you will see, the new solution uses arrays. Seems like the word stack just referred to the section in the HackerRank web site. You can easily figure out that the previous solution could have been edited to load stacks from the arrays. I decided to just use the arrays. In practice they are faster that stacks. Perhaps I missed it but the solution did not call for an implementation using stacks. I submitted the second approach and it was accepted.
Following is the code for the second solution. Please note that the testing scaffolding was provided by HackerRank.
package canessa.stacks.arrays;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the equalStacks function below.
*/
static int equalStacks(int[] h1, int[] h2, int[] h3) {
// **** compute the remaining heights on all stacks ****
for (int i = h1.length - 1; i > 0; i--)
h1[i - 1] += h1[i];
for (int i = h2.length - 1; i > 0; i--)
h2[i - 1] += h2[i];
for (int i = h3.length - 1; i > 0; i--)
h3[i - 1] += h3[i];
// **** traverse the stacks looking for the same height ****
int i = 0;
int j = 0;
int k = 0;
while ((i < h1.length) && (j < h2.length) && (k < h3.length)) {
// **** check if all stacks have the same height (we are done) ****
if ((h1[i] == h2[j]) && (h2[j] == h3[k]))
return h1[i];
// **** determine the max height of the stacks ****
int maxHeight = Math.max(h1[i], Math.max(h2[j], h3[k]));
// **** remove the next cylinder from the tallest stack ****
if (maxHeight == h1[i])
i++;
else if (maxHeight == h2[j])
j++;
else
k++;
}
// **** empty stacks ****
return 0;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
// BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(FileDescriptor.out));
String[] n1N2N3 = scanner.nextLine().split(" ");
int n1 = Integer.parseInt(n1N2N3[0].trim());
int n2 = Integer.parseInt(n1N2N3[1].trim());
int n3 = Integer.parseInt(n1N2N3[2].trim());
int[] h1 = new int[n1];
String[] h1Items = scanner.nextLine().split(" ");
for (int h1Itr = 0; h1Itr < n1; h1Itr++) {
int h1Item = Integer.parseInt(h1Items[h1Itr].trim());
h1[h1Itr] = h1Item;
}
int[] h2 = new int[n2];
String[] h2Items = scanner.nextLine().split(" ");
for (int h2Itr = 0; h2Itr < n2; h2Itr++) {
int h2Item = Integer.parseInt(h2Items[h2Itr].trim());
h2[h2Itr] = h2Item;
}
int[] h3 = new int[n3];
String[] h3Items = scanner.nextLine().split(" ");
for (int h3Itr = 0; h3Itr < n3; h3Itr++) {
int h3Item = Integer.parseInt(h3Items[h3Itr].trim());
h3[h3Itr] = h3Item;
}
int result = equalStacks(h1, h2, h3);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
}
}
Just to verify the operation of the code, a screen capture from the console follows:
5 3 4 3 2 1 1 1 4 3 2 1 1 4 1 5
Seems like the testing I was doing in parallel requires me to come up with a new test. Glad that I could complete this post in time.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate and leave a message; will respond as soon as possible.
Happy software development;
John
Follow me on Twitter: @john_canessa