patternjavaMinor
HackerRank: Equal Stacks
Viewed 0 times
hackerrankstacksequal
Problem
This is my solution to the Equal Stacks problem on HackerRank. I thinks it's really messy and slow. could you give me some thoughts about how to optimize given code and algorithm(i'm pretty sure problem can be solved way effectively)
```
import java.io.*;
import java.util.*;
import java.util.stream.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner inputStream = new Scanner(System.in);
int n1 = inputStream.nextInt();
int n2 = inputStream.nextInt();
int n3 = inputStream.nextInt();
int n1Height = 0;
int n2Height = 0;
int n3Height = 0;
int h1[] = new int[n1];
int h2[] = new int[n2];
int h3[] = new int[n3];
for(int h1_i=0; h1_i < n1; h1_i++){
h1[h1_i] = inputStream.nextInt();
n1Height += h1[h1_i];
}
for(int h2_i=0; h2_i < n2; h2_i++){
h2[h2_i] = inputStream.nextInt();
n2Height += h2[h2_i];
}
for(int h3_i=0; h3_i < n3; h3_i++){
h3[h3_i] = inputStream.nextInt();
n3Height += h3[h3_i];
}
int highestHeight = 0;
for(int i=0; i< n3; i++){
if(heightReachable(n3Height,h2,n2Height) && heightReachable(n3Height, h1, n1Height)){
highestHeight = n3Height;
break;
}
n3Height -= h3[i];
}
System.out.println(highestHeight);
inputStream.close();
}
/**
* [heightReachable - returns boolean identifying whether or not given height is reachable by given stack]
* @param height [height which we should check if is reachable or not]
* @param stackBlocks [stack blocks array containing height of each block]
* @param stackHeight [number of blocks in given stack]
* @return [tru
```
import java.io.*;
import java.util.*;
import java.util.stream.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner inputStream = new Scanner(System.in);
int n1 = inputStream.nextInt();
int n2 = inputStream.nextInt();
int n3 = inputStream.nextInt();
int n1Height = 0;
int n2Height = 0;
int n3Height = 0;
int h1[] = new int[n1];
int h2[] = new int[n2];
int h3[] = new int[n3];
for(int h1_i=0; h1_i < n1; h1_i++){
h1[h1_i] = inputStream.nextInt();
n1Height += h1[h1_i];
}
for(int h2_i=0; h2_i < n2; h2_i++){
h2[h2_i] = inputStream.nextInt();
n2Height += h2[h2_i];
}
for(int h3_i=0; h3_i < n3; h3_i++){
h3[h3_i] = inputStream.nextInt();
n3Height += h3[h3_i];
}
int highestHeight = 0;
for(int i=0; i< n3; i++){
if(heightReachable(n3Height,h2,n2Height) && heightReachable(n3Height, h1, n1Height)){
highestHeight = n3Height;
break;
}
n3Height -= h3[i];
}
System.out.println(highestHeight);
inputStream.close();
}
/**
* [heightReachable - returns boolean identifying whether or not given height is reachable by given stack]
* @param height [height which we should check if is reachable or not]
* @param stackBlocks [stack blocks array containing height of each block]
* @param stackHeight [number of blocks in given stack]
* @return [tru
Solution
Method decomposition
The
and does a large part of the calculation logic too.
It would be better to move the calculation outside.
That is, after the input is read and parsed,
it will be better to leave just this in
And all the calculation logic can be in
Simplify the algorithm
The algorithm is a bit complicated and hard to understand.
It's also inefficient.
As you knock off cylinders from the 3rd stack,
you check if you can reduce the others from the top.
This can lead to recalculating the sums multiple times.
Consider this alternative implementation:
knock off cylinders from the highest stack,
until they are all of the same height:
The
main method reads and parses the input,and does a large part of the calculation logic too.
It would be better to move the calculation outside.
That is, after the input is read and parsed,
it will be better to leave just this in
main:System.out.println(findEqualHeight(h1, h2, h3));And all the calculation logic can be in
findEqualHeight.Simplify the algorithm
The algorithm is a bit complicated and hard to understand.
It's also inefficient.
As you knock off cylinders from the 3rd stack,
you check if you can reduce the others from the top.
This can lead to recalculating the sums multiple times.
Consider this alternative implementation:
knock off cylinders from the highest stack,
until they are all of the same height:
static int findEqualHeight(int[] h1, int[] h2, int[] h3) {
int sum1 = sum(h1);
int sum2 = sum(h2);
int sum3 = sum(h3);
int i1 = 0;
int i2 = 0;
int i3 = 0;
while (true) {
if (sum1 > sum2 || sum1 > sum3) {
sum1 -= h1[i1++];
} else if (sum2 > sum1 || sum2 > sum3) {
sum2 -= h2[i2++];
} else if (sum3 > sum1 || sum3 > sum2) {
sum3 -= h3[i3++];
} else {
break;
}
}
return sum1;
}
static int sum(int[] arr) {
return IntStream.of(arr).sum();
}Code Snippets
System.out.println(findEqualHeight(h1, h2, h3));static int findEqualHeight(int[] h1, int[] h2, int[] h3) {
int sum1 = sum(h1);
int sum2 = sum(h2);
int sum3 = sum(h3);
int i1 = 0;
int i2 = 0;
int i3 = 0;
while (true) {
if (sum1 > sum2 || sum1 > sum3) {
sum1 -= h1[i1++];
} else if (sum2 > sum1 || sum2 > sum3) {
sum2 -= h2[i2++];
} else if (sum3 > sum1 || sum3 > sum2) {
sum3 -= h3[i3++];
} else {
break;
}
}
return sum1;
}
static int sum(int[] arr) {
return IntStream.of(arr).sum();
}Context
StackExchange Code Review Q#136664, answer score: 3
Revisions (0)
No revisions yet.