HackerRank: Equal Stacks

Question

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 [true if height is reachable by removing zero or more elements from the stack and false otherwise]
 */
 private static boolean heightReachable(int height, int[] stackBlocks, int stackHeight){
 for(int i=0; i < stackBlocks.length; i++){
 if(stackHeight == height) return true;
 stackHeight = stackHeight - stackBlocks[i]; 
 } 
 return false;
 }
}

• 200_success: Could you link to the problem and summarize it?
• jugelika: problem link

Answer 1

Method decomposition

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();
}

• jugelika: wouldn't it be quicker if i get starting sums in starting 3 loops in main method since we have no choice but to read input? i mean is IntStream.of(arr).sum(); really neccassary since we can provide these sums in parameters from main method and save time on getting their sums after array initialization?(very helpful answer btw)
• janos: Strictly speaking, yes, it would be faster. Practically the difference is negligible, and by separating the input parsing and the computation logic you get more readable, cleaner code.

Answer 2

You can also implement recursive solution that finds the highest stack and removes element from it and does this until all stacks are of same height:

 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=n1-1; h1_i >= 0; h1_i--){
 h1[h1_i] = inputStream.nextInt();
 n1Height += h1[h1_i];
 }
 for(int h2_i=n2-1; h2_i >= 0; h2_i--){
 h2[h2_i] = inputStream.nextInt();
 n2Height += h2[h2_i];
 }
 for(int h3_i=n3-1; h3_i >= 0; h3_i--){
 h3[h3_i] = inputStream.nextInt();
 n3Height += h3[h3_i];
 }
 int height = getHeight(n1, n1Height, n2, n2Height, n3, n3Height, h1, h2, h3);
 System.out.println(height);
 inputStream.close();
 }
private static int getHeight(int n1, int n1H, int n2, int n2H, int n3, int n3H, int[] h1, int[] h2, int[] h3) {
 if (n1H==n2H && n1H==n3H) {
 return n1H;
 }
 if (n1H > n2H) {
 n1-=1;
 n1H-=h1[n1-1];
 } else if (n2H > n3H){
 n2-=1;
 n2H-=h2[n2-1];
 } else {
 n3-=1;
 n3H-=h3[n3-1];
 }
 return getHeight(n1, n1H, n2, n2H, n3, n3H, h1, h2, h3);
}

Answer 3

Your solution is having O(n^2) complexity due to two nested for loops which are not efficient to solve this problem you can optimize it further.

By maintaining cummulative sum instead of individual cylinder height.

Here is my code with O(n1+n2+n3) solution-

static int equalStacks(int[] h1, int[] h2, int[] h3) {
 Stack<Integer> st1 = new Stack<Integer>();
 Stack<Integer> st2 = new Stack<Integer>();
 Stack<Integer> st3 = new Stack<Integer>();
 int st1TotalHeight = 0, st2TotalHeight = 0, st3TotalHeight = 0;
 // pushing consolidated height into the stack instead of individual cylinder
 // height
 for (int i = h1.length - 1; i >= 0; i--) {
 st1TotalHeight += h1[i];
 st1.push(st1TotalHeight);
 }
 for (int i = h2.length - 1; i >= 0; i--) {
 st2TotalHeight += h2[i];
 st2.push(st2TotalHeight);
 }
 for (int i = h3.length - 1; i >= 0; i--) {
 st3TotalHeight += h3[i];
 st3.push(st3TotalHeight);
 }
 while (true) {
 // If any stack is empty
 if (st1.isEmpty() || st2.isEmpty() || st3.isEmpty())
 return 0;
 st1TotalHeight = st1.peek();
 st2TotalHeight = st2.peek();
 st3TotalHeight = st3.peek();
 // If sum of all three stack are equal.
 if (st1TotalHeight == st2TotalHeight && st2TotalHeight == st3TotalHeight)
 return st1TotalHeight;
 // Finding the stack with maximum sum and
 // removing its top element.
 if (st1TotalHeight >= st2TotalHeight && st1TotalHeight >= st3TotalHeight)
 st1.pop();
 else if (st2TotalHeight >= st3TotalHeight && st2TotalHeight >= st3TotalHeight)
 st2.pop();
 else if (st3TotalHeight >= st2TotalHeight && st3TotalHeight >= st1TotalHeight)
 st3.pop();
 }
 }

you can refer the this link for video explanation in more detail.