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

feat: Add `MinStackUsingTwoStacks` 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/5758?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 `84.61538%` with `2 lines` 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 [(`cdc4952`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/cdc495229da406eef0226eccb138e0741416b328?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/5758?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...m/thealgorithms/stacks/MinStackUsingTwoStacks.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5758?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fstacks%2FMinStackUsingTwoStacks.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zdGFja3MvTWluU3RhY2tVc2luZ1R3b1N0YWNrcy5qYXZh) | 84.61% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5758?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    #5758      +/-   ##
============================================
+ Coverage     63.96%   63.98%   +0.01%     
- Complexity     4172     4178       +6     
============================================
  Files           583      584       +1     
  Lines         16320    16333      +13     
  Branches       3150     3151       +1     
============================================
+ Hits          10439    10450      +11     
- Misses         5456     5457       +1     
- Partials        425      426       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5758?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: Looks like this is not algorithm, this is leetcode issue
Hardvan: The **MinStackUsingTwoStacks** 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 6073904a..cb26c292 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -614,6 +614,7 @@
             * [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)
+            * [MinStackUsingTwoStacks](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/stacks/MinStackUsingTwoStacks.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)
@@ -1168,6 +1169,7 @@
             * [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)
+            * [MinStackUsingTwoStacksTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/stacks/MinStackUsingTwoStacksTest.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/MinStackUsingTwoStacks.java b/src/main/java/com/thealgorithms/stacks/MinStackUsingTwoStacks.java
new file mode 100644
index 00000000..47e337c8
--- /dev/null
+++ b/src/main/java/com/thealgorithms/stacks/MinStackUsingTwoStacks.java
@@ -0,0 +1,57 @@
+package com.thealgorithms.stacks;
+
+import java.util.Stack;
+
+/**
+ * Min-Stack implementation that supports push, pop, and retrieving the minimum element in constant time.
+ *
+ * @author Hardvan
+ */
+public final class MinStackUsingTwoStacks {
+    MinStackUsingTwoStacks() {
+    }
+
+    private final Stack<Integer> stack = new Stack<>();
+    private final Stack<Integer> minStack = new Stack<>();
+
+    /**
+     * Pushes a new element onto the {@code stack}.
+     * If the value is less than or equal to the current minimum, it is also pushed onto the {@code minStack}.
+     *
+     * @param value The value to be pushed.
+     */
+    public void push(int value) {
+        stack.push(value);
+        if (minStack.isEmpty() || value <= minStack.peek()) {
+            minStack.push(value);
+        }
+    }
+
+    /**
+     * Removes the top element from the stack.
+     * If the element is the minimum element, it is also removed from the {@code minStack}.
+     */
+    public void pop() {
+        if (stack.pop().equals(minStack.peek())) {
+            minStack.pop();
+        }
+    }
+
+    /**
+     * Retrieves the top element of the stack.
+     *
+     * @return The top element.
+     */
+    public int top() {
+        return stack.peek();
+    }
+
+    /**
+     * Retrieves the minimum element in the stack.
+     *
+     * @return The minimum element.
+     */
+    public int getMin() {
+        return minStack.peek();
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/stacks/MinStackUsingTwoStacksTest.java b/src/test/java/com/thealgorithms/stacks/MinStackUsingTwoStacksTest.java
new file mode 100644
index 00000000..e5deb17e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/stacks/MinStackUsingTwoStacksTest.java
@@ -0,0 +1,38 @@
+package com.thealgorithms.stacks;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class MinStackUsingTwoStacksTest {
+
+    @Test
+    public void testMinStackOperations() {
+        MinStackUsingTwoStacks minStack = new MinStackUsingTwoStacks();
+        minStack.push(3);
+        minStack.push(5);
+        assertEquals(3, minStack.getMin());
+
+        minStack.push(2);
+        minStack.push(1);
+        assertEquals(1, minStack.getMin());
+
+        minStack.pop();
+        assertEquals(2, minStack.getMin());
+    }
+
+    @Test
+    public void testMinStackOperations2() {
+        MinStackUsingTwoStacks minStack = new MinStackUsingTwoStacks();
+        minStack.push(3);
+        minStack.push(5);
+        assertEquals(3, minStack.getMin());
+
+        minStack.push(2);
+        minStack.push(1);
+        assertEquals(1, minStack.getMin());
+
+        minStack.pop();
+        assertEquals(2, minStack.getMin());
+    }
+}