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

Sort by

recency

|

1141 Discussions

|

  • 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;
        }       
    }   
    
     
    }

  • mrweisu
     + 0 comments

    Python 3:

    def equalStacks(h1, h2, h3): # Write your code here

    h1 = h1[::-1]
h2 = h2[::-1]
h3 = h3[::-1]

h1hite = sum(h1)
h2hite = sum(h2)
h3hite = sum(h3)

while True:

    if h1hite == h2hite and h1hite == h3hite:
        break
    else:
        if h1hite >= h2hite and h1hite >= h3hite:
            x = h1.pop()
            h1hite -= x
        elif h2hite >= h1hite and h2hite >= h3hite:
            x = h2.pop()
            h2hite -= x
        elif h3hite >= h1hite and h3hite >= h2hite:
            x = h3.pop()
            h3hite -= x

return h1hite

  • mrweisu
     + 0 comments

    Beat Google AI for this one :)

    from itertools import accumulate

    def equalStacks(h1, h2, h3): # Write your code here

    h1a = set(accumulate(h1[::-1]))
h2a = set(accumulate(h2[::-1]))
h3a = set(accumulate(h3[::-1]))

return max(h1a.intersection(h2a).intersection(h3a).union({0}))

  • sourav_raychaud1
     + 0 comments

    Java8 with steams

    public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
    // Write your code here
        // there are 3 stacks involved
        List<Integer> cumulHeights = new ArrayList<>();
        Integer cumul = 0;
        for (int i = h1.size() - 1; i>=0; i--) {
            cumul += h1.get(i);
            cumulHeights.add(cumul);
        }
        cumul = 0;
        for (int i = h2.size() - 1; i>=0; i--) {
            cumul += h2.get(i);
            cumulHeights.add(cumul);
        }
        cumul = 0;
        for (int i = h3.size() - 1; i>=0; i--) {
            cumul += h3.get(i);
            cumulHeights.add(cumul);
        }
        Optional<Map.Entry<Integer, Long>> mm = cumulHeights.stream().collect(Collectors.groupingBy(s -> s, Collectors.counting())).entrySet()
                .stream().filter((s) -> s.getValue() == 3).max(Comparator.comparingInt(s -> s.getKey()));
        if (mm.isPresent()) {
            return mm.get().getKey();
        }
        return 0;
    }

  • pavelkazeko1991
     + 0 comments

    C++ Solution with unlimited input stacks

    int equalStacks(std::vector<int> h1, std::vector<int> h2, std::vector<int> h3) {
    std::multimap<int, std::vector<int>> stacks {  };
    stacks.insert({ std::accumulate(h1.begin(), h1.end(), 0), h1 });
    stacks.insert({ std::accumulate(h2.begin(), h2.end(), 0), h2 });
    stacks.insert({ std::accumulate(h3.begin(), h3.end(), 0), h3 });
    
    while (stacks.count(stacks.begin()->first) != stacks.size()) {
        auto max_sum { stacks.rbegin()->first };
        auto max_stacks { stacks.equal_range(max_sum) };
        auto max_stacks_copy { std::vector<decltype(stacks)::iterator>() };
        
        for (auto it = max_stacks.first; it != max_stacks.second; ++it) {
            max_stacks_copy.push_back(it);
        }
        
        for (auto it : max_stacks_copy) {    
            auto node { stacks.extract(it->first) };            
            node.key() -= *node.mapped().begin();
            node.mapped().erase(node.mapped().begin());
            
            stacks.insert(std::move(node));
        }
    }
    
    return stacks.begin()->first;
}