Car Fleet Problem

The Car Fleet Problem is a common problem that involves calculating the number of car fleets
arriving at the destination. A car fleet is defined as a group of cars that are going to the same
destination and are traveling together because they are unable to overtake each other.

Problem Statement:

You are given:

1. N cars that travel at different speeds.

2. Each car has a position on a one-lane road.
3. The cars all move towards a destination at different speeds.

A car fleet is a group of cars that will travel together because a faster car will catch up with a
slower car, and thus, they will move together.

Task:

Calculate how many car fleets will reach the destination.

Example:

Input:
target = 12
position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]

Output:
3

Explanation:

● Car at position 10 moves at speed 2, car at position 8 moves at speed 4, car at position
0 moves at speed 1, car at position 5 moves at speed 1, and car at position 3 moves at
speed 3.
● The cars that start at positions 10 and 8 will reach the target together as the one at
position 10 moves slower than the one at position 8. Similarly, cars at positions 5 and 3
will also form a fleet together.

Approach:

1. Sort the Cars by Position:

 ○First, you should sort the cars by their positions in decreasing order, because the
car starting from the farthest position will likely be the leading car.
2. Calculate Time to Reach the Destination:

○For each car, the time to reach the destination can be calculated using the
formula: time=target−positionspeed\text{time} = \frac{\text{target} -
\text{position}}{\text{speed}}
○ After calculating the time, we can process the cars in order of their positions.
3. Group Cars into Fleets:

○Starting with the car at the furthest position, keep track of the car fleets. A new
fleet is formed when the current car reaches the destination later than the car
ahead of it. Otherwise, the current car joins the fleet formed by the car ahead of
it.
4. Count the Fleets:

○ For each car, check if it will catch up with the car in front. If it does, they will form
a fleet. If it doesn't, the car forms a new fleet by itself.

Java Solution:
import [Link].*;

public class CarFleet {

public int carFleet(int target, int[] position, int[] speed) {

// Step 1: Create a list of pairs (position, speed)
int n = [Link];
double[][] cars = new double[n][2]; // Array to store position and speed

// Step 2: Populate the cars array

for (int i = 0; i < n; i++) {
cars[i][0] = position[i];
cars[i][1] = speed[i];
}

// Step 3: Sort cars based on the position in decreasing order

[Link](cars, (a, b) -> [Link](b[0], a[0]));

// Step 4: Initialize a stack to store the times of each car to reach the target
Stack<Double> stack = new Stack<>();

// Step 5: Iterate over the sorted cars and calculate the time for each car to reach the target
for (int i = 0; i < n; i++) {
// Time = (Target - Position) / Speed
 double time = (target - cars[i][0]) / cars[i][1];

// If the stack is empty or the current car will reach the target later than the car in the fleet
if ([Link]() || time > [Link]()) {
[Link](time);
}
}

// Step 6: The number of fleets is the size of the stack

return [Link]();
}

public static void main(String[] args) {

CarFleet solution = new CarFleet();

int target = 12;

int[] position = {10, 8, 0, 5, 3};
int[] speed = {2, 4, 1, 1, 3};

[Link]("Number of Car Fleets: " + [Link](target, position, speed));

}
}

Explanation of the Solution:

1. Car Information:

○We create a 2D array cars, where each element contains the position and
speed of a car.
2. Sorting Cars:

○
We sort the cars based on their position in descending order, because the car
starting at the farthest position will be the first one to consider.
3. Calculating Time:

○
For each car, we calculate the time it takes to reach the destination using the
formula: time=target−positionspeed\text{time} = \frac{\text{target} -
\text{position}}{\text{speed}}
○ We use a stack to store the times. If the current car's time is greater than the time
of the car ahead, it means the current car will catch up and they will form a fleet,
so we add its time to the stack.
4. Count Fleets:
 ○ The number of fleets is simply the number of times we add a car’s time to the
stack, which corresponds to how many fleets formed.

Time Complexity:

● Sorting the cars takes O(nlog⁡n)O(n \log n), where nn is the number of cars.
● The iteration through the cars to calculate the time and determine the fleets takes
O(n)O(n).

Thus, the overall time complexity is O(nlog⁡n)O(n \log n).

Space Complexity:

