C# How to optimize my code using stacks? (HackerRank "Equal Stacks" problem)

Question

I've solved the problem, but 11/30 test cases fail because "Time limit exceeded". I wonder if there's a way to optimize my code, so that the solution passes all the test cases.

The link to the problem: https://www.hackerrank.com/challenges/equal-stacks/problem

My approach: I wanted to use stacks, as the name of the problem suggests, even though the arguments passed in the method is List. So first I convert lists to stacks the following way: each top element, represents current height of the stack. So if there are blocks with 1, 5, 10 height, then the elements in the stack will be 1, 6, 16. My algorithm is to pop max elements from stack till all the stacks have the same height.

Here's my code:

public static int equalStacks(List<int> h1, List<int> h2, List<int> h3)
{
 var result = 0;
 if (IsEmpty(h1) || IsEmpty(h2) || IsEmpty(h3)) return result;
 
 var h1Stack = GetStack(h1);
 var h2Stack = GetStack(h2);
 var h3Stack = GetStack(h3);
 
 while (h1Stack.Any() && h2Stack.Any() && h3Stack.Any())
 {
 var h1Height = LocalPeek(h1Stack);
 var h2Height = LocalPeek(h2Stack);
 var h3Height = LocalPeek(h3Stack);
 
 if (h1Height == h2Height && h1Height == h3Height) return CountHeight(h1Stack);
 
 var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
 if (h1Height == max && h1Stack.Any()) h1Stack.Pop();
 if (h2Height == max && h2Stack.Any()) h2Stack.Pop();
 if (h3Height == max && h3Stack.Any()) h3Stack.Pop();
 }
 
 return 0;
}
static bool IsEmpty(List<int> stack) 
{
 return (!stack?.Any() ?? true);
}
static int LocalPeek(Stack<int> stack){
 if (stack.Any()) return stack.Peek();
 return 0;
}
static Stack<int> GetStack(List<int> numbers)
{
 var stack = new Stack<int>(numbers.Count);
 for (var i = numbers.Count - 1; i >= 0; --i)
 {
 stack.Push(numbers[i] + LocalPeek(stack));
 }
 return stack;
}
static int CountHeight(Stack<int> stack)
{
 return stack.Any() ? stack.Peek() : 0;
}

If we have list of with length: m, n, k as an input an n is the max of them, then I think my algorithm executes in O(n); And I don't see any problem with it to be honest. Please let me know if I do something wrong and how can I fix that.

Thank you.

• Jeremy Lakeman: .Any() is going to open an enumeration. I'd just use .Count>0.
• Jeremy Lakeman: But I think what you actually want is a linear scan, from "bottom" to "top", across all lists. Recording each height where the cylinders all line up, keeping the last one.
• David Oganov: Thanks for your replies @JeremyLakeman . In terms of using Any() I know that Count is more efficient. But it will not change much, plus I think Any is more human readable. But thanks for pointing that out anyway. In terms of your second comment with scanning from "bottom" to "top".. Currently I scan from "top" to "bottom". And in some cases your approach will be more efficient, in others mine. It depends pretty much on the input.
• Jeremy Lakeman: What I mean, is you can think of the problem as decrementing the last element in each list. If all those elements are zero, you've found a possible solution. If any element is zero, advance to the next element. If you run out of elements, stop.
• Jeremy Lakeman: If you really want to use stacks, change the main method to populate them while parsing each line.

Answer 1

I also suggest not using stacks, here is a non linq approach with O(n) on each list (one parse), also it doesn't allocate more than the working out variables.

public static int EqualStacks(int[] h1, int[] h2, int[] h3)
{
 var a = new[] {h1, h2, h3};
 var i = new int[3];
 var c = new int[3];
 var last = 0;
 bool GetLowest(out int result)
 {
 result = -1;
 if (c[0] <= c[1] && c[0] <= c[2] && i[0] < a[0].Length-1) result = 0;
 else if (c[1] <= c[0] && c[1] <= c[2] && i[1] < a[1].Length - 1) result = 1;
 else if (i[2] < a[2].Length - 1) result = 2;
 else return false;
 return true;
 }
 while (true)
 {
 if (!GetLowest(out var index)) 
 return last;
 c[index] += a[index][i[index]];
 i[index]++;
 if (c[0] == c[1] && c[1] == c[2])
 last = c[0];
 // Console.WriteLine($"Current = {string.Join(", ", c)}, Index = {index}, Last = {last}");
 }
}

