SDE - 1

Initialize an empty stack.

Traverse the input string character by character.

If the current character is an opening bracket (i.e., '(', '{', '['), push it onto the stack.

If the current character is a closing bracket (i.e., ')', '}', ']'), check if the stack is empty. If it is empty, return false, because the closing bracket does not have a corresponding opening bracket. Otherwise, pop the top element from the stack and check if it matches the current closing bracket. If it does not match, return false because the brackets are not valid.

After traversing the entire input string, if the stack is empty, return true, because all opening brackets have been matched with their corresponding closing brackets. Otherwise, return false, because some opening brackets have not been matched with their corresponding closing brackets.

we transpose the matrix, it will make every row element into a column element.
Then we simply reverse every row.
Time complexity: O(n^2).

Data Structures:
Utilizes a Point class to represent 2D coordinates.
Defines a Node class to represent connections between points along with their distances.
Uses an ArrayList to store the points and a PriorityQueue for efficient connection retrieval.

Initialization:
Converts the input 2D array of points into an ArrayList of Point objects.
Initializes a HashSet to keep track of visited points.
Sets up a PriorityQueue (min-heap) to store connections based on distance.

Starting Point:
Selects the first point as the initial point of connection.
Adds the starting point to the visited set.

Connection Setup:
Calculates and adds connections from the starting point to all other points in the PriorityQueue.

Main Loop:
Iterates until all points are connected or the PriorityQueue is empty.
Picks the minimum distance connection from the PriorityQueue.
Check if the second point in the connection is already visited; if yes, skip it.

Update Cost and Visited Set:
Adds the second point to the visited set.
Updates the minimum cost with the distance of the current connection.

Expand Connections:
Adds new connections from the newly connected point to all unvisited points in the PriorityQueue.

Result:
Returns the accumulated minimum cost to connect all points.

Instead of computing the left and right parts separately, we may think of some way to do it in one iteration.

Suppose we start from both the left and right end by maintaining two pointers left and right. If the smaller tower is at the left end, water trapped would be dependent on the tower's height in the direction from left to right. Similarly, if the tower at the right end is smaller, the water trapped would be dependent on the tower's height in the direction from right to left. So we first calculate water trapped on the smaller tower among height[left] and height[right] and move the pointer associated with the smaller tower.

The loop will run till the left pointer doesn't cross the right pointer. In terms of an analogy, we can think of height[left] and height[right] as a wall of a partial container where we fix the higher end and flow water from the lower end.