Given an integer array arr of integers, the task is to find the maximum absolute difference between the nearest left smaller element and the nearest right smaller element of every element in array arr. If for any component of the arr, the nearest smaller element doesn’t exist then consider it as 0.
Examples :
Input: arr = [2, 1, 8] Output: 1
Explanation: left smaller array ls = [0, 0, 1], right smaller array rs = [1, 0, 0]. Maximum Diff of abs(ls[i] - rs[i]) = 1
Input: arr = [2, 4, 8, 7, 7, 9, 3] Output: 4
Explanation: left smaller array ls = [0, 2, 4, 4, 4, 7, 2], right smaller rs = [0, 3, 7, 3, 3, 3, 0]. Maximum Diff of abs(ls[i] - rs[i]) = abs(7 - 3) = 4
Expected Time Complexity: O(n)
Expected Space Complexity: O(n)
Constraints:
1 <= arr.size() <= 106
1<= arr[i] <=109
Approach 01:
-
C++
-
Python
class Solution {
public:
void findLeftSmallestElements(vector<int>& arr, vector<int>& leftSmallest) {
stack<int> elementStack;
for (int i = 0; i < arr.size(); i++) {
if (elementStack.empty()) {
leftSmallest.push_back(0);
}
else if (!elementStack.empty() && elementStack.top() >= arr[i]) {
while (!elementStack.empty() && elementStack.top() >= arr[i]) {
elementStack.pop();
}
if (elementStack.empty()) {
leftSmallest.push_back(0);
}
else {
leftSmallest.push_back(elementStack.top());
}
}
else if (!elementStack.empty() && elementStack.top() < arr[i]) {
leftSmallest.push_back(elementStack.top());
}
elementStack.push(arr[i]);
}
}
void findRightSmallestElements(vector<int>& arr, vector<int>& rightSmallest) {
stack<int> elementStack;
for (int i = arr.size() - 1; i >= 0; i--) {
if (elementStack.empty()) {
rightSmallest.push_back(0);
}
else if (!elementStack.empty() && elementStack.top() >= arr[i]) {
while (!elementStack.empty() && elementStack.top() >= arr[i]) {
elementStack.pop();
}
if (elementStack.empty()) {
rightSmallest.push_back(0);
}
else {
rightSmallest.push_back(elementStack.top());
}
}
else if (!elementStack.empty() && elementStack.top() < arr[i]) {
rightSmallest.push_back(elementStack.top());
}
elementStack.push(arr[i]);
}
}
int findMaxDiff(vector<int>& arr) {
int arraySize = arr.size();
vector<int> leftSmallestElements;
vector<int> rightSmallestElements;
findLeftSmallestElements(arr, leftSmallestElements);
findRightSmallestElements(arr, rightSmallestElements);
reverse(rightSmallestElements.begin(), rightSmallestElements.end());
int maximumDifference = INT_MIN;
for (int i = 0; i < arr.size(); i++) {
maximumDifference = max(maximumDifference, abs(leftSmallestElements[i] - rightSmallestElements[i]));
}
return maximumDifference;
}
};
class Solution:
def findLeftSmallestElements(self, arr, leftSmallest):
elementStack = []
for i in range(len(arr)):
if not elementStack:
leftSmallest.append(0)
elif elementStack and elementStack[-1] >= arr[i]:
while elementStack and elementStack[-1] >= arr[i]:
elementStack.pop()
if not elementStack:
leftSmallest.append(0)
else:
leftSmallest.append(elementStack[-1])
elif elementStack and elementStack[-1] < arr[i]:
leftSmallest.append(elementStack[-1])
elementStack.append(arr[i])
def findRightSmallestElements(self, arr, rightSmallest):
elementStack = []
for i in range(len(arr) - 1, -1, -1):
if not elementStack:
rightSmallest.append(0)
elif elementStack and elementStack[-1] >= arr[i]:
while elementStack and elementStack[-1] >= arr[i]:
elementStack.pop()
if not elementStack:
rightSmallest.append(0)
else:
rightSmallest.append(elementStack[-1])
elif elementStack and elementStack[-1] < arr[i]:
rightSmallest.append(elementStack[-1])
elementStack.append(arr[i])
def findMaxDiff(self, arr):
leftSmallestElements = []
rightSmallestElements = []
self.findLeftSmallestElements(arr, leftSmallestElements)
self.findRightSmallestElements(arr, rightSmallestElements)
rightSmallestElements.reverse()
maximumDifference = float('-inf')
for i in range(len(arr)):
maximumDifference = max(maximumDifference, abs(leftSmallestElements[i] - rightSmallestElements[i]))
return maximumDifference
Time Complexity
- Finding Left and Right Smallest Elements:
Both the
findLeftSmallestElementsandfindRightSmallestElementsfunctions iterate over the array of size \( n \) once. Each element is pushed and popped from the stack at most once, resulting in a time complexity of \( O(n) \) for each function. - Calculating Maximum Difference:
The
findMaxDifffunction also iterates over the array of size \( n \), leading to a time complexity of \( O(n) \). - Overall Time Complexity:
The overall time complexity of the solution is \( O(n) \), dominated by the operations on the array of size \( n \).
Space Complexity
- Stacks for Left and Right Smallest Elements:
Both
findLeftSmallestElementsandfindRightSmallestElementsuse a stack to store elements, which can hold up to \( O(n) \) elements in the worst case. - Vectors for Storing Results:
The vectors
leftSmallestElementsandrightSmallestElementseach require \( O(n) \) space to store the results. - Overall Space Complexity:
The overall space complexity of the solution is \( O(n) \), accounting for the space needed for the stacks and vectors.