● We are using a stack to store the times, which requires O(n)O(n) space.
● So, the space complexity is O(n)O(n).

Conclusion:

This solution efficiently calculates the number of car fleets arriving at the target using a
combination of sorting and stack operations. The key idea is to track the time it takes each car
to reach the target and use a stack to handle the merging of fleets based on arrival times.

Valid Parentheses Problem

The Valid Parentheses problem asks you to determine whether a given string of parentheses
(or brackets) is valid. A string is considered valid if:

1. Every opening parenthesis has a corresponding closing parenthesis.

2. Parentheses must be closed in the correct order.

This is a classic problem that can be solved using a stack data structure, where we push
opening parentheses and pop them when encountering closing parentheses.

Problem Statement:

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is
valid. An input string is valid if:

● Open brackets must be closed by the corresponding closing brackets.

● Open brackets must be closed in the correct order.

Example:
Input: "()[]{}"
Output: true
Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

Approach:

1. Use a Stack:
○ Traverse the string from left to right.
○ If you encounter an opening parenthesis ((, [, {), push it onto the stack.
○ If you encounter a closing parenthesis (), ], }), check if the stack is empty:
■ If the stack is empty, it means there's no corresponding opening
parenthesis, so the string is invalid.
■ If the stack is not empty, pop the top of the stack and check if it matches
the corresponding opening parenthesis.
2. At the end:
○ If the stack is empty, the parentheses are valid (all opening parentheses have
matching closing parentheses).
○ If the stack is not empty, the parentheses are invalid (some opening parentheses
do not have matching closing parentheses).

Java Solution:
import [Link];

public class ValidParentheses {

public boolean isValid(String s) {

// Initialize an empty stack to store opening parentheses
Stack<Character> stack = new Stack<>();

// Traverse through each character in the string

for (int i = 0; i < [Link](); i++) {
char c = [Link](i);

// If the current character is an opening parenthesis, push it onto the stack

if (c == '(' || c == '{' || c == '[') {
[Link](c);
 }
// If it's a closing parenthesis, check if it matches the top of the stack
else if (c == ')' || c == '}' || c == ']') {
// If the stack is empty or the top of the stack doesn't match the current closing
parenthesis
if ([Link]() || !isMatchingPair([Link](), c)) {
return false; // Invalid
}
}
}

// At the end, if the stack is empty, the parentheses are valid

return [Link]();
}

// Helper method to check if the opening and closing parentheses match

private boolean isMatchingPair(char open, char close) {
return (open == '(' && close == ')') ||
(open == '{' && close == '}') ||
(open == '[' && close == ']');
}

public static void main(String[] args) {

ValidParentheses solution = new ValidParentheses();

// Test cases
[Link]([Link]("()[]{}")); // true
[Link]([Link]("(]")); // false
[Link]([Link]("([)]")); // false
[Link]([Link]("{[]}")); // true
}
}

Explanation of the Solution:

1. Stack Initialization:

