We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Equal Stacks
  5. Discussions

Equal Stacks

  • rozic
     + 0 comments

    Key facts to realize to achieve the required runtime:

    1. any stack that is higher than any other can have a cylinder removed in the next step
    2. removing cylinders from the stack tops, we return on the first instance of finding (all three) equal height cylinders.
    3. I chose not to actually remove cylinders from the lists/stacks (which is possibly an expensive operation) but instead to maintain an index, per stack, of the top cylinder. But maybe list element removal would have worked too.

    Java below:

    public static int CylHeight (List<Integer> h1) {
        int height = 0;
        for (int c : h1) {
            height += c;
        }
        return height;
    }   
    
    public static boolean CheckEqualSizes (int h1Size, int h2Size, int h3Size) {
        if (h1Size == h2Size && h2Size == h3Size) return true;
        return false;
    }

    public static int ChooseNext (int h1Size, int h2Size, int h3Size) {
        if (h1Size > h2Size) {
            return 1;
        } else {
            if (h2Size > h3Size) {
                return 2;
            }
        }
        return 3;
    }


    public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
    
    /*
    choose the first stack that is higher than any other and then remove a cylnder
    stop on the first instance of equal stack heights
    */
    
    int h1Size = CylHeight(h1);
    int h2Size = CylHeight(h2);
    int h3Size = CylHeight(h3);
                  
    int myCyl1 = 0;
    int myCyl2 = 0;
    int myCyl3 = 0;
    
    int whichStack;
    while (true) {
        
        if (CheckEqualSizes(h1Size, h2Size, h3Size)) {
            return h1Size;
        }
        
        whichStack = ChooseNext(h1Size, h2Size, h3Size);
    
        switch (whichStack) {
            case 1:
            h1Size -= h1.get(myCyl1++);
            break;
            
            case 2:
            h2Size -= h2.get(myCyl2++);
            break;
            
            case 3:
            h3Size -= h3.get(myCyl3++);
            break;
        }       
    }   
    
     
    }