Usage

var result = EqualStacks(
 new[] {1, 1, 1, 2, 3},
 new[] {2, 3, 4},
 new[] {1, 4, 1, 1});
Console.WriteLine(result);

Results

Current = 1, 0, 0, Index = 0, Last = 0
Current = 1, 2, 0, Index = 1, Last = 0
Current = 1, 2, 1, Index = 2, Last = 0
Current = 2, 2, 1, Index = 0, Last = 0
Current = 2, 2, 5, Index = 2, Last = 0
Current = 3, 2, 5, Index = 0, Last = 0
Current = 3, 5, 5, Index = 1, Last = 0
Current = 5, 5, 5, Index = 0, Last = 5
Current = 5, 5, 6, Index = 2, Last = 5
Result = 5, 5, 6, Last = 5
5

_{Note : I haven't tested this thoroughly, though my brain says it works.. what could go wrong (said sheepishly)? ̄\_(ツ)_/ ̄,}

Also you can probably inline GetLowest(), would save a pesky stack call and other shenanigans, and you could likely get rid of the arrays or stack allocate them

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool GetLowest(out int result, int[] c, int[] i, int[][] a)

Benchmarks

Method	N	Mean	Error	StdDev	Gen 0	Gen 1	Allocated
Mine	10	90.89 ns	0.581 ns	0.544 ns	0.0153	-	128 B
Yours	10	2,069.31 ns	13.881 ns	12.984 ns	0.0343	-	288 B
Dmitrys	10	304.75 ns	1.331 ns	1.245 ns	0.0143	-	120 B
Mine	1000	8,626.12 ns	108.481 ns	101.473 ns	0.0153	-	128 B
Yours	1000	43,196.78 ns	327.480 ns	290.302 ns	1.4038	-	12,168 B
Dmitrys	1000	20,563.90 ns	64.089 ns	53.517 ns	-	-	120 B
Mine	10000	202,904.36 ns	684.727 ns	571.778 ns	-	-	128 B
Yours	10000	402,362.80 ns	3,263.325 ns	3,052.517 ns	14.1602	1.4648	120,168 B
Dmitrys	10000	205,329.07 ns	1,014.000 ns	948.496 ns	-	-	120 B

Code

[SimpleJob(RuntimeMoniker.Net50)]
[MemoryDiagnoser]
public class WeirdStuff
{
 private int[] data1;
 private int[] data2;
 private int[] data3;
 private List<int> h1;
 private List<int> h2;
 private List<int> h3;
 [Params(10, 1000, 10000)] public int N;
 [GlobalSetup]
 public void Setup()
 {
 var r = new Random(42);
 data1 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
 data2 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
 data3 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
 h1 = new List<int>(data1);
 h2 = new List<int>(data2);
 h3 = new List<int>(data3);
 }
 [Benchmark]
 public int Mine()
 {
 var a = new[] {data1, data2, data3};
 var i = new int[3];
 var c = new int[3];
 var last = 0;
 while (true)
 {
 if (!GetLowest(out var index, c, i, a))
 return last;
 c[index] += a[index][i[index]];
 i[index]++;
 if (c[0] == c[1] && c[1] == c[2])
 last = c[0];
 //Console.WriteLine($"Current = {string.Join(", ", c)}, Index = {index}, Last = {last}");
 }
 }
 [MethodImpl(MethodImplOptions.AggressiveInlining)]
 private static bool GetLowest(out int result, int[] c, int[] i, int[][] a)
 {
 result = -1;
 if (c[0] <= c[1] && c[0] <= c[2] && i[0] < a[0].Length - 1) result = 0;
 else if (c[1] <= c[0] && c[1] <= c[2] && i[1] < a[1].Length - 1) result = 1;
 else if (i[2] < a[2].Length - 1) result = 2;
 else return false;
 return true;
 }
 [Benchmark]
 public int Yours()
 {
 var result = 0;
 if (IsEmpty(h1) || IsEmpty(h2) || IsEmpty(h3)) return result;
 var h1Stack = GetStack(h1);
 var h2Stack = GetStack(h2);
 var h3Stack = GetStack(h3);
 while (h1Stack.Any() && h2Stack.Any() && h3Stack.Any())
 {
 var h1Height = LocalPeek(h1Stack);
 var h2Height = LocalPeek(h2Stack);
 var h3Height = LocalPeek(h3Stack);
 if (h1Height == h2Height && h1Height == h3Height) return CountHeight(h1Stack);
 var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
 if (h1Height == max && h1Stack.Any()) h1Stack.Pop();
 if (h2Height == max && h2Stack.Any()) h2Stack.Pop();
 if (h3Height == max && h3Stack.Any()) h3Stack.Pop();
 }
 return 0;
 }
 bool IsEmpty(List<int> stack)
 {
 return (!stack?.Any() ?? true);
 }
 int LocalPeek(Stack<int> stack)
 {
 if (stack.Any()) return stack.Peek();
 return 0;
 }
 Stack<int> GetStack(List<int> numbers)
 {
 var stack = new Stack<int>(numbers.Count);
 for (var i = numbers.Count - 1; i >= 0; --i)
 {
 stack.Push(numbers[i] + LocalPeek(stack));
 }
 return stack;
 }
 static int CountHeight(Stack<int> stack)
 {
 return stack.Any() ? stack.Peek() : 0;
 }
 [Benchmark]
 public int Dmitrys()
 {
 if (h1.Count <= 0 || h2.Count <= 0 || h3.Count <= 0)
 return 0;
 int height1 = h1.Sum();
 int height2 = h2.Sum();
 int height3 = h3.Sum();
 int p1 = 0;
 int p2 = 0;
 int p3 = 0;
 while (height1 != height2 || height1 != height3)
 {
 if (height1 >= height2 && height1 >= height3)
 height1 -= h1[p1++];
 else if (height2 >= height1 && height2 >= height3)
 height2 -= h2[p2++];
 else
 height3 -= h3[p3++];
 }
 return height1;
 }
}

• David Oganov: I'll wait a bit for possible answer with usage of Stack data structure before closing the question. But as I understand there's no such solution. And probably there's something wrong with the HackerRank's problem. They shouldn't put that into Stacks category, as the solution using stacks simple runs out of time and you are forced to use array/list.

Answer 2

You can check the top solutions from the other users.

• David Oganov: I know there are multiple ways to solve this, but my goal is not to have this problem solved in my profile. In that case I would be just copy pasting solutions. I come up with algorithms and implement them by myself. In this case, my algorithm fails at some test cases. I just wonder if there's a possible way to pass all the test cases with my algorithm with a small optimization, or should I come up with another solution.
• Mong Zhu: @ConnorStoop you probably meant to say "comment" ?=! ;)

