Repository: TheAlgorithms/Java
Pull request #5759 (2024-10-13 07:16:36)

feat: Add `MinStackUsingSingleStack` new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5759?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `93.75000%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 63.98%. Comparing base [(`6682c7c`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/6682c7c76e2bf016e2e7b51a6027ac30d354b13e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`f1a44f5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/f1a44f51d01f4172c8128242ceedd510155e19a8?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5759?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...thealgorithms/stacks/MinStackUsingSingleStack.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5759?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fstacks%2FMinStackUsingSingleStack.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zdGFja3MvTWluU3RhY2tVc2luZ1NpbmdsZVN0YWNrLmphdmE=) | 93.75% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5759?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5759      +/-   ##
============================================
+ Coverage     63.96%   63.98%   +0.01%     
- Complexity     4172     4179       +7     
============================================
  Files           583      584       +1     
  Lines         16320    16336      +16     
  Branches       3150     3150              
============================================
+ Hits          10439    10452      +13     
- Misses         5456     5457       +1     
- Partials        425      427       +2     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5759?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

alxkm: This seems similar to a LeetCode 
Hardvan: The **MinStackUsingSingleStack** algorithm is a widely known solution in data structures, frequently discussed in programming interviews and textbooks. It is not exclusive to LeetCode but is a classic problem in designing a stack that supports `push()`, `pop()`, and retrieving the minimum element in constant time using two stacks—one to store the elements and the other to track the minimum values. You can find similar implementations and discussions on several well-known platforms, such as GeeksforGeeks and Stack Overflow, as well as in books like *Cracking the Coding Interview*. 

