23.04.11 Today’s Leetcode

2390. Removing Stars From a String (medium)

class Solution:
    def removeStars(self, s: str) -> str:
        stack = [] 
        for char in s:
            if char == '*':
                stack.pop()
            else:
                stack.append(char)
        return ''.join(stack)

1021. Remove Outermost Parentheses (easy)

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        stack = []
        p = []
        for index, char in enumerate(s):
            if len(stack) == 0:
                p.append(index)
            if char == '(': stack.append(char)
            if char == ')': stack.pop()
            if len(stack) == 0:
                p.append(index)
        
        res = ''
        for i in range(0, len(p), 2):
            a, b = p[i], p[i + 1]
            res += s[a + 1:b]
        return res

581. Shortest Unsorted Continuous Subarray (medium)

failed at 133/333

class Solution:
    def findUnsortedSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        start, end = n - 1, 0
        temp = arr[0]
        for i in range(n - 1):
            temp = max(temp, arr[i])
            if temp > arr[i + 1]:
                start = min(start, i)
                end = max(end, i + 1)
        print(start, end)
        return end - start + 1 if start < end else 0

O(n) Solution

class Solution:
    def findUnsortedSubarray(self, arr: List[int]) -> int:
        # Find index of element out of order
        left, right = 0, 0
        for i in range(len(arr)-1):
            if arr[i] > arr[i+1]:
                left = i
                break

        for j in range(len(arr)-1, -1, -1):
            if arr[j-1] > arr[j]:
                right = j
                break

        minElem, maxElem = min(arr[left: right+1]), max(arr[left: right+1])

        # Find MIN & MAX Element its proper position in the array
        i, j = 0, len(arr)-1
        # Loop till the last occurance if they are equal
        while arr[i] <= minElem and i < len(arr)-1:
            i += 1

        left = i

        # Loop till first occurance if they are equal
        while arr[j] >= maxElem and j > -1:
            j -= 1

        right = j

        return right-left+1 if right-left > 0 else 0