○ We start by creating an empty stack (stack) that will hold the opening
parentheses ((, {, [).
2. Traversing the String:

○ We loop through each character in the string s.

○ If the character is an opening parenthesis ((, {, or [), we push it onto the stack.
 ○If the character is a closing parenthesis (), }, or ]), we check if the stack is
empty or if the top of the stack doesn't match the corresponding opening
parenthesis:
■ If the stack is empty, it means there's no opening parenthesis for the
current closing parenthesis, so we return false.
■ If the top of the stack doesn't match the current closing parenthesis, it
means the parentheses are not balanced, so we also return false.
3. Matching Pair Check:

○ The helper function isMatchingPair checks if the pair of parentheses

(opening and closing) are valid, i.e., if they match correctly (() , {}, []).
4. Final Check:

○ After the loop, if the stack is empty, it means all the opening parentheses had
matching closing parentheses, so the string is valid, and we return true.
○ If the stack is not empty, it means some opening parentheses did not have
corresponding closing parentheses, so we return false.

Time Complexity:

● The time complexity is O(n), where n is the length of the string. We only iterate through
the string once, and each operation (push and pop) on the stack takes constant time,
O(1).

Space Complexity:

● The space complexity is O(n), where n is the length of the string. In the worst case, the
stack may need to store all n characters (when the string contains only opening
parentheses).

Test Cases:
Valid Parentheses:

[Link]([Link]("()[]{}")); // true

1. Explanation: All the parentheses are correctly paired.

Invalid Parentheses (Mismatched Pair):

[Link]([Link]("(]")); // false
 2. Explanation: The opening parenthesis ( does not have a matching closing parenthesis
].

Invalid Parentheses (Incorrect Order):

[Link]([Link]("([)]")); // false

3. Explanation: The parentheses are not closed in the correct order. [ is closed before (.

Valid Parentheses (Complex):

[Link]([Link]("{[]}")); // true

4. Explanation: All the parentheses are correctly paired and nested.

Conclusion:

The Valid Parentheses problem can be solved efficiently using a stack, which helps in
maintaining the order and balance of opening and closing parentheses. The stack-based
approach ensures that we can check for validity in linear time.

Min Stack Problem

The Min Stack problem involves designing a stack that supports all the basic stack operations,
push, pop, and top, and also supports retrieving the minimum element in constant time
(O(1)).

Problem Statement:

Design a data structure that supports the following operations:

1. push(x): Pushes the element x onto the stack.

2. pop(): Removes the element on the top of the stack.
3. top(): Retrieves the element on the top of the stack.
4. getMin(): Returns the minimum element in the stack.

Example:
MinStack minStack = new MinStack();
[Link](-2);
[Link](0);
[Link](-3);
[Link]([Link]()); // Returns -3.
[Link]();
[Link]([Link]()); // Returns 0.
[Link]([Link]()); // Returns -2.

Approach:

The challenge in this problem is to maintain the minimum element in the stack while still
supporting the basic stack operations in constant time.

To solve this, we can use two stacks:

1. Main Stack: This stack will store all the elements.

2. Min Stack: This stack will store the minimum values. The minimum value at any point in
time will always be at the top of the minStack.

Steps:

1. Push Operation:

○ When pushing a new element, push it onto the main stack.

○ If the minStack is empty or the current element is smaller than or equal to the
top of the minStack, push it onto the minStack.
2. Pop Operation:

○When popping an element from the stack, check if the element is equal to the top
of the minStack. If it is, also pop it from the minStack since it was the
minimum element.
3. Get Minimum:

○ The top element of the minStack always represents the minimum element in the
stack.

Java Solution:
import [Link];

public class MinStack {

// Main stack to store the elements

private Stack<Integer> stack;
// Min stack to store the minimum values
private Stack<Integer> minStack;
 /** Initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}

/** Push the element x onto the stack. */

public void push(int x) {
// Push the element onto the main stack
[Link](x);

// If the min stack is empty or the current element is smaller than the current minimum
// push it onto the min stack
if ([Link]() || x <= [Link]()) {
[Link](x);
}
}

/** Removes the element on the top of the stack. */

public void pop() {
// Pop the element from the main stack
int poppedElement = [Link]();

// If the popped element is the same as the top of the min stack, pop it from the min stack
as well
if (poppedElement == [Link]()) {
[Link]();
}
}

/** Get the top element. */

public int top() {
return [Link]();
}

/** Retrieve the minimum element in the stack. */

public int getMin() {
return [Link]();
}

public static void main(String[] args) {

MinStack minStack = new MinStack();

[Link](-2);
 [Link](0);
[Link](-3);

[Link]([Link]()); // Returns -3.

[Link]();
[Link]([Link]()); // Returns 0.
[Link]([Link]()); // Returns -2.
}
}

Explanation of the Solution:

1. Two Stacks:

○ stack: This stack stores the actual elements pushed by the user.
○ minStack: This stack stores the minimum element up to the current point. The
top of minStack always holds the minimum element.
2. Push Operation:

○ When we push a new element x, it goes into the stack.

○ If minStack is empty or x is smaller than or equal to the top of minStack, we
also push x onto minStack because it might be the new minimum.
3. Pop Operation:

○ When we pop an element from the stack, we check if the popped element is the
same as the top of the minStack. If it is, we also pop it from the minStack to
maintain the correct minimum value.
4. Top Operation:

○ The top() operation simply returns the top element of the stack.
5. Get Minimum Operation:

○ The getMin() operation retrieves the top element of the minStack, which
represents the minimum value in the stack.

Time Complexity:

● Push operation: O(1), since we are only pushing onto two stacks.
● Pop operation: O(1), since we are popping from two stacks (if necessary).
● Top operation: O(1), since we are just peeking the top element of the stack.
 ● GetMin operation: O(1), since we are just peeking the top element of the minStack.

Space Complexity:

● O(n), where n is the number of elements pushed onto the stack. In the worst case, both
stack and minStack will contain all n elements.

Test Cases:
Test with mixed elements:

MinStack minStack = new MinStack();

[Link](-2);
[Link](0);
[Link](-3);
[Link]([Link]()); // Output: -3
[Link]();
[Link]([Link]()); // Output: 0
[Link]([Link]()); // Output: -2

1.

Test with all elements being the same:

MinStack minStack = new MinStack();

[Link](1);
[Link](1);
[Link](1);
[Link]([Link]()); // Output: 1

2.

Test with decreasing elements:

MinStack minStack = new MinStack();

[Link](3);
[Link](2);
[Link](1);
[Link]([Link]()); // Output: 1

3.

Conclusion:
The Min Stack problem is an excellent example of how to use an auxiliary data structure (in this
case, a second stack) to efficiently track additional information (the minimum value) while still
maintaining the time complexity of basic stack operations. Using two stacks allows us to achieve
O(1) time complexity for push, pop, top, and getMin operations.

Evaluate Reverse Polish Notation (RPN) Problem

The Evaluate Reverse Polish Notation (RPN) problem involves evaluating an expression that
is written in Reverse Polish Notation. In Reverse Polish Notation, operators follow their
operands, meaning that the expression does not require parentheses or operator precedence
rules to determine the order of operations.

Problem Statement:

You are given an array of strings tokens that represent an arithmetic expression in Reverse
Polish Notation. Evaluate the expression and return the result.

Valid operators are:

● + (addition)
● - (subtraction)
● * (multiplication)
● / (integer division)

Note:

● Integer division should truncate toward zero.

● The expression is guaranteed to be valid, with no division by zero.

Example:
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4", "13", "5", "/", "+"]

Output: 6
Explanation: (13 / 5) = 2, then (4 + 2) = 6

Input: tokens = ["10", "6", "9", "3", "/", "-", "*"]

Output: 50
Explanation: (9 / 3) = 3, (6 - 3) = 3, (10 * 3) = 30

Approach:
To solve this problem, we can use a stack data structure. The process is as follows:

1. Traverse the tokens one by one:

○ If the token is a number (operand), push it onto the stack.
○ If the token is an operator (+, -, *, /), pop the two top operands from the stack,
perform the operation, and push the result back onto the stack.
2. After processing all tokens, the final result will be the only number left in the stack.

Handling Operations:

● For each operator, you pop the top two operands from the stack, apply the operator, and
push the result back.
● Ensure that integer division truncates toward zero (this is handled correctly in Java by
casting the result of integer division).

Java Solution:
import [Link];

public class EvaluateRPN {

public int evalRPN(String[] tokens) {

// Create a stack to store the operands
Stack<Integer> stack = new Stack<>();

// Iterate over each token in the RPN expression

for (String token : tokens) {
// If the token is an operator
if ([Link]("+") || [Link]("-") || [Link]("*") || [Link]("/")) {
// Pop the two operands
int b = [Link]();
int a = [Link]();

// Apply the operator and push the result back to the stack
switch (token) {
case "+":
[Link](a + b);
break;
case "-":
[Link](a - b);
break;
case "*":
[Link](a * b);
break;
case "/":
 // Integer division truncates toward zero
[Link](a / b);
break;
}
} else {
// If the token is a number, push it onto the stack
[Link]([Link](token));
}
}

// The final result is the only number left in the stack

return [Link]();
}

public static void main(String[] args) {

EvaluateRPN solution = new EvaluateRPN();

// Test case 1
String[] tokens1 = {"2", "1", "+", "3", "*"};
[Link]([Link](tokens1)); // Output: 9

// Test case 2
String[] tokens2 = {"4", "13", "5", "/", "+"};
[Link]([Link](tokens2)); // Output: 6

// Test case 3
String[] tokens3 = {"10", "6", "9", "3", "/", "-", "*"};
[Link]([Link](tokens3)); // Output: 50
}
}

Explanation of the Solution:

1. Stack Initialization:

○We use a stack to store operands as we traverse through the tokens array.
Whenever we encounter an operator, we pop the top two elements from the
stack, apply the operator, and push the result back onto the stack.
2. Processing Tokens:

○ For each token, we check if it's an operator (+, -, *, /). If it is, we:
■ Pop the top two operands from the stack.
■ Apply the operator on these two operands.
 ■ Push the result back onto the stack.
○ If the token is a number, we simply convert it to an integer and push it onto the
stack.
3. Final Result:

○ After processing all tokens, the stack will contain exactly one element, which is
the final result of the RPN expression.

Time Complexity:

● O(n), where n is the number of tokens in the input array. We process each token exactly
once, and each operation (push, pop) on the stack takes constant time.

Space Complexity:

● O(n), where n is the number of tokens. In the worst case, the stack will hold all n
operands if the expression does not contain any operators.

Test Cases:
Example 1:

String[] tokens1 = {"2", "1", "+", "3", "*"};

[Link]([Link](tokens1)); // Output: 9

1. Explanation: (2 + 1) * 3 = 9.

Example 2:

String[] tokens2 = {"4", "13", "5", "/", "+"};

[Link]([Link](tokens2)); // Output: 6

2. Explanation: 13 / 5 = 2 (integer division), then 4 + 2 = 6.

Example 3:

String[] tokens3 = {"10", "6", "9", "3", "/", "-", "*"};

[Link]([Link](tokens3)); // Output: 50

3. Explanation: 9 / 3 = 3, 6 - 3 = 3, 10 * 3 = 30.
Edge Case - Single Operand:

String[] tokens4 = {"42"};

[Link]([Link](tokens4)); // Output: 42

4. Explanation: Only one operand, so the result is 42.

Conclusion:

The Evaluate Reverse Polish Notation problem is an excellent exercise in using the stack
data structure for evaluating expressions in a non-standard notation. The key idea is that
operators apply to the most recent operands, which makes the stack a perfect choice for solving
this problem in linear time.

Generate Parentheses Problem

The Generate Parentheses problem asks you to generate all combinations of well-formed
parentheses. Given an integer n, you need to generate all possible valid combinations of n pairs
of parentheses.

Problem Statement:

Given an integer n, generate all combinations of n pairs of parentheses.

Example:
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Input: n = 1
Output: ["()"]

Approach:

The problem can be solved using backtracking. The idea is to generate parentheses by
recursively adding an opening parenthesis ( or a closing parenthesis ) while maintaining the
following conditions:

1. The number of opening parentheses ( should never exceed n.

2. The number of closing parentheses ) should never exceed the number of opening
parentheses ( at any point.

Backtracking Algorithm Steps:

 1. Base Case: If the current string has reached a length of 2 * n (which means all
parentheses are used), add this string to the result.
2. Recursive Case:
○ Add an opening parenthesis ( if the number of opening parentheses is less than
n.
○ Add a closing parenthesis ) if the number of closing parentheses is less than the
number of opening parentheses.
3. Continue the recursion until all valid combinations are generated.

Java Solution:
import [Link];
import [Link];

public class GenerateParentheses {

public List<String> generateParenthesis(int n) {

List<String> result = new ArrayList<>();
generateParenthesisHelper(result, "", 0, 0, n);
return result;
}

// Helper function to perform backtracking

private void generateParenthesisHelper(List<String> result, String current, int open, int close,
int n) {
// If the current string has reached the maximum length (2 * n)
if ([Link]() == 2 * n) {
[Link](current); // Add the valid combination to the result
return;
}

// Add an opening parenthesis if we haven't used up all opening parentheses

if (open < n) {
generateParenthesisHelper(result, current + "(", open + 1, close, n);
}

// Add a closing parenthesis if we have more opening parentheses than closing

parentheses
if (close < open) {
generateParenthesisHelper(result, current + ")", open, close + 1, n);
}
}

public static void main(String[] args) {

 GenerateParentheses solution = new GenerateParentheses();

// Test case 1
List<String> result1 = [Link](3);
[Link](result1); // Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

// Test case 2
List<String> result2 = [Link](1);
[Link](result2); // Output: ["()"]
}
}

Explanation of the Solution:

1. Helper Function (generateParenthesisHelper):

○ The function takes parameters:

■ result: A list that stores all the valid combinations of parentheses.
■ current: The current string being built.
■ open: The count of opening parentheses used so far.
■ close: The count of closing parentheses used so far.
■ n: The total number of pairs of parentheses we need to generate.
2. Base Case:

○ If the length of current equals 2 * n, it means we've formed a valid

combination of parentheses, so we add it to the result.
3. Recursive Case:

○ We add an opening parenthesis ( if the number of open parentheses used is less

than n.
○We add a closing parenthesis ) if the number of closing parentheses used is less
than the number of opening parentheses used.
4. Recursive Calls:

○The recursion explores all possible combinations by adding either an opening or

closing parenthesis at each step.
5. Main Function:

○ We invoke the helper function starting with an empty string and zero counts for
both open and close parentheses.
○ Finally, we return the list result that contains all valid combinations.
Time Complexity:

The time complexity is O(4^n / √n), which is derived from the Catalan number that counts the
number of valid combinations of n pairs of parentheses. This is because there are many valid
combinations, and the algorithm needs to explore all of them.

Space Complexity:

The space complexity is O(n) for the recursion stack, as the maximum depth of recursion is 2 *
n. Additionally, we store the result in a list, which can hold up to O(4^n / √n) valid strings.

Test Cases:
Test Case 1 (n = 3):

List<String> result1 = [Link](3);

[Link](result1); // Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

1. Explanation: There are 5 valid combinations for 3 pairs of parentheses.

Test Case 2 (n = 1):

List<String> result2 = [Link](1);

[Link](result2); // Output: ["()"]

2. Explanation: There is only 1 valid combination for 1 pair of parentheses.

Test Case 3 (n = 2):

List<String> result3 = [Link](2);

[Link](result3); // Output: ["(())", "()()"]

3. Explanation: There are 2 valid combinations for 2 pairs of parentheses.

Test Case 4 (n = 4):

List<String> result4 = [Link](4);

[Link](result4); // Output: [ ...] (All valid combinations for 4 pairs)

4.

Conclusion:
The Generate Parentheses problem is a typical example of backtracking, where we explore
all possible combinations of valid parentheses by ensuring that the number of opening
parentheses is never less than the number of closing parentheses at any point. The algorithm
efficiently generates all valid combinations and returns them in a list. The approach handles the
constraints well and works within a reasonable time for small to medium-sized n.

Daily Temperatures Problem

The Daily Temperatures problem involves finding the number of days you would have to wait
for a warmer temperature for each day in a list of daily temperatures.

Problem Statement:

Given an array of integers temperatures where temperatures[i] represents the

temperature on the i-th day, return an array answer such that answer[i] is the number of
days you have to wait after the i-th day to get a warmer temperature. If there is no future day
for which this is possible, put 0 instead.

Example:
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation:
- On day 0, the next warmer temperature is on day 1 (74 > 73).
- On day 1, the next warmer temperature is on day 2 (75 > 74).
- On day 2, the next warmer temperature is on day 6 (76 > 75).
- On day 3, the next warmer temperature is on day 4 (72 > 71).
- On day 4, the next warmer temperature is on day 5 (72 > 69).
- On day 5, the next warmer temperature is on day 6 (76 > 72).
- On day 6, there is no future day with a warmer temperature.
- On day 7, there is no future day with a warmer temperature.

Approach:

The problem can be efficiently solved using a stack data structure, which helps in keeping track
of the indices of the temperatures in a way that allows us to easily compute the number of days
until a warmer temperature.

Steps:

1. Stack: Use a stack to store indices of the temperatures array. The stack will help us
track which days' temperatures we haven't yet found a warmer temperature for.
2. Iterate through the temperatures:
 ○ For each temperature, check if it's warmer than the temperature corresponding to
the index at the top of the stack (this is the last day we haven't found a warmer
temperature for).
○ If it is warmer, pop the stack and calculate how many days it took for that index to
reach a warmer temperature (current index - index popped from the stack).
○ Push the current index onto the stack.
3. After the loop, the remaining elements in the stack correspond to days where there is no
future day with a warmer temperature, so we assign 0 for those days.

Java Solution:
import [Link];

public class DailyTemperatures {

public int[] dailyTemperatures(int[] temperatures) {

int n = [Link];
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();

for (int i = 0; i < n; i++) {

// While stack is not empty and the current temperature is higher than the temperature
// of the day at the index stored in the stack
while (![Link]() && temperatures[i] > temperatures[[Link]()]) {
int index = [Link]();
result[index] = i - index; // Calculate the number of days to wait for a warmer
temperature
}
[Link](i); // Push the current index to the stack
}

return result; // Return the result array

}

public static void main(String[] args) {

DailyTemperatures solution = new DailyTemperatures();

// Test case 1
int[] temperatures1 = {73, 74, 75, 71, 69, 72, 76, 73};
int[] result1 = [Link](temperatures1);
for (int i : result1) {
[Link](i + " "); // Output: 1 1 4 2 1 1 0 0
}
[Link]();
 // Test case 2
int[] temperatures2 = {30, 40, 50, 60};
int[] result2 = [Link](temperatures2);
for (int i : result2) {
[Link](i + " "); // Output: 1 1 1 0
}
[Link]();

// Test case 3
int[] temperatures3 = {30, 20, 10};
int[] result3 = [Link](temperatures3);
for (int i : result3) {
[Link](i + " "); // Output: 0 0 0
}
[Link]();
}
}

Explanation of the Solution:

1. Stack Usage:

○ The stack holds the indices of the temperatures array. As we iterate through the
temperatures, we check if the current temperature is higher than the temperature
at the index stored at the top of the stack.
○ If it is, it means we've found the next warmer temperature for the day at the top of
the stack. We pop that index from the stack, calculate the difference in days
(current index - popped index), and store that in the result array.
○ We continue this process until we have found the next warmer temperature for all
the days in the stack.
2. Result Array:

○ We maintain a result array where the value at each index represents the
number of days to wait for a warmer temperature.
○ If no warmer temperature is found, the value remains 0 (as initialized).
3. Time Complexity:

○ O(n), where n is the length of the temperatures array. Each index is pushed onto
the stack once and popped at most once, so the time complexity is linear.
4. Space Complexity:
 ○ O(n), where n is the length of the temperatures array. We use a stack to store
indices, which can hold at most n elements in the worst case (when the
temperatures are in strictly decreasing order).

Test Cases and Expected Outputs:

Test Case 1:

int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};

1. Expected Output: [1, 1, 4, 2, 1, 1, 0, 0]

Test Case 2:

int[] temperatures = {30, 40, 50, 60};

2. Expected Output: [1, 1, 1, 0]

Test Case 3:

int[] temperatures = {30, 20, 10};

3. Expected Output: [0, 0, 0]

Conclusion:

The Daily Temperatures problem can be efficiently solved using a stack in O(n) time. The stack
helps us keep track of indices for which we haven't found a warmer temperature, allowing us to
calculate the number of days to wait for a warmer temperature for each day. The approach is
both time-efficient and space-efficient, making it a great solution for this problem.

Largest Rectangle in Histogram Problem

The Largest Rectangle in Histogram problem involves finding the largest rectangle that can
be formed in a histogram. Each bar in the histogram has a width of 1, and the height of the bar
is represented by an integer. The goal is to find the area of the largest rectangle that can be
formed under the histogram.

Problem Statement:
Given an array of integers heights where heights[i] represents the height of the bar at
index i, find the area of the largest rectangle in the histogram.

Example:
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle is formed by the bars with heights [5, 6], which has an area
of 5 * 2 = 10.

Input: heights = [2, 4]

Output: 4
Explanation: The largest rectangle is formed by the bar with height 4, which has an area of 4 * 1
= 4.

Approach:

To solve this problem efficiently, we can use a stack to keep track of the indices of the bars in
the histogram. The stack helps us efficiently calculate the largest rectangle area by ensuring
that we process each bar in a way that allows us to find the largest possible rectangle at each
step.

Steps:

1. Initialize a Stack: The stack will store indices of the histogram bars. The stack helps us
keep track of the indices where the heights are in a non-decreasing order.
2. Iterate through the histogram:
○ For each bar, we check if its height is smaller than the height of the bar at the
index stored at the top of the stack.
○ If it is, it means we've found a bar that ends the potential rectangles formed by
the bars stored in the stack. We pop the stack and calculate the area of the
rectangle using the popped height.
○ If the current bar’s height is greater than or equal to the height at the top of the
stack, we push its index onto the stack.
3. After processing all bars, there may still be bars in the stack. These need to be
processed by considering the end of the histogram as the right boundary for calculating
the area.
4. Return the maximum area found during the entire process.

Java Solution:
import [Link];

public class LargestRectangleInHistogram {

public int largestRectangleArea(int[] heights) {
int n = [Link];
Stack<Integer> stack = new Stack<>();
int maxArea = 0;

// Traverse all the bars of the histogram

for (int i = 0; i < n; i++) {
// If the current bar is shorter than the bar at the stack's top, pop the stack
// and calculate area for the popped bar
while (![Link]() && heights[i] < heights[[Link]()]) {
int height = heights[[Link]()];
// If the stack is empty, it means the popped bar was the smallest bar so far
// and its width spans from 0 to i (the current index)
int width = [Link]() ? i : i - [Link]() - 1;
maxArea = [Link](maxArea, height * width);
}
// Push the current bar's index to the stack
[Link](i);
}

// Now, process any remaining bars in the stack

while (![Link]()) {
int height = heights[[Link]()];
int width = [Link]() ? n : n - [Link]() - 1;
maxArea = [Link](maxArea, height * width);
}

return maxArea;
}

public static void main(String[] args) {

LargestRectangleInHistogram solution = new LargestRectangleInHistogram();

// Test case 1
int[] heights1 = {2, 1, 5, 6, 2, 3};
[Link]([Link](heights1)); // Output: 10

// Test case 2
int[] heights2 = {2, 4};
[Link]([Link](heights2)); // Output: 4

// Test case 3
int[] heights3 = {1, 1, 1, 1};
 [Link]([Link](heights3)); // Output: 4
}
}

Explanation of the Solution:

1. Using a Stack:

○ We use a stack to store the indices of the bars in the histogram.

○ As we traverse the histogram, we keep checking if the current bar is smaller than
the bar at the index stored in the stack's top. If it is, it means the current bar ends
the rectangle formed by the bars in the stack, and we can calculate the area.
2. Area Calculation:

○ When we pop a bar from the stack, the popped bar represents the smallest bar in
a potential rectangle. We calculate the width of the rectangle by using the
difference between the current index and the index stored in the stack.
○ If the stack is empty after popping, it means the popped bar could extend all the
way back to the beginning of the histogram (index 0).
3. Final Calculation:

○ After iterating through all the bars, there might still be bars in the stack. These
need to be processed by treating the right end of the histogram as the boundary
for calculating the area.
4. Max Area:

○ We update the maximum area found so far by comparing it with the area of the
rectangle formed at each step.

Time Complexity:

● O(n), where n is the number of bars in the histogram. Each bar is pushed and popped
from the stack at most once.

Space Complexity:

● O(n), where n is the number of bars. The stack stores indices of bars, so in the worst
case (when the heights are in increasing order), the stack will hold n indices.

Test Cases:
Test Case 1:

int[] heights = {2, 1, 5, 6, 2, 3};

[Link]([Link](heights)); // Output: 10

1. Explanation: The largest rectangle is formed by the bars with heights [5, 6], which
has an area of 5 * 2 = 10.

Test Case 2:

int[] heights = {2, 4};

[Link]([Link](heights)); // Output: 4

2. Explanation: The largest rectangle is formed by the bar with height 4, which has an area
of 4 * 1 = 4.

Test Case 3:

int[] heights = {1, 1, 1, 1};

[Link]([Link](heights)); // Output: 4

3. Explanation: The largest rectangle is formed by all bars, which has an area of 1 * 4 =
4.

Test Case 4:

int[] heights = {1, 2, 3, 4, 5};

[Link]([Link](heights)); // Output: 9

4. Explanation: The largest rectangle is formed by the bars with heights [3, 4, 5],
which has an area of 3 * 3 = 9.

Conclusion:

The Largest Rectangle in Histogram problem can be efficiently solved using a stack in O(n)
time. By maintaining the stack of indices of the histogram bars and ensuring that we calculate
the maximum area when we encounter a smaller bar, we can find the largest possible rectangle
in linear time. This solution is both optimal and space-efficient.