- [Design and Implement Special Stack Data Structure | Added Space Optimized Version
](https://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/)  
- [Stack Overflow: MinStack discussion](https://stackoverflow.com/questions/685060/design-a-stack-that-supports-push-pop-min-and-max-in-constant-time)  
- [Design a stack that supports getMin() in O(1) time and O(1) extra space](https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/)

This problem is a common way to assess problem-solving skills and understanding of space-time trade-offs in interviews and is thus not tied to any single platform.
Hardvan: The **MinStackUsingSingleStack** algorithm is a widely known solution in data structures, frequently discussed in programming interviews and textbooks. It is not exclusive to LeetCode but is a classic problem in designing a stack that supports `push()`, `pop()`, and retrieving the minimum element in constant time using two stacks—one to store the elements and the other to track the minimum values. You can find similar implementations and discussions on several well-known platforms, such as GeeksforGeeks and Stack Overflow, as well as in books like *Cracking the Coding Interview*. 

- [Design and Implement Special Stack Data Structure | Added Space Optimized Version
](https://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/)  
- [Stack Overflow: MinStack discussion](https://stackoverflow.com/questions/685060/design-a-stack-that-supports-push-pop-min-and-max-in-constant-time)  
- [Design a stack that supports getMin() in O(1) time and O(1) extra space](https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/)

This problem is a common way to assess problem-solving skills and understanding of space-time trade-offs in interviews and is thus not tied to any single platform.

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 265d1aee..6073904a 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -431,6 +431,7 @@
             * [StrobogrammaticNumber](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StrobogrammaticNumber.java)
             * [SumOfArithmeticSeries](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfArithmeticSeries.java)
             * [SumOfDigits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfDigits.java)
+            * [SumOfOddNumbers](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumOfOddNumbers.java)
             * [SumWithoutArithmeticOperators](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SumWithoutArithmeticOperators.java)
             * [TrinomialTriangle](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/TrinomialTriangle.java)
             * [TwinPrime](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/TwinPrime.java)
@@ -612,6 +613,7 @@
             * [InfixToPrefix](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/InfixToPrefix.java)
             * [LargestRectangle](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/LargestRectangle.java)
             * [MaximumMinimumWindow](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/MaximumMinimumWindow.java)
+            * [MinStackUsingSingleStack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/MinStackUsingSingleStack.java)
             * [NextGreaterElement](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/NextGreaterElement.java)
             * [NextSmallerElement](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/NextSmallerElement.java)
             * [PostfixEvaluator](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/PostfixEvaluator.java)
@@ -1009,6 +1011,7 @@
             * [StrobogrammaticNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StrobogrammaticNumberTest.java)
             * [SumOfArithmeticSeriesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfArithmeticSeriesTest.java)
             * [SumOfDigitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfDigitsTest.java)
+            * [SumOfOddNumbersTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumOfOddNumbersTest.java)
             * [SumWithoutArithmeticOperatorsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SumWithoutArithmeticOperatorsTest.java)
             * [TestArmstrong](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/TestArmstrong.java)
             * [TwinPrimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/TwinPrimeTest.java)
@@ -1164,6 +1167,7 @@
             * [InfixToPostfixTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/InfixToPostfixTest.java)
             * [InfixToPrefixTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/InfixToPrefixTest.java)
             * [LargestRectangleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/LargestRectangleTest.java)
+            * [MinStackUsingSingleStackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/MinStackUsingSingleStackTest.java)
             * [NextGreaterElementTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/NextGreaterElementTest.java)
             * [NextSmallerElementTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/NextSmallerElementTest.java)
             * [PostfixEvaluatorTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/PostfixEvaluatorTest.java)
diff --git a/src/main/java/com/thealgorithms/stacks/MinStackUsingSingleStack.java b/src/main/java/com/thealgorithms/stacks/MinStackUsingSingleStack.java
new file mode 100644
index 00000000..f5e526b1
--- /dev/null
+++ b/src/main/java/com/thealgorithms/stacks/MinStackUsingSingleStack.java
@@ -0,0 +1,65 @@
+package com.thealgorithms.stacks;
+
+import java.util.EmptyStackException;
+import java.util.Stack;
+
+/**
+ * Min-Stack implementation using a single stack.
+ *
+ * This stack supports push, pop, and retrieving the minimum element
+ * in constant time (O(1)) using a modified approach where the stack
+ * stores both the element and the minimum value so far.
+ *
+ * @author Hardvan
+ */
+public class MinStackUsingSingleStack {
+    private final Stack<long[]> stack = new Stack<>();
+
+    /**
+     * Pushes a new value onto the stack.
+     * Each entry stores both the value and the minimum value so far.
+     *
+     * @param value The value to be pushed onto the stack.
+     */
+    public void push(int value) {
+        if (stack.isEmpty()) {
+            stack.push(new long[] {value, value});
+        } else {
+            long minSoFar = Math.min(value, stack.peek()[1]);
+            stack.push(new long[] {value, minSoFar});
+        }
+    }
+
+    /**
+     * Removes the top element from the stack.
+     */
+    public void pop() {
+        if (!stack.isEmpty()) {
+            stack.pop();
+        }
+    }
+
+    /**
+     * Retrieves the top element from the stack.
+     *
+     * @return The top element of the stack.
+     */
+    public int top() {
+        if (!stack.isEmpty()) {
+            return (int) stack.peek()[0];
+        }
+        throw new EmptyStackException();
+    }
+
+    /**
+     * Retrieves the minimum element in the stack.
+     *
+     * @return The minimum element so far.
+     */
+    public int getMin() {
+        if (!stack.isEmpty()) {
+            return (int) stack.peek()[1];
+        }
+        throw new EmptyStackException();
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/stacks/MinStackUsingSingleStackTest.java b/src/test/java/com/thealgorithms/stacks/MinStackUsingSingleStackTest.java
new file mode 100644
index 00000000..90887294
--- /dev/null
+++ b/src/test/java/com/thealgorithms/stacks/MinStackUsingSingleStackTest.java
@@ -0,0 +1,66 @@
+package com.thealgorithms.stacks;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import java.util.EmptyStackException;
+import org.junit.jupiter.api.Test;
+
+public class MinStackUsingSingleStackTest {
+
+    @Test
+    public void testBasicOperations() {
+        MinStackUsingSingleStack minStack = new MinStackUsingSingleStack();
+
+        minStack.push(3);
+        minStack.push(5);
+        assertEquals(3, minStack.getMin(), "Minimum should be 3");
+
+        minStack.push(2);
+        minStack.push(1);
+        assertEquals(1, minStack.getMin(), "Minimum should be 1");
+
+        minStack.pop();
+        assertEquals(2, minStack.getMin(), "Minimum should be 2");
+
+        minStack.pop();
+        assertEquals(3, minStack.getMin(), "Minimum should be 3");
+    }
+
+    @Test
+    public void testTopElement() {
+        MinStackUsingSingleStack minStack = new MinStackUsingSingleStack();
+
+        minStack.push(8);
+        minStack.push(10);
+        assertEquals(10, minStack.top(), "Top element should be 10");
+
+        minStack.pop();
+        assertEquals(8, minStack.top(), "Top element should be 8");
+    }
+
+    @Test
+    public void testGetMinAfterPops() {
+        MinStackUsingSingleStack minStack = new MinStackUsingSingleStack();
+
+        minStack.push(5);
+        minStack.push(3);
+        minStack.push(7);
+
+        assertEquals(3, minStack.getMin(), "Minimum should be 3");
+
+        minStack.pop(); // Popping 7
+        assertEquals(3, minStack.getMin(), "Minimum should still be 3");
+
+        minStack.pop(); // Popping 3
+        assertEquals(5, minStack.getMin(), "Minimum should now be 5");
+    }
+
+    @Test
+    public void testEmptyStack() {
+        MinStackUsingSingleStack minStack = new MinStackUsingSingleStack();
+
+        assertThrows(EmptyStackException.class, minStack::top, "Should throw exception on top()");
+        assertThrows(EmptyStackException.class, minStack::getMin, "Should throw exception on getMin()");
+    }
+}