SDE - 1

Use the Kadanes algorithm to solve this problem 

1) The idea is to fix the left and right columns one by one and find the maximum sum of contiguous rows for every left and right column pair. 
2) I find top and bottom row numbers (which have maximum sum) for every fixed left and right column pair. 
3) To find the top and bottom row numbers, calculate the sum of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates the sum of elements from left to right in row i. If I apply Kadane’s 1D algorithm on temp[], and get the maximum sum subarray of temp, this maximum sum would be the maximum possible sum with left and right as boundary columns. 
4) To get the overall maximum sum, we compare this sum with the maximum sum so far

While iterating over the array, check the current element, and if not in the correct place, replace that element with the index of the element that should have come to this place greedily which will give the optimal answer

Follow the below steps to solve the problem:

1) Create a new array and copy the elements of the input array
2) Sort the new array and declare a variable ans equal to 0
3) Run a for loop to traverse the elements
4) If the current element in the sorted array is not equal to the one in the input array then increase the ans by 1
And swap the current element, with the required element at this index
Return ans

Assuming that time T starts with 0. The task is to find the maximum number of lectures that are ongoing at a particular instance of time. This will give the minimum number of halls required to schedule all the lectures.
To find the number of lectures ongoing at any instance of time. Maintain a prefix_sum[] which will store the number of lectures ongoing at any instance of time t. For any lecture with timings between [s, t], do prefix_sum[s]++ and prefix_sum[t + 1]–.
Afterwards, the cumulative sum of this prefix array will give the count of lectures going on at any instance of time.
The maximum value for any time instant t in the array is the minimum number of halls required.

Follow the steps to implement the approach:

Iterate Through the Array
Calculate an index based on the absolute value of each element.
If the index is equal to ‘n,‘ count it as the largest element.
If the element at the calculated index is negative, add (index – 1) to the result vector and modify the element at that index.
If there are more than one largest element, add ‘n – 1’ to the result vector.
If the result vector is empty, add ‘-1‘ to it.
Otherwise, sort the result vector.
Return the Result Vector

The idea is to put all the opening brackets in the stack. Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration. In the end, if the stack is empty, it means all brackets are balanced or well-formed. Otherwise, they are not balanced.