Answer 3

I suggest removing cylinders from the highest stack while stacks are of different heights:

// Assuming that we don't have cylinders of negative height
public static int equalStacks(List<int> h1, List<int> h2, List<int> h3) {
 if (h1.Count <= 0 || h2.Count <= 0 || h3.Count <= 0)
 return 0;
 int height1 = h1.Sum();
 int height2 = h2.Sum();
 int height3 = h3.Sum();
 int p1 = 0;
 int p2 = 0;
 int p3 = 0;
 while (height1 != height2 || height1 != height3) {
 if (height1 >= height2 && height1 >= height3) 
 height1 -= h1[p1++];
 else if (height2 >= height1 && height2 >= height3) 
 height2 -= h2[p2++];
 else 
 height3 -= h3[p3++];
 }
 return height1; 
}

• David Oganov: Yeah, this is pretty much the same that my code does. Except this doesn't use stack data structure and removes one at a time. My solution uses stacks & removes 1 or 2 blocks if they both are violating desired result. But this still doesn't answer my question. I guess there's no further improvement that can be done.
• Dmitrii Bychenko: @David Oganov: it does use stack structure (stack is actually emulated as list); I'd remove (pop) items from list but move first element pointer (p1, p2, p3) instead
• David Oganov: Yeah, it's emulated & this will definately work faster, since you work with the list directly.