Constraints

• 0 <= len(s) <= 100000
• s contains only '(', ')', '[', ']', '{', '}'
• Target complexity: O(n) time and O(n) auxiliary space
• Do not modify the input string

Examples

Solution

def solution(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return not stack

Time complexity: O(n). Space complexity: O(n).

Hints

1. Use a stack to store opening brackets as you scan from left to right.
2. When you see a closing bracket, the top of the stack must be the matching opening bracket.

Constraints

• 0 <= number of intervals <= 200000
• For every interval, start <= end
• If start == end and not both endpoints are closed, the interval is empty
• Target complexity: O(n log n) time due to sorting and O(n) extra space

Examples

Solution

def solution(intervals):
    cleaned = []
    for start, end, left_closed, right_closed in intervals:
        if start == end and not (left_closed and right_closed):
            continue
        cleaned.append((start, end, left_closed, right_closed))

    if not cleaned:
        return []

    cleaned.sort(key=lambda x: (x[0], 0 if x[2] else 1, x[1], 0 if x[3] else 1))

    result = []
    cur_start, cur_end, cur_left, cur_right = cleaned[0]

    for start, end, left_closed, right_closed in cleaned[1:]:
        if cur_end > start or (cur_end == start and (cur_right or left_closed)):
            if end > cur_end:
                cur_end = end
                cur_right = right_closed
            elif end == cur_end:
                cur_right = cur_right or right_closed
        else:
            result.append((cur_start, cur_end, cur_left, cur_right))
            cur_start, cur_end, cur_left, cur_right = start, end, left_closed, right_closed

    result.append((cur_start, cur_end, cur_left, cur_right))
    return result

Time complexity: O(n log n). Space complexity: O(n).

Hints

1. Sort intervals by starting position, with closed left endpoints before open ones when starts are equal.
2. When two merged intervals end at the same value, the merged right endpoint is closed if either interval includes that endpoint.

Constraints

• 1 <= len(expr) <= 100000
• expr contains digits, spaces, '+', '-', '*', '/', and parentheses
• The expression is valid
• Intermediate and final results fit in 32-bit signed integer range
• Target complexity: O(n) time and O(n) space

Examples

Solution

def solution(expr):
    nums = []
    ops = []
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, 'u-': 3}
    right_associative = {'u-'}

    def trunc_div(a, b):
        sign = -1 if (a < 0) ^ (b < 0) else 1
        return sign * (abs(a) // abs(b))

    def apply_op():
        op = ops.pop()
        if op == 'u-':
            nums.append(-nums.pop())
            return

        b = nums.pop()
        a = nums.pop()
        if op == '+':
            nums.append(a + b)
        elif op == '-':
            nums.append(a - b)
        elif op == '*':
            nums.append(a * b)
        else:
            nums.append(trunc_div(a, b))

    i = 0
    n = len(expr)
    prev = 'start'  # one of: start, num, op, (, )

    while i < n:
        ch = expr[i]

        if ch == ' ':
            i += 1
            continue

        if ch.isdigit():
            value = 0
            while i < n and expr[i].isdigit():
                value = value * 10 + (ord(expr[i]) - ord('0'))
                i += 1
            nums.append(value)
            while ops and ops[-1] == 'u-':
                apply_op()
            prev = 'num'
            continue

        if ch == '(':
            ops.append(ch)
            prev = '('
        elif ch == ')':
            while ops and ops[-1] != '(':
                apply_op()
            ops.pop()
            while ops and ops[-1] == 'u-':
                apply_op()
            prev = ')'
        else:
            if ch == '-' and prev in ('start', 'op', '('):
                ops.append('u-')
                prev = 'op'
            else:
                while ops and ops[-1] != '(' and (
                    precedence[ops[-1]] > precedence[ch] or
                    (precedence[ops[-1]] == precedence[ch] and ch not in right_associative)
                ):
                    apply_op()
                ops.append(ch)
                prev = 'op'
        i += 1

    while ops:
        apply_op()

    return nums[-1]

Time complexity: O(n). Space complexity: O(n).

Hints

1. Use one stack for numbers and one for operators, applying operators by precedence.
2. Treat unary minus as a separate operator with higher precedence than binary + and -.